MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: A fast way to compare two vectors

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.

  • Prev by Date: Re: HoldForm and Sum
  • Next by Date: Re: Simple fractal
  • Previous by thread: Re: A fast way to compare two vectors
  • Next by thread: Re: A fast way to compare two vectors