Board index » delphi » Comparing two arrays - help !

Comparing two arrays - help !

Hi,

I've the 2 following arrays :

A=[1,2,3,4,5,6]
B_[1,5,7,8,9,11]

Is there an efficient way of comparing A and B and stating that they
have only 2 elements equal ?

I'me not intersted in the elements. I dont want to use a loop.

Any help will be appreciated
Ivanov

 

Re:Comparing two arrays - help !


Quote
>I've the 2 following arrays :

>A=[1,2,3,4,5,6]
>B_[1,5,7,8,9,11]

>Is there an efficient way of comparing A and B and stating that they
>have only 2 elements equal ?

Just an idea, in pseudo-code (should be linear (=O(2n)) complexity):

ElementCount:=count1:=count2:=0;
while (count1<>length(Array1)) and (count2<>length(Array2)) do
begin
     while Array1[count1]<Array2[count2] do
          Inc(count1);

     while Array2[count2]<Array1[count1] do
          Inc(count2);

     if Array1[count1]=Array2[count2} then
        Inc(ElementCount);
end;

hth,
Ralf S.

Re:Comparing two arrays - help !


In article <a0846ab0.0202090500.481c9...@posting.google.com>,

Quote
ivano...@hotmail.com (Ivanov) writes:
>'ve the 2 following arrays :

>A=[1,2,3,4,5,6]
>B_[1,5,7,8,9,11]

>Is there an efficient way of comparing A and B and stating that they
>have only 2 elements equal ?

If you had two sets (ie of ordinals less than 256) then it would be fairly easy
...

 A, B, C : set of byte;

C := A * B;  // intersection of A and B
CommonCount := 0
for i = 0 to 255
  if i in C then
    inc(CommonCount);

... and as the "in" operator is fairly fast, it would be quite quick.

Alan Lloyd
alangll...@aol.com

Re:Comparing two arrays - help !


Quote
Ralf Steinhaeusser <newsbouncer...@spoonworx.com> wrote in message <news:ctba6uc138ulohg2istdlug0m4cco6gmbn@4ax.com>...
> >I've the 2 following arrays :

> >A=[1,2,3,4,5,6]
> >B_[1,5,7,8,9,11]

> >Is there an efficient way of comparing A and B and stating that they
> >have only 2 elements equal ?

> Just an idea, in pseudo-code (should be linear (=O(2n)) complexity):

> ElementCount:=count1:=count2:=0;
> while (count1<>length(Array1)) and (count2<>length(Array2)) do
> begin
>      while Array1[count1]<Array2[count2] do
>           Inc(count1);

>      while Array2[count2]<Array1[count1] do
>           Inc(count2);

>      if Array1[count1]=Array2[count2} then
>         Inc(ElementCount);
> end;

> hth,
> Ralf S.

Hi, Ralf,

Thanks for the tip. I'll try to code it in delphi 5 and compare the
execution time with the classical For ... Do ..  Loop.

Ivanov.

Re:Comparing two arrays - help !


On 9 Feb 2002 05:00:43 -0800, ivano...@hotmail.com (Ivanov) wrote:

Quote
>I'me not intersted in the elements. I dont want to use a loop.

Why must a loop be avoided?

Re:Comparing two arrays - help !


On Sat, 09 Feb 2002 15:24:06 +0100, Ralf Steinhaeusser

Quote
<newsbouncer...@spoonworx.com> wrote:
>>A=[1,2,3,4,5,6]
>>B_[1,5,7,8,9,11]

>Just an idea, in pseudo-code (should be linear (=O(2n)) complexity):

This assumes that the arrays are sorted.  OP: can we be sure that the
arrays are sorted?

Re:Comparing two arrays - help !


Quote
>>Just an idea, in pseudo-code (should be linear (=O(2n)) complexity):

>This assumes that the arrays are sorted.  OP: can we be sure that the
>arrays are sorted?

Add to pseudo-code:

if Not_Sorted then Sort;

Re:Comparing two arrays - help !


Hi, All

I had some problems implementing in Delphi The excellent Ralph's
algorithm, however, the additional work was rewarded.

Note: for ralph's algorithm to work, Arrays must be sorted.
      (And, in my example arrays are sorted.)

I tested it (for speed) against (1) a FOR...LOOP.., and (2) the IN
operator using sets.

Using a Pentium II, 600 Mhz, I made  1.000.000 calls to a procedure
containing just the necesary code of each of the three cases, and the
execution times were as follows:

Ralph's algorithm :   394 ms
FOR.. LOOP        :   705 ms
IN operator       : 1.140 ms in average

No comment..

Any sugestion to improve Ralph's algorithm will be appreciated.
Thanks Ralph,

Ivanov.

Re:Comparing two arrays - help !


It's hard to beat "in" .. as long as you are not dealing with more than
255 elements.

If you are, then a "sparse matrix" implementation that uses, say, a tree
of sets and maybe other sets showing what tree-nodes exist, could be
created to implement very fast comparisons indeed.

The tradeoff is, as always, "speed vs. memory."  If your data structures
are very large you may have to remember that the memory is, in fact,
virtual.

When you "find a better algorithm," quantum leaps in efficiency are not
unusual.

Quote
>Ivanov wrote:

> Hi, All

> I had some problems implementing in Delphi The excellent Ralph's
> algorithm, however, the additional work was rewarded.

> Note: for ralph's algorithm to work, Arrays must be sorted.
>       (And, in my example arrays are sorted.)

> I tested it (for speed) against (1) a FOR...LOOP.., and (2) the IN
> operator using sets.

> Using a Pentium II, 600 Mhz, I made  1.000.000 calls to a procedure
> containing just the necesary code of each of the three cases, and the
> execution times were as follows:

> Ralph's algorithm :   394 ms
> FOR.. LOOP        :   705 ms
> IN operator       : 1.140 ms in average

> No comment..

> Any sugestion to improve Ralph's algorithm will be appreciated.

----------------------------------------------------------------
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:i...@sundialservices.com  (PGP public key available.)

- Show quoted text -

Quote
> Fast(!), automatic table-repair with two clicks of the mouse!
> ChimneySweep(R):  Release 4.0 is here!!
> http://www.sundialservices.com/products/chimneysweep

Re:Comparing two arrays - help !


On Sun, 10 Feb 2002 10:30:20 -0700, Sundial Services

Quote
<info_...@sundialservices.com> wrote:
>It's hard to beat "in" .. as long as you are not dealing with more than
>255 elements.

>If you are, then a "sparse matrix" implementation that uses, say, a tree
>of sets and maybe other sets showing what tree-nodes exist, could be
>created to implement very fast comparisons indeed.

>The tradeoff is, as always, "speed vs. memory."  If your data structures
>are very large you may have to remember that the memory is, in fact,
>virtual.

>When you "find a better algorithm," quantum leaps in efficiency are not
>unusual.

Quite !

Sorting the arrays is going to be an overhead for a start
- and the timing test was totally unrealistic as it was simply
repeatedly comparing _sorted_ arrays.

Since the problem looks like a Lottery checker, I am damn sure that
the thing could be both simplified *and* dramatically speeded up - a
target array of Booleans and for each ticket just look at the value
of:
          If  Bool[ A[ L9 ] ] Then Count := Count + 1

If it is not a Lottery checker then it would be interesting to know
what is _really_ required

ie: is the data naturally sorted
     what is the upper bound of the data (if any)
     how many items in the array(s)

Quote

>>Ivanov wrote:

>> Hi, All

>> I had some problems implementing in Delphi The excellent Ralph's
>> algorithm, however, the additional work was rewarded.

>> Note: for ralph's algorithm to work, Arrays must be sorted.
>>       (And, in my example arrays are sorted.)

>> I tested it (for speed) against (1) a FOR...LOOP.., and (2) the IN
>> operator using sets.

>> Using a Pentium II, 600 Mhz, I made  1.000.000 calls to a procedure
>> containing just the necesary code of each of the three cases, and the
>> execution times were as follows:

>> Ralph's algorithm :   394 ms
>> FOR.. LOOP        :   705 ms
>> IN operator       : 1.140 ms in average

>> No comment..

>> Any sugestion to improve Ralph's algorithm will be appreciated.
>----------------------------------------------------------------
>Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
>mailto:i...@sundialservices.com  (PGP public key available.)
>> Fast(!), automatic table-repair with two clicks of the mouse!
>> ChimneySweep(R):  Release 4.0 is here!!
>> http://www.sundialservices.com/products/chimneysweep

Re:Comparing two arrays - help !


In article <a0846ab0.0202100914.79ce4...@posting.google.com>,

Quote
ivano...@hotmail.com (Ivanov) writes:
>Using a Pentium II, 600 Mhz, I made  1.000.000 calls to a procedure
>containing just the necesary code of each of the three cases, and the
>execution times were as follows:

>Ralph's algorithm :   394 ms
>FOR.. LOOP        :   705 ms
>IN operator       : 1.140 ms in average

I measured the times within a procedure to carry out 1 million tests of the two
arrays and got similar results, but a markedly greater improvement for Ralf's
algorithm (optimisation made little relative difference) with an AMD K2-600 ...

Set 7500 mS
For loop 800 mS
Ralf's 170 mS

I don't think you are going to improve on Ralf's, it has similarities to the
Boyer - Moore - Horspool search on strings, and that is quite good.

BTW I think that Ralf's needed a couple of inc() on the counts before the end
of the outer while loop, otherwise mine got stuck on equal elements with the
same indices..

Alan Lloyd
alangll...@aol.com

Re:Comparing two arrays - help !


On 10 Feb 2002 09:14:06 -0800, ivano...@hotmail.com (Ivanov) wrote:

Quote
>Ralph's algorithm :   394 ms
>FOR.. LOOP        :   705 ms
>IN operator       : 1.140 ms in average

Yes, the set method works well if your data is byte-sized.

Re:Comparing two arrays - help !


On 10 Feb 2002 09:14:06 -0800, ivano...@hotmail.com (Ivanov) wrote:

Quote
>Using a Pentium II, 600 Mhz, I made  1.000.000 calls to a procedure
>containing just the necesary code of each of the three cases, and the
>execution times were as follows:

The method below takes 110 ms for 1,000,000 trials on a 1.3 GHz
Athlon, which is somewhat more than twice as fast as your CPU.  It
doesn't require them to be sorted, but it does require the data to be
in arrays.  Is your data in arrays or sets?  Your data was written
like a set, but you said array.

It is also dependant on the largest number that can be in the data.
Of course, it uses loops, and you wanted to avoid that.

const aa : array[ 1 .. 6] of integer = (1,2,3,4,5,6);
      bb : array[ 1 .. 6] of integer = (1,5,7,8,9,11);

var i, counter : integer;
  xx : array[ 1 .. 255] of boolean;

  FillChar( xx, sizeof( xx), false);

  for i := 1 to 6
    do xx[ aa[ i]] := true;

  counter := 0;

  for i := 1 to 6 do
  if xx[ bb[ i]]
    then inc( counter);

The FillChar takes 86% of the time in this example, which depends on
the size of the array.

Re:Comparing two arrays - help !


On Sun, 10 Feb 2002 16:05:31 +0100, Ralf Steinhaeusser

Quote
<newsbouncer...@spoonworx.com> wrote:
>Add to pseudo-code:

>if Not_Sorted then Sort;

That will increase the running time, and the OP wanted no loops.  Hard
to do without loops.

If you are doing it with a small enough bound on the numbers, and they
both are unsorted, a better way would be to use the first one to set a
boolean array and then loop through the second and count the matches.

Re:Comparing two arrays - help !


On Sun, 10 Feb 2002 16:29:53 -0500, Jan Philips

Quote
<jud.mccra...@mindspring.com> wrote:

<snip from below>

Quote
>The FillChar takes 86% of the time in this example, which depends on
>the size of the array.

Ah - but what happens if the OP only needs to use FillChar once
- ie: they have one set/array of numbers that they are comparing with
a lot of .... um ... lottery tickets.

The original problem is ill defined - if it is Lottery tickets then
the Boolean lookup is the answer - if it is not Lottery tickets then
there is bound to be another approach.

Quote

>const aa : array[ 1 .. 6] of integer = (1,2,3,4,5,6);
>      bb : array[ 1 .. 6] of integer = (1,5,7,8,9,11);

>var i, counter : integer;
>  xx : array[ 1 .. 255] of boolean;

>  FillChar( xx, sizeof( xx), false);

>  for i := 1 to 6
>    do xx[ aa[ i]] := true;

>  counter := 0;

>  for i := 1 to 6 do
>  if xx[ bb[ i]]
>    then inc( counter);

>The FillChar takes 86% of the time in this example, which depends on
>the size of the array.

Go to page: [1] [2]

Other Threads