Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #5282

Re: A fast way to compare two vectors

From Ray Koopman <koopman@sfu.ca>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: A fast way to compare two vectors
Date 2011-09-29 06:13 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <j6129e$m4j$1@smc.vnet.net> (permalink)
References <j5m44t$ple$1@smc.vnet.net> <j5mt8t$sn8$1@smc.vnet.net>

Show all headers | View raw


On Sep 27, 3:52 pm, Ray Koopman <koop...@sfu.ca> wrote:
> On Sep 26, 1:13 am, Yasha Gindikin <gindi...@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

If each vector is compared to many other vectors then some time
can be saved by doing the setup preprocessing only once, instead of
repeating it for every comparison. The following does all k(k-1)/2
pairwise comparisons of k vectors.

Dimensions[a = Table[Sort@RandomSample[Range[m = 200], n = 100],
{k = 150}]]

{150, 100}

AbsoluteTiming@Dimensions[ u = vcomb @@@ Subsets[a,{2}] ]

{2.074797, {11175, 2}}

AbsoluteTiming@Dimensions[ v = vkom @@@ Subsets[a,{2}] ]

{2.288352, {11175, 2}}

AbsoluteTiming@Dimensions[ p = SparseArray[Automatic, {m}, 0,
{1, {{0, n}, Transpose@{#}}, Range@n}]& /@ a; q = UnitStep[-p];
w = {SparseArray[p[[#1]]*q[[#2]]]/.SparseArray[_,_,_,d_] :> d[[3]],
     SparseArray[p[[#2]]*q[[#1]]]/.SparseArray[_,_,_,d_] :> d[[3]]}&
    @@@ Subsets[Range@k,{2}] ]

{1.369321, {11175, 2}}

SameQ[u, v, w]

True

Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

A fast way to compare two vectors Yasha Gindikin <gindikin@gmail.com> - 2011-09-25 02:37 +0000
  Re: A fast way to compare two vectors "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> - 2011-09-25 09:44 +0000
    Re: A fast way to compare two vectors "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> - 2011-09-26 08:16 +0000
    Re: A fast way to compare two vectors Yasha Gindikin <gindikin@gmail.com> - 2011-09-26 08:19 +0000
    Re: A fast way to compare two vectors "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> - 2011-09-27 00:08 +0000
      Re: A fast way to compare two vectors Yasha Gindikin <gindikin@gmail.com> - 2011-09-28 06:47 +0000
    Re: A fast way to compare two vectors "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> - 2011-09-29 06:14 +0000
  Re: A fast way to compare two vectors Ray Koopman <koopman@sfu.ca> - 2011-09-25 09:46 +0000
    Re: A fast way to compare two vectors Ray Koopman <koopman@sfu.ca> - 2011-09-26 08:16 +0000
    Re: A fast way to compare two vectors Yasha Gindikin <gindikin@gmail.com> - 2011-09-26 08:13 +0000
      Re: A fast way to compare two vectors Ray Koopman <koopman@sfu.ca> - 2011-09-27 22:52 +0000
      Re: A fast way to compare two vectors Ray Koopman <koopman@sfu.ca> - 2011-09-27 10:23 +0000
    Re: A fast way to compare two vectors Ray Koopman <koopman@sfu.ca> - 2011-09-29 06:13 +0000
    Re: A fast way to compare two vectors "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> - 2011-09-30 08:06 +0000
      Re: A fast way to compare two vectors Ray Koopman <koopman@sfu.ca> - 2011-10-01 07:13 +0000
    Re: A fast way to compare two vectors Yasha Gindikin <gindikin@gmail.com> - 2011-10-03 08:22 +0000
      Re: A fast way to compare two vectors Ray Koopman <koopman@sfu.ca> - 2011-10-07 09:09 +0000

csiph-web