Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #5194 > unrolled thread
| Started by | Yasha Gindikin <gindikin@gmail.com> |
|---|---|
| First post | 2011-09-25 02:37 +0000 |
| Last post | 2011-10-07 09:09 +0000 |
| Articles | 17 — 3 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
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
| From | Yasha Gindikin <gindikin@gmail.com> |
|---|---|
| Date | 2011-09-25 02:37 +0000 |
| Subject | A fast way to compare two vectors |
| Message-ID | <j5m44t$ple$1@smc.vnet.net> |
I'm looking for a hyper-fast way to compare two vectors using Mathematica built-in functions. The problem arises in the calculation of the Hamiltonian matrix elements of a many-particle quantum system.
Consider two rows of equal length n, a[[p1] and a[[p2]]. Their elements are integers from 1 to M, put in an increasing order, without repeats. E.g., a[[p1]]={1,2,3,6,7,9} and a[[p2]]={1,2,4,7,8,9}. I need to find the number of different elements (4 in the example) and, if this number is less or equal to 4, their positions ((3,4) and (3,5) in the example). The simplest way looks like this:
diff = Intersection[a[[p1]], a[[p2]]];
R = Dimensions[diff][[1]];
If[R<5,d1 = Complement[a[[p1]], diff];
d2 = Complement[a[[p2]], diff];
k1 = Position[a[[p1]], d1[[1]]]; k2 = Position[a[[p1]], d1[[2]]];
k3 = Position[a[[p2]], d2[[1]]]; k4 = Position[a[[p2]], d2[[2]]]];
This is slow, since four search operations are used (and because the ordering of the elements is not taken advantage of). Is there a built-in function that quickly finds the differences between the two vectors?
Thank you.
Regards,
Yasha.
[toc] | [next] | [standalone]
| From | "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> |
|---|---|
| Date | 2011-09-25 09:44 +0000 |
| Message-ID | <j5mt5u$smm$1@smc.vnet.net> |
| In reply to | #5194 |
On Sun, 25 Sep 2011 03:37:17 +0100, Yasha Gindikin <gindikin@gmail.com>
wrote:
> I'm looking for a hyper-fast way to compare two vectors using
> Mathematica built-in functions. The problem arises in the calculation of
> the Hamiltonian matrix elements of a many-particle quantum system.
>
> Consider two rows of equal length n, a[[p1] and a[[p2]]. Their elements
> are integers from 1 to M, put in an increasing order, without repeats.
> E.g., a[[p1]]={1,2,3,6,7,9} and a[[p2]]={1,2,4,7,8,9}. I need to find
> the number of different elements (4 in the example) and, if this number
> is less or equal to 4, their positions ((3,4) and (3,5) in the example).
> The simplest way looks like this:
>
> diff = Intersection[a[[p1]], a[[p2]]];
> R = Dimensions[diff][[1]];
> If[R<5,d1 = Complement[a[[p1]], diff];
> d2 = Complement[a[[p2]], diff];
> k1 = Position[a[[p1]], d1[[1]]]; k2 = Position[a[[p1]], d1[[2]]];
> k3 = Position[a[[p2]], d2[[1]]]; k4 = Position[a[[p2]], d2[[2]]]];
>
> This is slow, since four search operations are used (and because the
> ordering of the elements is not taken advantage of). Is there a built-in
> function that quickly finds the differences between the two vectors?
>
> Thank you.
> Regards,
> Yasha.
>
No. But you can achieve high performance with a hand-coded implementation
specific to the problem at hand.
Firstly, a few operations in your given code are redundant. Removing these
and instituting a little good programming practice it becomes
vectorCompare = Function[
{vec1, vec2, MAXDIFFS},
Block[{
d1 = Complement[vec1, vec2], d2 = Complement[vec2, vec1],
k1, k2
},
If[Length[d1] + Length[d2] <= MAXDIFFS,
k1 = Flatten@Position[vec1, Alternatives @@ d1];
k2 = Flatten@Position[vec2, Alternatives @@ d2]
];
{k1, k2}
]
];
which is called as vectorCompare[a[[p1]], a[[p2]], 4], giving {{3, 4}, {3,
5}} as we expect.
But this is not where the big gains lie, since this problem can be
attacked very efficiently in procedural code. Such code can even be
compiled (from C, if necessary), in which case you will obtain the desired
high performance:
hyperfastVectorCompare = Compile[{
{vec1, _Integer, 1}, {vec2, _Integer, 1},
{MAXDIFFS, _Integer, 0}
},
Block[{
i1 = 1, i2 = 1,
diffct = 0,
diffs1 = Most[{0}], diffs2 = Most[{0}]
},
(* Run along the lists, recording differences as we go *)
While[
i1 <= Length[vec1] && i2 <= Length[vec2] && diffct < MAXDIFFS,
Which[
vec1[[i1]] == vec2[[i2]], i1++; i2++,
vec1[[i1]] < vec2[[i2]], diffct++; AppendTo[diffs1, i1]; i1++,
vec1[[i1]] > vec2[[i2]], diffct++; AppendTo[diffs2, i2]; i2++
]
];
(* Fix up in case we ran off the end of one of the lists *)
While[i1 <= Length[vec1] && diffct < MAXDIFFS,
diffct++; AppendTo[diffs1, i1]; i1++
];
While[i2 <= Length[vec2] && diffct < MAXDIFFS,
diffct++; AppendTo[diffs2, i2]; i2++
];
{diffs1, diffs2}
]
];
naturally, hyperfastVectorCompare[a[[p1]], a[[p2]], 4] also gives {{3, 4},
{3, 5}} for your inputs, but traverses the vectors only once and takes
advantage of the ordering of the elements. Note that if you choose
MAXDIFFS to be odd and less than the actual number of differences the
compiled code will throw an error due to {diffs1, diffs2} not being a
full-rank tensor; this can be avoided by passing diffs1 and diffs2 out
separately but I have not bothered with it here since requesting an odd
number of differences seemed to me inherently ill-defined and as such a
rather unlikely corner case. If you need the number of differences
explicitly, you can either pass this out separately as well or otherwise
just count the number of elements in the returned list of positions.
If you need higher performance still, AppendTo is the prime candidate for
replacement since it copies the entire accumulated list of differences on
every call. However, I doubt that this will present much of a limitation
in practice unless you have very long vectors with a large number of
differences.
Best,
O. R.
[toc] | [prev] | [next] | [standalone]
| From | "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> |
|---|---|
| Date | 2011-09-26 08:16 +0000 |
| Message-ID | <j5pcda$8gf$1@smc.vnet.net> |
| In reply to | #5203 |
On Sun, 25 Sep 2011 10:44:30 +0100, Oleksandr Rasputinov
<oleksandr_rasputinov@hmamail.com> wrote:
> On Sun, 25 Sep 2011 03:37:17 +0100, Yasha Gindikin <gindikin@gmail.com>
> wrote:
>
>> I'm looking for a hyper-fast way to compare two vectors using
>> Mathematica built-in functions. The problem arises in the calculation of
>> the Hamiltonian matrix elements of a many-particle quantum system.
>>
>> Consider two rows of equal length n, a[[p1] and a[[p2]]. Their elements
>> are integers from 1 to M, put in an increasing order, without repeats.
>> E.g., a[[p1]]={1,2,3,6,7,9} and a[[p2]]={1,2,4,7,8,9}. I need to find
>> the number of different elements (4 in the example) and, if this number
>> is less or equal to 4, their positions ((3,4) and (3,5) in the example).
>> The simplest way looks like this:
>>
>> diff = Intersection[a[[p1]], a[[p2]]];
>> R = Dimensions[diff][[1]];
>> If[R<5,d1 = Complement[a[[p1]], diff];
>> d2 = Complement[a[[p2]], diff];
>> k1 = Position[a[[p1]], d1[[1]]]; k2 = Position[a[[p1]], d1[[2]]];
>> k3 = Position[a[[p2]], d2[[1]]]; k4 = Position[a[[p2]], d2[[2]]]];
>>
>> This is slow, since four search operations are used (and because the
>> ordering of the elements is not taken advantage of). Is there a built-in
>> function that quickly finds the differences between the two vectors?
>>
>> Thank you.
>> Regards,
>> Yasha.
>>
>
> If you need higher performance still, AppendTo is the prime candidate for
> replacement since it copies the entire accumulated list of differences on
> every call. However, I doubt that this will present much of a limitation
> in practice unless you have very long vectors with a large number of
> differences.
>
In fact, having just read Daniel Lichtblau's description of the
undocumented internal functions for manipulating expression bags (see
http://stackoverflow.com/questions/6691491/implementing-a-quadtree-in-mathematica),
it is clear that bags are an ideal (and utterly trivial) substitute for
AppendTo in this case:
hyperfastVectorCompareBag = Compile[{
{vec1, _Integer, 1}, {vec2, _Integer, 1},
{MAXDIFFS, _Integer, 0}
},
Block[{
i1 = 1, i2 = 1,
diffct = 0,
diffs1 = Internal`Bag@Most[{0}], diffs2 = Internal`Bag@Most[{0}]
},
(* Run along the lists, recording differences as we go *)
While[
i1 <= Length[vec1] && i2 <= Length[vec2] && diffct < MAXDIFFS,
Which[
vec1[[i1]] == vec2[[i2]], i1++; i2++,
vec1[[i1]] < vec2[[i2]], diffct++; Internal`StuffBag[diffs1, i1]; i1++,
vec1[[i1]] > vec2[[i2]], diffct++; Internal`StuffBag[diffs2, i2]; i2++
]
];
(* Fix up in case we ran off the end of one of the lists *)
While[i1 <= Length[vec1] && diffct < MAXDIFFS,
diffct++; Internal`StuffBag[diffs1, i1]; i1++
];
While[i2 <= Length[vec2] && diffct < MAXDIFFS,
diffct++; Internal`StuffBag[diffs2, i2]; i2++
];
{Internal`BagPart[diffs1, All], Internal`BagPart[diffs2, All]}
]
];
This version is extremely fast. Using your test vectors,
vec1 = {1, 2, 3, 6, 7, 9};
vec2 = {1, 2, 4, 7, 8, 9};
but expanded a little (to give about 100,000 elements/400KB per vector)
using
Do[
vec1 = Join[vec1, vec1 + Max[vec1]];
vec2 = Join[vec2, vec2 + Max[vec2]],
{14}
];
we get:
Version Run time /s
vectorCompare 92.36
hyperfastVectorCompare 1.375
hyperfastVectorCompareBag 0.031
More gains are available by translating to C ("CompilationTarget" -> "C")
and compiling down into native code. Expanding the inputs a little more
(to over 200 million elements/800MB per vector), we obtain:
Version Run time /s
hyperfastVectorCompareBag (MVM) 55.59
hyperfastVectorCompareBag (C) 8.578
which in my opinion is not too bad at all considering that this code is
single-threaded and written wholly in the Mathematica language.
[toc] | [prev] | [next] | [standalone]
| From | Yasha Gindikin <gindikin@gmail.com> |
|---|---|
| Date | 2011-09-26 08:19 +0000 |
| Message-ID | <j5pci6$8hb$1@smc.vnet.net> |
| In reply to | #5203 |
Dear Oleksandr, thank you very much for your code. Actually, I was trying to implement the same algorithm. My code was the following:
Compare := Compile[{{a, _Integer, 1}, {b, _Integer, 1}},
{s1 = s2 = 0; k = n; d1 = d2 = Table[0, {k, 3}];
While[s1 < 3 && s2 < 3 && k - s1 > 0 && k - s2 > 0,
Which[a[[k - s1]] > b[[k - s2]], d1[[s1 + 1]] = a[[k - s1]]; s1++,
a[[k - s1]] < b[[k - s2]], d2[[s2 + 1]] = b[[k - s2]]; s2++,
a[[k - s1]] == b[[k - s2]], k--]]; Cm = Max[{s1, s2}];
Which[Cm > 2, False, s1 - s2 == 1, d2[[s1]] = b[[1]],
s2 - s1 == 1, d1[[s2]] = a[[1]], s1 - s2 == 2, d2[[1]] = b[[2]];
d2[[2]] = b[[1]], s2 - s1 == 2, d1[[1]] = a[[2]];
d1[[2]] = a[[1]]]; Cm}];
But due to my very limited programming experience, the code turned out to be not very efficient. It even works faster without the Compile option, which puzzles me a lot. I will try to use your realization instead. Thank you once again!
Regards,
Yasha.
[toc] | [prev] | [next] | [standalone]
| From | "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> |
|---|---|
| Date | 2011-09-27 00:08 +0000 |
| Message-ID | <j5r46e$ibt$1@smc.vnet.net> |
| In reply to | #5203 |
On Mon, 26 Sep 2011 09:19:18 +0100, Yasha Gindikin <gindikin@gmail.com>
wrote:
> Dear Oleksandr, thank you very much for your code. Actually, I was
> trying to implement the same algorithm. My code was the following:
>
> Compare := Compile[{{a, _Integer, 1}, {b, _Integer, 1}},
> {s1 = s2 = 0; k = n; d1 = d2 = Table[0, {k, 3}];
> While[s1 < 3 && s2 < 3 && k - s1 > 0 && k - s2 > 0,
> Which[a[[k - s1]] > b[[k - s2]], d1[[s1 + 1]] = a[[k - s1]]; s1++,
> a[[k - s1]] < b[[k - s2]], d2[[s2 + 1]] = b[[k - s2]]; s2++,
> a[[k - s1]] == b[[k - s2]], k--]]; Cm = Max[{s1, s2}];
> Which[Cm > 2, False, s1 - s2 == 1, d2[[s1]] = b[[1]],
> s2 - s1 == 1, d1[[s2]] = a[[1]], s1 - s2 == 2, d2[[1]] = b[[2]];
> d2[[2]] = b[[1]], s2 - s1 == 2, d1[[1]] = a[[2]];
> d1[[2]] = a[[1]]]; Cm}];
>
> But due to my very limited programming experience, the code turned out
> to be not very efficient. It even works faster without the Compile
> option, which puzzles me a lot. I will try to use your realization
> instead. Thank you once again!
>
> Regards,
> Yasha.
>
Dear Yasha
The above example is slow for two reasons. The first is that SetDelayed
(:=) is used instead of Set (=) in the definition. This means that the
code is unnecessarily compiled afresh every time it is used. The second
reason is that many of the values are not localised to the compiled code
and such values are dealt with via Mathematica's interpreter. These
problems can be addressed without changing the logic at all, simply by
inserting a Block where local variable are defined, then passing the
values of the localised variables out to the corresponding global
variables at the end of the procedure:
compare = Compile[{
{a, _Integer, 1}, {b, _Integer, 1}
},
Block[{
s1 = 0, s2 = 0, k = Length[a],
loc`Cm = 0, loc`d1 = Table[0, {3}], loc`d2 = Table[0, {3}]
},
While[s1 < 3 && s2 < 3 && k - s1 > 0 && k - s2 > 0,
Which[
a[[k - s1]] > b[[k - s2]], loc`d1[[s1 + 1]] = a[[k - s1]]; s1++,
a[[k - s1]] < b[[k - s2]], loc`d2[[s2 + 1]] = b[[k - s2]]; s2++,
a[[k - s1]] == b[[k - s2]], k--
]
];
loc`Cm = Max[{s1, s2}];
Which[
loc`Cm > 2, False,
s1 - s2 == 1, loc`d2[[s1]] = b[[1]],
s2 - s1 == 1, loc`d1[[s2]] = a[[1]],
s1 - s2 == 2, loc`d2[[1]] = b[[2]]; loc`d2[[2]] = b[[1]],
s2 - s1 == 2, loc`d1[[1]] = a[[2]]; loc`d1[[2]] = a[[1]]
];
d1 = loc`d1; d2 = loc`d2;
Cm = loc`Cm
]
];
Now, the code compiles fully and is quite fast. Unfortunately, it does not
appear to give correct results: compare[{1, 2, 3, 6, 7, 9}, {1, 2, 4, 7,
8, 9}] returns Cm = 2 and sets d1 = {6, 3, 0} and d2 = {8, 4, 0}, whereas
per your description I had understood that Cm = 4, d1 = {3, 4}, and d2 =
{3, 5} were required. As I'm not sure whether the error lies in your
procedure or in my understanding of your problem, I haven't attempted to
change the logic of the above. If you need the function I gave previously
to return values in global variables, you could use:
compareCompiled = Compile[{
{vec1, _Integer, 1}, {vec2, _Integer, 1},
{MAXDIFFS, _Integer, 0}
},
Block[{
i1 = 1, i2 = 1,
diffct = 0,
db1 = Internal`Bag@Most[{0}], db2 = Internal`Bag@Most[{0}],
d1 = Most[{0}], d2 = Most[{0}]
},
(* Run along the lists, recording differences as we go *)
While[
i1 <= Length[vec1] && i2 <= Length[vec2] && diffct < MAXDIFFS,
Which[
vec1[[i1]] == vec2[[i2]], i1++; i2++,
vec1[[i1]] < vec2[[i2]], diffct++; Internal`StuffBag[db1, i1++],
vec1[[i1]] > vec2[[i2]], diffct++; Internal`StuffBag[db2, i2++]
]
];
(* Fix up in case we ran off the end of one of the lists *)
While[i1 <= Length[vec1] && diffct < MAXDIFFS,
diffct++; Internal`StuffBag[db1, i1++];
];
While[i2 <= Length[vec2] && diffct < MAXDIFFS,
diffct++; Internal`StuffBag[db2, i2++];
];
(* Convert bags to vectors *)
d1 = Internal`BagPart[db1, All];
d2 = Internal`BagPart[db2, All];
(* Return values *)
compare`d1 = d1;
compare`d2 = d2;
diffct
]
];
With[{cc = compareCompiled},
compare[vec1_, vec2_, MAXDIFFS_] :=
Block[{tmp`Cm, compare`d1, compare`d2},
If[(tmp`Cm = cc[vec1, vec2, MAXDIFFS + 1]) <= MAXDIFFS,
d1 = compare`d1; d2 = compare`d2,
d1 = d2 = {}
];
Cm = tmp`Cm
]
];
so that compare[{1, 2, 3, 6, 7, 9}, {1, 2, 4, 7, 8, 9}, 4] returns Cm = 4
and sets d1 = {3, 4} and d2 = {3, 5}, while compare[{1, 2, 3, 6, 7, 9},
{1, 2, 4, 7, 8, 9}, 3] returns Cm = 4 and sets d1 = d2 = {}. One aspect of
the problem I am not very clear about is whether you require the total
number of differences even when it exceeds the maximum number for which
you need the positions. The above simply stops accumulating differences
when the specified number is exceeded, so the maximum value of Cm you will
see is MAXDIFFS+1. Of course, this is easily changed if necessary.
I hope that these examples will be useful to you.
Best,
O. R.
[toc] | [prev] | [next] | [standalone]
| From | Yasha Gindikin <gindikin@gmail.com> |
|---|---|
| Date | 2011-09-28 06:47 +0000 |
| Message-ID | <j5ufue$7qa$1@smc.vnet.net> |
| In reply to | #5237 |
Dear Oleksandr, thank you for your kind explanations. I would be happy if the compiled function simply returned the values of diffs1 and diffs2. Assigning values to global variables is not obligatory for me, especially if it is time-consuming.
Unfortunately, there are problems. Trying to calculate the compiled functio n hyperfastVectorCompare[a, b, 4] with a = {1, 2, 3, 4, 5} and b = {1, 2, 6, 7, 12} yields "CompiledFunction::cflist: Nontensor object generated; proceeding with uncompiled evaluation", with the returned values being {{3, 4, 5}, {3}}.
It looks like that when local variables diffs1 and diffs2 have different length, the compiled function can not return those.
Is there any chance for the compiled function to return the local variables of different length (diffs1, diffs2 and diffct), without assigning those to the global variables? Thank you!
[toc] | [prev] | [next] | [standalone]
| From | "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> |
|---|---|
| Date | 2011-09-29 06:14 +0000 |
| Message-ID | <j612c9$m5i$1@smc.vnet.net> |
| In reply to | #5203 |
On Wed, 28 Sep 2011 07:47:42 +0100, Yasha Gindikin <gindikin@gmail.com>
wrote:
> Dear Oleksandr, thank you for your kind explanations. I would be happy
> if the compiled function simply returned the values of diffs1 and
> diffs2. Assigning values to global variables is not obligatory for me,
> especially if it is time-consuming.
>
> Unfortunately, there are problems. Trying to calculate the compiled
> functio n hyperfastVectorCompare[a, b, 4] with a = {1, 2, 3, 4, 5} and b
> = {1, 2, 6, 7, 12} yields "CompiledFunction::cflist: Nontensor object
> generated; proceeding with uncompiled evaluation", with the returned
> values being {{3, 4, 5}, {3}}.
>
> It looks like that when local variables diffs1 and diffs2 have different
> length, the compiled function can not return those.
>
> Is there any chance for the compiled function to return the local
> variables of different length (diffs1, diffs2 and diffct), without
> assigning those to the global variables? Thank you!
>
My mistake was to implicitly assume that we would not run off the end of
one of the vectors with more than one difference remaining, and thus that
diffs1 and diffs2 would be of the same length for any even number of
requested differences. As your example demonstrates, this is not
necessarily the case.
Unfortunately, compiled functions are restricted to returning full-rank
tensors, so to return the correct result in this case we must either pad
the shorter vector or use an uncompiled function to catch the two lists of
differences and build the result. The latter is probably the better
solution in terms of not returning unexpected values in the list of
differences, and can be achieved with minor modifications:
compareCompiled = Compile[{
{vec1, _Integer, 1}, {vec2, _Integer, 1},
{MAXDIFFS, _Integer, 0}
},
Block[{
i1 = 1, i2 = 1, diffct = 0,
(* Bags occupy scalar registers; contents returned as vectors *)
b1 = Internal`Bag@Most[{0}], v1,
b2 = Internal`Bag@Most[{0}], v2
},
(* Run along the lists, recording differences as we go *)
While[
i1 <= Length[vec1] && i2 <= Length[vec2] && diffct < MAXDIFFS,
Which[
vec1[[i1]] < vec2[[i2]], diffct++; Internal`StuffBag[b1, i1++],
vec1[[i1]] > vec2[[i2]], diffct++; Internal`StuffBag[b2, i2++],
True, i1++; i2++
]
];
(* Fix up in case we ran off the end of one of the lists *)
While[i1 <= Length[vec1] && diffct < MAXDIFFS,
diffct++; Internal`StuffBag[b1, i1++];
];
While[i2 <= Length[vec2] && diffct < MAXDIFFS,
diffct++; Internal`StuffBag[b2, i2++];
];
(* Move bag contents into vector registers and clear bags *)
v1 = Internal`BagPart[b1, All]; b1 = 0;
v2 = Internal`BagPart[b2, All]; b2 = 0;
(* Return contents of vector registers in external variables *)
Evaluate[compare`d1 = v1; compare`d2 = v2;];
diffct
]
];
(* Wrapper function to catch returned values and build the result *)
With[{cc = compareCompiled},
compare[vec1_, vec2_, MAXDIFFS_] :=
Block[{compare`d1, compare`d2},
{cc[vec1, vec2, MAXDIFFS], compare`d1, compare`d2}
]
];
Now compare[{1, 2, 3, 4, 5}, {1, 2, 6, 7, 12}, 4] gives the expected
result of {4, {3, 4, 5}, {3}} without any errors (where the elements of
this list are {diffct, diffs1, diffs2}). However, this does effectively
involve the use of global variables and so there will be a (small)
performance penalty. Depending on the length of your vectors and how you
use the result, it may be better just to return all of the differences, in
which case the result will always be a full-rank tensor that can be
returned directly from the compiled code; Ray Koopman has already given
examples of functions that do this.
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-09-25 09:46 +0000 |
| Message-ID | <j5mt8t$sn8$1@smc.vnet.net> |
| In reply to | #5194 |
On Sep 24, 7:37 pm, Yasha Gindikin <gindi...@gmail.com> wrote:
> I'm looking for a hyper-fast way to compare two vectors using
> Mathematica built-in functions. The problem arises in the
> calculation of the Hamiltonian matrix elements of a many-particle
> quantum system.
>
> Consider two rows of equal length n, a[[p1] and a[[p2]]. Their
> elements are integers from 1 to M, put in an increasing order,
> without repeats. E.g., a[[p1]] = {1,2,3,6,7,9} and a[[p2]] =
> {1,2,4,7,8,9}. I need to find the number of different elements
> (4 in the example) and, if this number is less or equal to 4,
> their positions ((3,4) and (3,5) in the example).
> The simplest way looks like this:
>
> diff = Intersection[a[[p1]], a[[p2]]];
> R = Dimensions[diff][[1]];
> If[R < 5, d1 = Complement[a[[p1]], diff];
> d2 = Complement[a[[p2]], diff];
> k1 = Position[a[[p1]], d1[[1]]]; k2 = Position[a[[p1]], d1[[2]]];
> k3 = Position[a[[p2]], d2[[1]]]; k4 = Position[a[[p2]], d2[[2]]]];
>
> This is slow, since four search operations are used (and because
> the ordering of the elements is not taken advantage of). Is there
> a built-in function that quickly finds the differences between the
> two vectors?
>
> Thank you.
> Regards,
> Yasha.
I'm confused about what you want. The verbal description refers
to "the number of different elements", which I would ordinaryily
take to mean Length@Union[a1,a2], and specifies that it be <= 4.
But the code checks Length@Intersection[a1,a2], the number of
different values that occur in both lists, and wants it to be <= 4.
The two criteria are not equivalent.
poscom[a,b] assumes that a and b are sorted lists of positive
integers, with no within-list duplicates. It returns the positions
in a of those values that are not also in b. It is equivalent to
Flatten[Position[a,#]&/@Complement[a,b]].
poscom[a_,b_] := Block[{r = ConstantArray[0,Max[a[[-1]],b[[-1]]]]},
r[[a]] = Range@Length@a; r[[b]] = ConstantArray[0,Length@b];
SparseArray[r] /. SparseArray[_,_,_,d_] :> d[[3]] ]
poscom[a1,a2]
poscom[a2,a1]
{3,4}
{3,5}
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-09-26 08:16 +0000 |
| Message-ID | <j5pcca$8fu$1@smc.vnet.net> |
| In reply to | #5206 |
On Sep 25, 2:46 am, Ray Koopman <koop...@sfu.ca> wrote:
> [...]
> poscom[a,b] assumes that a and b are sorted lists of positive
> integers, with no within-list duplicates. It returns the positions
> in a of those values that are not also in b. It is equivalent to
> Flatten[Position[a,#]&/@Complement[a,b]].
>
> poscom[a_,b_] := Block[{r = ConstantArray[0,Max[a[[-1]],b[[-1]]]]},
> r[[a]] = Range@Length@a; r[[b]] = ConstantArray[0,Length@b];
> SparseArray[r] /. SparseArray[_,_,_,d_] :> d[[3]] ]
This may be faster than poscom for some data:
poskom[a_,b_] := Block[{r = Normal@SparseArray[ Automatic,
{Max[a[[-1]],b[[-1]]]}, 0, {1, {{0, Length@a}, Transpose@{a}},
Range@Length@a} ]}, r[[b]] = ConstantArray[0,Length@b];
SparseArray[r] /. SparseArray[_,_,_,d_] :> d[[3]] ]
[toc] | [prev] | [next] | [standalone]
| From | Yasha Gindikin <gindikin@gmail.com> |
|---|---|
| Date | 2011-09-26 08:13 +0000 |
| Message-ID | <j5pc7f$8c8$1@smc.vnet.net> |
| In reply to | #5206 |
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.:)
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-09-27 22:52 +0000 |
| Message-ID | <j5tk3k$3bd$1@smc.vnet.net> |
| In reply to | #5227 |
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
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-09-27 10:23 +0000 |
| Message-ID | <j5s87d$peq$1@smc.vnet.net> |
| In reply to | #5227 |
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
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-09-29 06:13 +0000 |
| Message-ID | <j6129e$m4j$1@smc.vnet.net> |
| In reply to | #5206 |
On Sep 27, 3:52 pm, 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
If each vector is compared to many other vectors then some time
can be saved by doing the setup preprocessing only once, instead of
repeating it for every comparison. The following does all k(k-1)/2
pairwise comparisons of k vectors.
Dimensions[a = Table[Sort@RandomSample[Range[m = 200], n = 100],
{k = 150}]]
{150, 100}
AbsoluteTiming@Dimensions[ u = vcomb @@@ Subsets[a,{2}] ]
{2.074797, {11175, 2}}
AbsoluteTiming@Dimensions[ v = vkom @@@ Subsets[a,{2}] ]
{2.288352, {11175, 2}}
AbsoluteTiming@Dimensions[ p = SparseArray[Automatic, {m}, 0,
{1, {{0, n}, Transpose@{#}}, Range@n}]& /@ a; q = UnitStep[-p];
w = {SparseArray[p[[#1]]*q[[#2]]]/.SparseArray[_,_,_,d_] :> d[[3]],
SparseArray[p[[#2]]*q[[#1]]]/.SparseArray[_,_,_,d_] :> d[[3]]}&
@@@ Subsets[Range@k,{2}] ]
{1.369321, {11175, 2}}
SameQ[u, v, w]
True
[toc] | [prev] | [next] | [standalone]
| From | "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> |
|---|---|
| Date | 2011-09-30 08:06 +0000 |
| Message-ID | <j63taq$6g3$1@smc.vnet.net> |
| In reply to | #5206 |
On Tue, 27 Sep 2011 23:52:36 +0100, Ray Koopman <koopman@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
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-10-01 07:13 +0000 |
| Message-ID | <j66ejg$hft$1@smc.vnet.net> |
| In reply to | #5290 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Yasha Gindikin <gindikin@gmail.com> |
|---|---|
| Date | 2011-10-03 08:22 +0000 |
| Message-ID | <j6brc0$8it$1@smc.vnet.net> |
| In reply to | #5206 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-10-07 09:09 +0000 |
| Message-ID | <j6mfjr$7m7$1@smc.vnet.net> |
| In reply to | #5334 |
On Oct 3, 1:22 am, Yasha Gindikin <gindi...@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}
[toc] | [prev] | [standalone]
Back to top | Article view | comp.soft-sys.math.mathematica
csiph-web