Re: more on vector unions
- To: mathgroup at smc.vnet.net
- Subject: [mg23308] Re: [mg23236] more on vector unions
- From: Carl Woll <carlw at u.washington.edu>
- Date: Mon, 1 May 2000 18:00:10 -0400 (EDT)
- References: <200004300204.WAA16567@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Russell,
Russell Towle wrote:
> Initial tests of this vunion1 function suggest that it is not only accurate
> but very fast; it found the union of a list of 8448 3-vectors in 2.95
> seconds. However, I myself believe it should be modified to Sort a Chop-ped
> list:
>
> >vunion1[v_] := Module[{r},
> > r = Split[Sort[ Chop[v, .000001] ], (Abs[#1[[1]] - #2[[1]]] < tol &)];
> > Flatten[vunion /@ r, 1]]
>
> I think this is crucial, because a typical list of vectors (vertices of
> polytopes, actually) with many duplicates will have many components close
> to zero--which actually should be zero--but which differ in sign. Chop
> fixes this and Sort proceeds as it should... right?
The additional Chop that you suggest is not necessary.
By the way, I have come up with a minor speed up (25%):
tst = splitQ[[i++]] &;
vunion3[v_] := Block[{i, splitQ, r1, r2},
r1 = Sort[v];
r2 = r1[[All, 1]];
splitQ = Thread[Abs[Drop[r2, -1] - Rest[r2]] < tol];
i = 1;
r2 = Split[r1, tst];
Join @@ (vunion /@ r2)]
Basically, splitQ stores up all the test results first, then when the Split
function is run, h spits those results back out. This is faster because the
complicated tests can then be vectorized as opposed to being performed
piecemeal. Another refinement is using Join@@ instead of Flatten[ ,1], which as
Allan Hayes pointed out in a different context is slightly faster.
Carl