Re: Re: O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg42002] 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:57:19 -0400 (EDT)
- References: <8EB1C3634596D6118952006008F711CD02B5FFAA@debis.com>
- Sender: owner-wri-mathgroup at wolfram.com
Hartmut,
Now, to finish off my original topic, all we need to do is find the fastest
FromCycles. The following attempt is about 7 times faster than the
Combinatorica package.
fromcycles[c_]:=Module[{old=Flatten[c],perm},
perm=Range[Length[old]];
perm[[Flatten[RotateRight/@c]]]=old;
perm]
In fact, the above approach can handle (with a small change) the usual cycle
form notation where 1-cycles are omitted.
Now, we can compose two permutations in cycle form extremely quickly by
using tc1x0 and fromcycles.
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: [mg42002] RE: [mg41915] Re: O(n^2) complexity of ToCycles in Combinatorica
> Carl,
>
> thank you for that remark. This is was due to a last minute try to squeeze
> out the last drop. (Alas! by principle, never do so!) I even had a bad
> feeling about doing so anyhow, i.e. had I left off the necessary checks,
> hurry and greed!
>
> My prior version copied the input p to a local pa and worked with that.
It's
> only minute slower:
>
>
> In[3]:=
> tc1x0c = Compile[{{p, _Integer, 1}},
> Module[{ca = p, pa = p, ppa = p, xp = 0, xc = 0, xxp = 0, xppa = 0,
> xlp = 0, len = Length[p]},
> While[While[++xp <= len && pa[[xp]] === 0,];
> xp <= len,
> ca[[++xc]] = xp;
> ppa[[++xppa]] = xc;
> xxp = xp;
>
> While[(xxp = pa[[xlp = xxp]]) =!= xp, ca[[++xc]] = xxp;
> pa[[xlp]] = 0]; pa[[xlp]] = 0
> ];
> n = xppa;
> {ca, ppa}]];
>
> The idea is: not to use any List constructions. 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 of that length (needed for the identity permutation). The
valid
> length of that is returned via a global variable.
>
> pa is a copy of the permutation, where all used values are being marked
off
> in the course of the calculation.
>
> In[4]:=
> tc1x0[p_] := Block[{n, ca, ppa, res},
> res = tc1x0c[p];
> ppa = Take[res[[2]], n];
> Block[{Take}, Thread[Take[res[[1]], #], List, -1]] &@
> Transpose[{ppa, (Drop[ppa, 1] - 1)~Join~{Length[p]}}]
> ]
>
> In[47]:=
> p0 = p1000000;
> Scan[Print[Timing[#[p0]][[1]], ": ", ToString[#]] &, {tc1x0, tc1x}]
> >From In[47]:= 5.268 Second": "tc1x0"
> >From In[47]:= 5.207 Second": "tc1x"
>
>
>
> In[51]:=
> p0 = Range[100000];
> Scan[Print[Timing[#[p0]][[1]], ": ", ToString[#]] &, {tc1x0, tc1x}]
> >From In[51]:= 2.584 Second": "tc1x0"
> >From In[51]:= 2.763 Second": "tc1x"
>
>
> --
> Hartmut
>
>
>
>
> >-----Original Message-----
> >From: Carl K. Woll [mailto:carlw at u.washington.edu]
To: mathgroup at smc.vnet.net
> >Sent: Thursday, June 12, 2003 4:25 PM
> >To: Wolf, Hartmut
> >Subject: [mg42002] Re: [mg41915] Re: O(n^2) complexity of ToCycles in
> >Combinatorica
> >
> >
> >Hartmut,
> >
> >Only a comment. Your tc1x overwrites its input so that it
> >can't be run twice
> >in a row. For example,
> >
> >perm=Range[10];
> >tc1x[perm]
> >tc1x[perm]
> >
> >produces a bunch of error messages.
> >
> >Carl Woll
> >Physics Dept
> >U of Washington
> >
> [...]
>