Re: A fast way to compare two vectors

*To*: mathgroup at smc.vnet.net*Subject*: [mg121723] Re: A fast way to compare two vectors*From*: Ray Koopman <koopman at sfu.ca>*Date*: Tue, 27 Sep 2011 06:21:57 -0400 (EDT)*Delivered-to*: l-mathgroup@mail-archive0.wolfram.com*References*: <j5m44t$ple$1@smc.vnet.net> <j5mt8t$sn8$1@smc.vnet.net> <j5pc7f$8c8$1@smc.vnet.net>

On Sep 26, 1:13 am, Yasha Gindikin <gindi... at gmail.com> wrote: > Alas, there was a misprint in my code, I'm terribly sorry > about that. The length of the intersection R should be >=n-2, > where n is the length of the vector a[[p]]. Thank you so much > for your realization of the poscom function, I'll explore the > performance gain and report here.:) vcomb is a version of hyperfastVectorCompareBag that always returns all the differences vcomb = Compile[{{v1, _Integer, 1}, {v2, _Integer, 1}}, Block[{i1 = 1, i2 = 1, d1 = Internal`Bag@Most[{0}], d2 = Internal`Bag@Most[{0}]}, (* Run along the lists, recording differences as we go *) While[i1 <= Length[v1] && i2 <= Length[v2], Which[v1[[i1]] < v2[[i2]], Internal`StuffBag[d1, i1]; i1++, v1[[i1]] > v2[[i2]], Internal`StuffBag[d2, i2]; i2++, True , i1++; i2++ ]]; (* Fix up in case we ran off the end of one of the lists *) While[i1 <= Length[v1], Internal`StuffBag[d1, i1]; i1++]; While[i2 <= Length[v2], Internal`StuffBag[d2, i2]; i2++]; {Internal`BagPart[d1, All], Internal`BagPart[d2, All]} ] ] ; vkom is a merged version of two poskom's that also returns all the differences vkom[a_,b_] := Block[{ r = SparseArray[ Automatic, {Max[a[[-1]],b[[-1]]]}, 0, {1, {{0, Length@a}, Transpose@{a}}, Range@Length@a} ], s = SparseArray[ Automatic, {Max[a[[-1]],b[[-1]]]}, 0, {1, {{0, Length@b}, Transpose@{b}}, Range@Length@b} ]}, r[[b]] = ConstantArray[0,Length@b]; s[[a]] = ConstantArray[0,Length@a]; {r /. SparseArray[_,_,_,d_] :> d[[3]], s /. SparseArray[_,_,_,d_] :> d[[3]]}] This is one of the approximate break-even data configurations ab = Table[Sort@RandomSample[Range@200,100],{1*^4},{2}]; AbsoluteTiming[u = vcomb @@@ ab;] {2.202807, Null} AbsoluteTiming[v = vkom @@@ ab;] {2.101078, Null} u === v True