Re: Compile
- To: mathgroup at smc.vnet.net
- Subject: [mg86120] Re: Compile
- From: Peter Pein <petsie at dordos.net>
- Date: Sun, 2 Mar 2008 13:57:20 -0500 (EST)
- References: <fqb8pg$n2l$1@smc.vnet.net>
Hi Michael,
I've got no explanation but if you are interested in a version of multiset
which needs uncompiled less time than multisetC, here it is:
Clear[mulset];
mulset[0] = {{}};
mulset[n_Integer] := (mulset[n] = Block[{ms = mulset[n - 1], k},
Union[Join[Flatten[
(ReplaceList[#1, {s___, {x_Integer, y_}, e___} :>
Flatten[(Table[Insert[#1, {y, n}, k], {k, n}] & ) /@
Table[Insert[{s, e}, {x, n}, k], {k, n - 1}], 1]] & ) /@ ms
, 2],
Flatten[(Table[Insert[#1, {n, n}, k], {k, n}] & ) /@ ms, 1]
]]
]) /; n >= 1
For easyer coding this function uses lists of pairs instead of flat lists.
If you want flat lists, use Flatten /@ mulset[n].
On my linux-box Mathematica 5.2 takes 2.06s for multiset[5], multisetC uses
0.285s and mulset[5] uses 0.115s (mulset[6] finishes after 5.3s).
If you are just interested in the lengths of these lists,
a[n_] = Sum[2^(i - 2*n)*Binomial[n, i]^2*(2*(n - i))!*i!, {i, 0, n}]
--> (Gamma[1 + 2*n]*Hypergeometric1F1[-n, 1/2 - n, 1/2])/2^(2*n)
is a lot faster (see http://www.research.att.com/~njas/sequences/A000681).
Regards,
Peter
P.S.: an almost uncommented notebook can be found at
http://freenet-homepage.de/Peter_Berlin/Mathe/A000681.nb
Michael Weyrauch schrieb:
> Hello,
>
> in Mathematica V6.0.1 I define the following two functions
>
>
> multiset[n_] := Module[{ro, re, ms}, ro = Range[1, 2*n, 2];
> re = Range[2, 2*n, 2]; ms = Flatten[Table[{i, i}, {i, n}]];
> Select[Permutations[ms], ! MemberQ[Sign[#1[[re]] - #1[[ro]]], -1] & ]]
>
> multisetC = Compile[{{n, _Integer}}, Module[{ro, re, ms},
> ro = Range[1, 2*n, 2]; re = Range[2, 2*n, 2];
> ms = Flatten[Table[{i, i}, {i, n}]]; Select[Permutations[ms], ! MemberQ[Sign[#1[[re]] - #1[[ro]]], -1] & ]]];
>
> Obviously, multisetC ist just the compiled version of multiset.
>
>
> Now, I evaluate
>
>
> Timing[Length[multiset[5]]]
> Timing[Length[multisetC[5]]]
>
> and obtain
>
> {2.7339999999999995, 6210}
> {0.3440000000000003, 6210}
> so Compile was really useful.
>
> However, if I evaluate
>
> Timing[Length[multiset[6]]]
> Timing[Length[multisetC[6]]]
>
> {189.109, 202410}
>
>
> No more memory available.
> Mathematica kernel has shut down.
>
> So, the compiled version fails badly and crashes the kernel. This also happens if I evaluate this statement seperately in a
> completely fresh kernel. Enough memory is definitly available, since the uncompiled version runs smoothly. (Surprisingly the crash
> is immediate, not after some time of working along in the program, and it happens on Windows with 2GB of memory and on Linux with 32
> GB of memory.]
>
> It would be nice if some could explain this unpleasant behaviour. Is there a fix or is it a bug?
>
> Michael Weyrauch
>
>
>
>