RE: Re: O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg41998] RE: [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Mon, 16 Jun 2003 03:57:05 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Carl, >-----Original Message----- >From: Carl K. Woll [mailto:carlw at u.washington.edu] To: mathgroup at smc.vnet.net >Sent: Thursday, June 12, 2003 6:50 AM >To: Wolf, Hartmut; mathgroup at smc.vnet.net >Subject: [mg41998] Re: [mg41915] Re: O(n^2) complexity of ToCycles in >Combinatorica > > >Hartmut, > >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. > My timings are a bit different, and I had suspected so from past experience. (If I only knew exactly why/how!) >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. > Not per se compiling, but passing the cycle information, see below! >Carl Woll >Physics Dept >U of Washington > >----- Original Message ----- >From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com> To: mathgroup at smc.vnet.net >To: "'Carl K. Woll'" <carlw at u.washington.edu>; <mathgroup at smc.vnet.net> >Sent: Wednesday, June 11, 2003 5:49 AM >Subject: [mg41998] 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: [mg41998] [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: [mg41998] [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 & ]; >> >> f /@ p] I deleted that RotateRight, to restore the original version (see your remark 1. above) >> >> >> >> >> >> but it's still a remarkable one-liner, >> >> a programmer's Haiku, >> >> a pleasure to work through >> >> >> >> Wouter. >> >> >> >> >> >> >> > >> > [...] >> >> 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 tries not to fade away by an attack from the >> identity permutation.) [...] Here now a small modification of tc1bis, that avoids the penalty from the identity permutation: In[64]:= tc1xc = Compile[{{p, _Integer, 1}}, Module[{ca = p, ppa = p, xp = 0, xc = 0, xxp = 0, xppa = 0, xlp = 0, len = Length[p]}, While[While[++xp <= len && p[[xp]] === 0,]; xp <= len, ca[[++xc]] = xp; ppa[[++xppa]] = xc; xxp = xp; While[(xxp = p[[xlp = xxp]]) =!= xp, ca[[++xc]] = xxp; p[[xlp]] = 0]; p[[xlp]] = 0 ]; n = xppa; {ca, ppa}]]; The idea is: not to use any List constructors. The cycles are returned in an array, ca, however as a flat structure (of same length as the permutation p). Therefore the beginning indices for each cycle are also returned, again in an array ppa of that length (full length needed for the identity permutation). The valid length of that is returned via a global variable, n. The values used, are being marked off in the permutation during the course of the calculation. In[48]:= tc1x[p_] := Block[{n, ppa, res}, res = tc1xc[p]; ppa = Take[res[[2]], n]; Block[{Take}, Thread[Take[res[[1]], #], List, -1]] &@ Transpose[{ppa, (Drop[ppa, 1] - 1)~Join~{Length[p]}}] ] My Timings: In[70]:= p0 = p100000; Scan[Print[Timing[#[p0]][[1]], ": ", ToString[#]] &, {tocycles, tc3bis, tc1bis, tc1x}] >From In[70]:= 4.907 Secon: "tocycles" >From In[70]:= 0.531 Second: "tc3bis" >From In[70]:= 0.49 Second: "tc1bis" >From In[70]:= 0.461 Second: "tc1x" In[74]:= p0 = Developer`ToPackedArray[p100000]; Scan[Print[Timing[#[p0]][[1]], ": ", ToString[#]] &, {tocycles, tc3bis, tc1bis, tc1x}] >From In[74]:= 3.505 Second: "tocycles" >From In[74]:= 0.5 Second: "tc3bis" >From In[74]:= 0.471 Second: "tc1bis" >From In[74]:= 0.451 Second: "tc1x" My programs receive no big grants from packed arrays (which should not surprise). Identity permutation In[78]:= p0 = Range[100000]; Scan[Print[Timing[#[p0]][[1]], ": ", ToString[#]] &, {tocycles, "not timed tc3bis" &, tc1bis, tc1x}] >From In[78]:= 13.84 Second: "tocycles" >From In[78]:= 0. Second: "not timed tc3bis & " >From In[78]:= 14.341 Second: "tc1bis" >From In[78]:= 2.263 Second: "tc1x" This is the advantage of the new interface for the cycle pointers. In[80]:= Developer`PackedArrayQ[p0] Out[80]= True -- Hartmut