Vector Union
- To: mathgroup at smc.vnet.net
- Subject: [mg23117] Vector Union
- From: Russell Towle <rustybel at foothill.net>
- Date: Wed, 19 Apr 2000 02:30:48 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
The problem of finding a function to return the union of a list of
n-vectors which is at once *fast* and yet *unfailing* has beguiled me for
several years. I contrived a slow but unfailing 'vunion' function about
five years ago; made a not-so-slow and unfailing version a year ago; and
then found it to occasionally fail when Chop was applied to the vectors
without a second argument.
I posed a programming challenge to the Group a few days ago: make a fast
and unfailing vector union function. David Park and Michael Trott were kind
enough to respond, for which I thank them very much. Around a year around
Martin Kraus also supplied a vector union function.
Good solutions seem to hinge upon *sorting the list of n-vectors*.
Searching the internet, I find that sorting a list of vectors seems to be a
classic problem in computer science. This is where Chop comes into play: to
compare one vector to another, when the components are machine precision,
is easier when very small numbers with opposite signs are Chopped to zero.
My function, slow but sure:
vunion[v_] :=
Union[Chop[v, .000001],
SameTest -> (Sign[#1] == Sign[#2] &&
Chop[#1 - #2, .000001] == Table[0, {Length[v[[1]]]}] & )]
David Park appealed to an "UnorderUnion" function devised by Carl Woll,
which works well on lists with integer and symbolic components. Park uses
Round to put the machine numbers into a form acceptable to UnorderUnion.
The implications of using Round worry me, but Park's method has not failed
yet, given inputs which made most other methods fail. His function is
around twenty times faster than mine. Thanks David!!
(*modified Woll*)
OrderedUnion2[li_] :=
Block[{i}, i[n_] := (i[n] = Null; n);
i /@ li]
vunion2[v_] :=
Block[{accuracylist, v2},
accuracylist = OrderedUnion2[Round[10^5*(v2 = Sort[Chop[v, .000001]])]];
Do[If[accuracylist[[i]] === Null, v2[[i]] = Null], {i, Length[v2]}];
v2 /. Null -> Sequence[]]
Russell Towle
Box 141
Dutch Flat, CA 95714
(530) 389-2872
- Follow-Ups:
- Re: Vector Union
- From: Hartmut Wolf <hwolf@debis.com>
- Re: Vector Union