Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1997
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1997

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: Not a machine-size real number?
  • Next by Date: Re: Not a machine-size real number?
  • Previous by thread: Utilization Of System Resources
  • Next by thread: graphing