Re: Ver 6.0 Subsets and Packed Array Question
- To: mathgroup at smc.vnet.net
- Subject: [mg82423] Re: Ver 6.0 Subsets and Packed Array Question
- From: Szabolcs Horvát <szhorvat at gmail.com>
- Date: Sat, 20 Oct 2007 05:45:06 -0400 (EDT)
- References: <ff9t7l$6e6$1@smc.vnet.net>
Dana DeLouis wrote:
> Hello. Does anyone know why the built in function Subsets "apparently" does
> not generate a Packed Array for a large table? Do you think it should? The
> reason I ask is that the Combinatorica Package function "KSubsets"
> apparently does return a packed array.
> I was having memory troubles with Subsets, and I traced the problem back to
> this.
>
> Set up (Ver 6.0)...
>
> Needs["Combinatorica`"];
> TPA[m_] := Developer`ToPackedArray[m];
> PAQ[m_] := Developer`PackedArrayQ[m];
>
> n = Binomial[20, 6]
> 38760
>
> Here are 3 tables w/ the same dimension:
>
> m1 = RandomInteger[{1, 49}, {n, 6}];
> m2 = KSubsets[Range[20], 6];
> m3 = Subsets[Range[20], {6}];
>
> Dimensions /@ {m1, m2, m3}
>
> {{38760, 6}, {38760, 6}, {38760, 6}}
>
> The first two are Packed Arrays, but the built-in function "Subsets" is not:
>
> PAQ /@ {m1, m2, m3}
>
> {True, True, False}
>
> The ByteCount of the built-in function is much larger:
>
> ByteCount /@ {m1, m2, m3}
>
> {930320, 930320, 5736512}
>
> We could make it a Packed Array and get the same ByteCount:
>
> ByteCount[TPA[m3]]
> 930320
>
>
> This makes a big difference on my 2 Gig Memory computer. Don't know how I
> even got an answer here. I can't do anything else after this point without
> shutting down the Kernel.
>
> ByteCount[KSubsets[Range[49], 6]] (* ok *)
>
> 335,611,664
>
> ByteCount[Subsets[Range[49], {6}]] (* This is tough!! *)
>
> 2,069,604,800
>
> Thanks for any insight:
> Dana
When the size of subsets is not fixed, Subsets[] does not return a list
shaped as a matrix.
This is a matrix: Subsets[{1, 2, 3, 4}, {3}]
This is not: Subsets[{1, 2, 3, 4}, 3]
Only n-dimensional numerical arrays can be represented as packed arrays,
not arbitrarily nested lists. Probably this is why Subsets[] does not
return a packed array (even when we ask for subsets of a fixed size).
--
Szabolcs