RE: Re: O(n^2) complexity of ToCycles in Combinatorica
- To: mathgroup at smc.vnet.net
- Subject: [mg42001] 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:13 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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: [mg42001] 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
>
[...]