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}