Re: Re: O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg41992] Re: [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica
- From: "Carl K. Woll" <carlw at u.washington.edu>
- Date: Mon, 16 Jun 2003 03:56:49 -0400 (EDT)
- References: <8EB1C3634596D6118952006008F711CD02B5FFA5@debis.com>
- Sender: owner-wri-mathgroup at wolfram.com
Hartmut, Good work getting Compile to handle this problem. Interestingly enough, on my machine, your tc3bis is 5 times as fast as my tocycles when working with packed arrays, and 9 times as fast when working with nonpacked arrays. On the other hand, when working with the identity permutation, my tocycles is actually 15% faster than your tc1bis, and your tc3bis is completely inadequate. It seems that the shenanigans you go through to coerce Compile to handle this problem are worthwhile when there are not too many cycles, but tocycles becomes competitive when there are many cycles. Since your tc1bis appears to be messy, it may be possible to streamline it so that tc1bis is better than tocycles even for the identity permutation. Carl Woll Physics Dept U of Washington ----- Original Message ----- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com> To: mathgroup at smc.vnet.net Subject: [mg41992] RE: [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica > > >-----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: [mg41992] [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: [mg41992] [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? >