speed of the ToCycles[] function
- To: mathgroup at smc.vnet.net
- Subject: [mg9302] speed of the ToCycles[] function
- From: "W. Meeussen" <w.meeussen.vdmcc at vandemoortele.be>
- Date: Mon, 27 Oct 1997 02:47:13 -0500
- Sender: owner-wri-mathgroup at wolfram.com
hi group,
in the DiscreteMath`Permutations` package lives the "ToCycles[]"
function as written by Steve Skienna.
I found that it can be accelerated by a factor of at least two. In some
applications, its speed is the main time consumer, so speeding it up is
worthwhile.
It might be a good idea to do timing tests with permutations that either
produce few large cycles, or a lot of small cycles.
Since members of this group have drastically different programming
styles, and can be tenacious in their attempts to find "optimal
algorithms", it seems a good idea to try.
here is my bit:
mytocycles[perm_List] :=
DeleteCases[Table[Module[{predi =
Position[perm, i][[1,1]], fpl},
fpl = If[i > 1 && predi < i, Null,
Drop[FixedPointList[If[perm[[#1]] <= i,
predi, perm[[#1]]] & , i], -1]];
If[fpl === Null ||
perm[[fpl[[-Min[Length[fpl], 2]]]]] =!=
fpl[[-1]] || fpl[[1]] =!= Min[fpl], Null, fpl]],
{i, 1, Length[perm]}], Null]
As the timing results below show, "mytocycles[]" has a bit of an
advantage for the "many short cycles" -case. It attains about the same
speed for the "few long cycles" -case when the permutation length is
over 200.
In[14]:=
n=501;
perm=RandomPermutation[n];
manyshort=FromCycles at Partition[perm,3];
fewlong=FromCycles at Partition[perm,Floor[n/3]];
Timing[a=ToCycles[manyshort];]
Timing[b=RotateLeft/@mytocycles[manyshort];] a==b
Timing[d=ToCycles[fewlong];]
Timing[e=RotateLeft/@mytocycles[fewlong];] d==e
Out[18]=
{209.49 Second, Null}
Out[19]=
{3.24 Second, Null}
Out[20]=
True
Out[21]=
{4.22 Second, Null}
Out[22]=
{3.85 Second, Null}
Out[23]=
True
Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be