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


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

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-10-01 07:13 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <j66ejg$hft$1@smc.vnet.net> (permalink)
References <j5m44t$ple$1@smc.vnet.net> <j5mt8t$sn8$1@smc.vnet.net> <j63taq$6g3$1@smc.vnet.net>

Show all headers | View raw


On Sep 30, 1:06 am, "Oleksandr Rasputinov"
<oleksandr_rasputi...@hmamail.com> wrote:
> On Tue, 27 Sep 2011 23:52:36 +0100, 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
>
> These timings seem to be system-dependent, as I observe vcomb to be about
> twice as fast as vkom for any length of list on Windows, with no apparent
> differences between Mathematica 5.2, 7.0.1, and 8.0.1. Nonetheless it may
> be the case that invoking a CompiledFunction incurs considerably more
> overhead on other platforms and so for relatively short vectors vkom would
> be faster as shown by your results. If we restrict ourselves to version 8,
> inputs of the particular form used here can be processed more quickly
> still by taking advantage of CompiledFunction auto-parallelization:
>
> vcomc = Compile[{{m, _Integer, 2}},
>      Block[{v1 = m[[1]], v2 = m[[2]],
>             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]} ],
>      RuntimeAttributes -> {Listable} ] ;
>
> For the same definition of ab given above, on my system:
>
> AbsoluteTiming[u = vcomb @@@ ab;]
>
> {0.4531250, Null}
>
> AbsoluteTiming[v = vkom @@@ ab;]
>
> {0.8281250, Null}
>
> AbsoluteTiming[w = vcomc[ab];]
>
> {0.1406250, Null}
>
> u === v === w
>
> True

The times I gave were with v6 on a Mac G5. By "data configuration" I
meant the parameters of the data-generating process: two independent
vectors of length n = 100, with elements taken equiprobably without
replacement from 1 to M = 200. With n = 200, M = 400, I get

ab = Table[Sort@RandomSample[Range@400,200],{1*^4},{2}];

AbsoluteTiming[u = vcomb @@@ ab;]

{3.485911, Null}

AbsoluteTiming[v = Apply[vkom, ab, {1}]; ]

{2.400956, Null}

u === v

True

I don't know what range of values of n and M the OP is working with,
or if independence is reasonable in his problem -- with independence,
the expected proportion of matches is n/M -- or if the considerations
I mentioned in my Sep 28 post apply. In any case, the parallelization
speedup in vcomc is impressive and will be hard to beat.

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