Re: A fast way to compare two vectors
- To: mathgroup at smc.vnet.net
- Subject: [mg121976] Re: A fast way to compare two vectors
- From: Ray Koopman <koopman at sfu.ca>
- Date: Fri, 7 Oct 2011 04:51:23 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <j5m44t$ple$1@smc.vnet.net> <j5mt8t$sn8$1@smc.vnet.net> <j6brc0$8it$1@smc.vnet.net>
On Oct 3, 1:22 am, Yasha Gindikin <gindi... at gmail.com> wrote:
> First of all, let me thank both of my interlocutors for being
> extremely helpful (and also amicable).
>
>> I don't know what range of values of n and M the OP is working with
>
> I would say, n<20 and M<3n.
> As a typical example, let's consider the following:
>
> a = Subsets[Range[12], {6}];
> Q = Dimensions[a][[1]]
> AbsoluteTiming[Do[quick_compare_function[a[[p1]], a[[p2]]],
> {p1, Q}, {p2, Q}]].
>
> The system is Mathematica 8.0.1 running on desktop Linux x86_64,
> the compile option is "CompilationTarget" -> "C" (gcc 4.5 used).
>
> For such a setup, I get
>
> compare gives 25.16 sec
>
> poscom gives 25.43 sec
>
> poskom gives 49.55 sec
>
> vcomb gives 4.59 sec
>
> vkom gives 66.06 sec.
>
> The winner is vcomb, which turns out to be a real treasure. It's
> perfectly OK that it returns all the differences. The number of
> diffs was checked in the procedure to be <=4 only in the hope to
> speed-up the calculations (avoiding unnecessary comparisons);
> however, without these checks, the function is even faster.
>
>> In any case, the parallelization speedup in vcomc is impressive
>> and will be hard to beat.
>
> Actually, I'm planning to utilize CUDA for the parallelization.
> Hope the structure of the vcomb function allows for a transition
> to a GPU.
I thought this topic was finally wound up, but then I started
wondering if bags were really necessary for such short vectors.
vcoma is a bagless version of vcomb.
vcoma = Compile[{{v1, _Integer, 1}, {v2, _Integer, 1}},
Block[{i1 = 1, i2 = 1, k1 = 0, k2 = 0, n = Length@v1,
d1 = Table[0,{Length@v1}],
d2 = Table[0,{Length@v1}]},
(* Run along the lists, recording differences as we go *)
While[i1 <= n && i2 <= n,
Which[v1[[i1]] < v2[[i2]], d1[[++k1]] = i1++,
v1[[i1]] > v2[[i2]], d2[[++k2]] = i2++,
True , i1++; i2++ ] ];
(* Fix up in case we ran off the end of one of the lists *)
Which[k1 < k2, {Join[Take[d1,k1],Range[i1,n]], Take[d2,k2]},
k1 > k2, {Take[d1,k1], Join[Take[d2,k2],Range[i2,n]]},
True , {Take[d1,k1], Take[d2,k2]}] ] ];
Here are times for versions 5.2 and 6. (ranperk[m,n] in 5.2
is equivalent to RandomSample[Range@m,n] in 6.) Bags are needed
only for n = 20 in 5.2, and not at all in 6. Of course, YMMV in 8.
With[{k = 400}, Flatten[Table[{n,m,k, Timing[ (* v5.2 *)
a = Table[Sort@ranperk[m,n],{k}]; Do[Null,{1*^7}]];
First@Timing@Do[vcomb[a[[i]],a[[j]]],{i,k},{j,k}],
First@Timing@Do[vcoma[a[[i]],a[[j]]],{i,k},{j,k}]},
{n,8,20,4},{m,2n,3n,4}],1]] /. Second->1 //ColumnForm
{ 8, 16, 400, 4.89, 4.36}
{ 8, 20, 400, 4.91, 4.46}
{ 8, 24, 400, 5.01, 4.60}
{12, 24, 400, 5.79, 5.46}
{12, 28, 400, 5.88, 5.63}
{12, 32, 400, 5.92, 5.72}
{12, 36, 400, 5.97, 5.79}
{16, 32, 400, 6.74, 6.64}
{16, 36, 400, 6.78, 6.78}
{16, 40, 400, 6.88, 6.87}
{16, 44, 400, 6.94, 6.94}
{16, 48, 400, 7.07, 7.03}
{20, 40, 400, 7.68, 7.83}
{20, 44, 400, 7.73, 7.90}
{20, 48, 400, 7.87, 7.99}
{20, 52, 400, 7.91, 8.13}
{20, 56, 400, 7.97, 8.20}
{20, 60, 400, 8.04, 8.29}
With[{k = 400}, Flatten[Table[{n,m,k, Timing[ (* v6 *)
a = Table[Sort@RandomSample[Range@m,n],{k}]; Do[Null,{1*^7}]];
First@Timing@Do[vcomb[a[[i]],a[[j]]],{i,k},{j,k}],
First@Timing@Do[vcoma[a[[i]],a[[j]]],{i,k},{j,k}]},
{n,8,20,4},{m,2n,3n,4}],1]] //ColumnForm
{ 8, 16, 400, 5.62, 4.88}
{ 8, 20, 400, 5.60, 4.95}
{ 8, 24, 400, 5.72, 5.01}
{12, 24, 400, 6.51, 5.94}
{12, 28, 400, 6.56, 5.99}
{12, 32, 400, 6.62, 6.09}
{12, 36, 400, 6.73, 6.18}
{16, 32, 400, 7.35, 6.93}
{16, 36, 400, 7.49, 6.96}
{16, 40, 400, 7.42, 7.07}
{16, 44, 400, 7.58, 7.17}
{16, 48, 400, 7.65, 7.28}
{20, 40, 400, 8.35, 7.88}
{20, 44, 400, 8.40, 8.03}
{20, 48, 400, 8.58, 8.19}
{20, 52, 400, 8.65, 8.21}
{20, 56, 400, 8.69, 8.34}
{20, 60, 400, 8.68, 8.35}