Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #5194 > unrolled thread

A fast way to compare two vectors

Started byYasha Gindikin <gindikin@gmail.com>
First post2011-09-25 02:37 +0000
Last post2011-10-07 09:09 +0000
Articles 17 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  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

#5194 — A fast way to compare two vectors

FromYasha Gindikin <gindikin@gmail.com>
Date2011-09-25 02:37 +0000
SubjectA 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]


#5203

From"Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com>
Date2011-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]


#5214

From"Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com>
Date2011-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]


#5219

FromYasha Gindikin <gindikin@gmail.com>
Date2011-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]


#5237

From"Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com>
Date2011-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]


#5254

FromYasha Gindikin <gindikin@gmail.com>
Date2011-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]


#5285

From"Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com>
Date2011-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]


#5206

FromRay Koopman <koopman@sfu.ca>
Date2011-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]


#5213

FromRay Koopman <koopman@sfu.ca>
Date2011-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]


#5227

FromYasha Gindikin <gindikin@gmail.com>
Date2011-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]


#5250

FromRay Koopman <koopman@sfu.ca>
Date2011-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]


#5262

FromRay Koopman <koopman@sfu.ca>
Date2011-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]


#5282

FromRay Koopman <koopman@sfu.ca>
Date2011-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]


#5290

From"Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com>
Date2011-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]


#5312

FromRay Koopman <koopman@sfu.ca>
Date2011-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]


#5334

FromYasha Gindikin <gindikin@gmail.com>
Date2011-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]


#5507

FromRay Koopman <koopman@sfu.ca>
Date2011-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