RE: Re: O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg41958] RE: [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Wed, 11 Jun 2003 13:17:47 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: Carl K. Woll [mailto:carlw at u.washington.edu] To: mathgroup at smc.vnet.net >Sent: Tuesday, June 10, 2003 10:47 AM >To: mathgroup at smc.vnet.net >Subject: [mg41958] [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica > > >Wouter, > >Thanks, I didn't think to check out the new Combinatorica >package. I do have >a few comments, though. > >1. The RotateRight will make my output identical to Sriram's, >but that's >really unnecessary. After all, for example, the cycle {1,2,3} >is completely >equivalent to the cycle {3,1,2}. > >2. On my machine, tocycles does release its memory afterwards. >On the other >hand, it does take quite a bit more memory than Sriram's version, as >evidenced by MaxMemoryUsed[]. > >3. At least on my version of Mathematica (4.1), Sriram's >version is still >O(n^2) if the permutation is not in a packed array, while my >tocycles is >O(n) with or without packed arrays. > >4. The basic algorithm used by both Sriram and myself are >essentially the >same. I don't understand why Sriram's ToCycles has O(n^2) algorithmic >complexity when working with non packed array permutations. > >5. Finally, inspired by the challenge, I present another tocycles which >seems to be more than twice as fast as Sriram's: > >tocycles[p_] := Block[{np = p}, > If[np[[#]] =!= 0, > tmp = fc[p, #]; > np[[tmp]] = 0; > tmp, > Unevaluated[Sequence[]]] & /@ p] > >fc = Compile[{{p, _Integer, 1}, {i, _Integer}}, > NestWhileList[p[[#]] &, p[[i]], # =!= i &]]; > >Carl Woll >Physics Dept >U of Washington > >----- Original Message ----- >From: "wouter meeussen" <wouter.meeussen at pandora.be> To: mathgroup at smc.vnet.net >To: mathgroup at smc.vnet.net >Subject: [mg41958] [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica > > >> dear Carl, >> >> looked it up, the link is >> www.cs.uiowa.edu/~sriram/Combinatorica/newFeatures.nb.pdf >> tested your 'tocycles' against Sriram's for a RandomPermutation[10^6] >> yours=48.8 s, his=31.8s >> BUT : yours hogs 339 Mb memory and doesn't release it! >> >> btw, a RotateRight is needed to make your cycles equivalent >to Sriram's >> as in : >> >> tocycles[p_] := Block[{f}, >> f[i_] := NestWhileList[p[[f[#1] = Sequence[]; #1]] & , >> p[[i]], #1 =!= i & ];RotateRight/@ (f /@ p)] >> >> >> but it's still a remarkable one-liner, >> a programmer's Haiku, >> a pleasure to work through >> >> Wouter. >> >> >> > > Dear Carl, full of admiration to your 'Haiku', more so, your celebrated UnorderedUnion, which then had struck me like a lightning. However, Daniel Lichtblau had taught me the value of simple, c-style, compiled code, which still is a strong candidate for performance. Here is such a humble piece of code: In[101]:= tc3c = Compile[{{p, _Integer, 1}}, Module[{pa = p, len = Length[p], xp = 1, cc}, cl = c[]; While[xp <= len, cc = NestWhileList[(pa[[#]] = 0; p[[#]]) &, (pa[[xp]] = 0; p[[xp]]), (#1 =!= xp &)]; cl = c[cl, cc]; While[++xp <= len && pa[[xp]] === 0, ]] ]]; In[102]:= tc3bis[p_] := Block[{cl, c}, tc3c[p]; List @@ Flatten[cl, Infinity, c]] It turns out to be faster on my machine by nearly a factor of nine (compared to your last tocycles above). The differences of timing might however change (largely, as we have learnt recently) with different memory bus and cpu architecture. I don't however fully understand yet, where you left time. -- Hartmut ___________ P.S.: I just detected that this, clumsy!, code is still faster (by 20-25%, stronger at very large permutations): In[173]:= tcc = Compile[{{p, _Integer, 1}}, Module[{ca = p, pa = p, xp = 0, xc = 0, xxp, xlp = 0, len = Length[p]}, While[While[++xp <= len && pa[[xp]] === 0,]; xp <= len, ca[[++xc]] = xp; pl = {pl, xc}; xxp = xp; While[(xxp = pa[[xlp = xxp]]) =!= xp, ca[[++xc]] = xxp; pa[[xlp]] = 0]; pa[[xlp]] = 0 ]; ca]]; tc1bis[p_] := Block[{pl = {}, ca}, ca = tcc[p]; pl = Flatten[pl]; Take[ca, #] & /@ Transpose[{pl, Join[Drop[RotateLeft[pl - 1], -1], {Length[p]}]}] ] In fact this was my first idea, now compiled. Avoids NestWhileList, list operations are now only for the pointer collection to take the cycles from the resulting array. We may even use Append for that as the number of cyles grows only very slowly with the length of a _random_ permutation, they are almost derangements! (This code here trys not fade away by an attac from the identity permutation.) But I now got enough for that. Oh, man! Where is all that beauty gone?