Re: A fast way to compare two vectors
- To: mathgroup at smc.vnet.net
- Subject: [mg121797] Re: A fast way to compare two vectors
- From: Yasha Gindikin <gindikin at gmail.com>
- Date: Mon, 3 Oct 2011 04:20:38 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <j5m44t$ple$1@smc.vnet.net> <j5mt8t$sn8$1@smc.vnet.net>
- Reply-to: comp.soft-sys.math.mathematica at googlegroups.com
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.