Velocity Reviews > Algorithm to compare to arrays of int

# Algorithm to compare to arrays of int

Devrobcom
Guest
Posts: n/a

 05-18-2004
Hi
I have an array with 30 int and another array with 1000 int.
If any of the 30 intergers can be found in the 1000 int array I shall return
true.
The contents of the arrays will also change over time.
I'm looking for a way to do this with good performance.

One way could be to:

bool any_match(int smal[], int smal_sz, int large[], int large_sz)
{
for(int i = 0; i < smal_sz; i++)
{
if ( binary_search(large, large_sz, smal[i]) >= 0) return true;
}
return false;
}

{
//
int large_array[1000];
int smal_array[30]

//
// sort large array when updated
//

// check if any id can be found
if (any_match(smal_array, 30, large_array, 1000) )
{
dowork();
}
}

Since I will do this very frequently I need something that takes little cpu.
The memory size is not a problem.

/Dev

Allan Bruce
Guest
Posts: n/a

 05-18-2004

"Devrobcom" <(E-Mail Removed)> wrote in message
news:40a9cbe9\$(E-Mail Removed)...
> Hi
> I have an array with 30 int and another array with 1000 int.
> If any of the 30 intergers can be found in the 1000 int array I shall

return
> true.
> The contents of the arrays will also change over time.
> I'm looking for a way to do this with good performance.
>
> One way could be to:
>
> bool any_match(int smal[], int smal_sz, int large[], int large_sz)
> {
> for(int i = 0; i < smal_sz; i++)
> {
> if ( binary_search(large, large_sz, smal[i]) >= 0) return true;
> }
> return false;
> }
>
> {
> //
> int large_array[1000];
> int smal_array[30]
>
> //
> // sort large array when updated
> //
>
> // check if any id can be found
> if (any_match(smal_array, 30, large_array, 1000) )
> {
> dowork();
> }
> }
>
> Since I will do this very frequently I need something that takes little

cpu.
> The memory size is not a problem.
>

If speed is an issue, then consider using a hashtable. Have the hashtable
store the int as your index and a char as the data. If the data returned is
non-null then your number is located in the hashtable. You must remember to
remove items from the hashtable this way tho.
Allan

Stephen L.
Guest
Posts: n/a

 05-18-2004
Devrobcom wrote:
>
> Hi
> I have an array with 30 int and another array with 1000 int.
> If any of the 30 intergers can be found in the 1000 int array I shall return
> true.
> The contents of the arrays will also change over time.
> I'm looking for a way to do this with good performance.
>
> One way could be to:
>
> bool any_match(int smal[], int smal_sz, int large[], int large_sz)
> {
> for(int i = 0; i < smal_sz; i++)
> {
> if ( binary_search(large, large_sz, smal[i]) >= 0) return true;
> }
> return false;
> }
>
> {
> //
> int large_array[1000];
> int smal_array[30]
>
> //
> // sort large array when updated
> //
>
> // check if any id can be found
> if (any_match(smal_array, 30, large_array, 1000) )
> {
> dowork();
> }
> }
>
> Since I will do this very frequently I need something that takes little cpu.
> The memory size is not a problem.
>
> /Dev

You imply that you program has knowledge when
a position in the "large" array is updated.
Why not, for each position changed in this "large"
array, search the "small" array for a match.

Since you haven't mentioned how the "large" array
is updated (round-robin, etc.), doing the above
may eliminate the need for keeping the "large"
array sorted (if its only purpose is for a later
binary search). Saving a 1000 item sort has gotta
provide a performance boost...

HTH,

Stephen

buda
Guest
Posts: n/a

 05-18-2004
Hashing seems to be the only way to make this really fast IMHO.

"Devrobcom" <(E-Mail Removed)> wrote in message
news:40a9cbe9\$(E-Mail Removed)...
> Hi
> I have an array with 30 int and another array with 1000 int.
> If any of the 30 intergers can be found in the 1000 int array I shall

return
> true.
> The contents of the arrays will also change over time.
> I'm looking for a way to do this with good performance.
>
> One way could be to:
>
> bool any_match(int smal[], int smal_sz, int large[], int large_sz)
> {
> for(int i = 0; i < smal_sz; i++)
> {
> if ( binary_search(large, large_sz, smal[i]) >= 0) return true;
> }
> return false;
> }
>
> {
> //
> int large_array[1000];
> int smal_array[30]
>
> //
> // sort large array when updated
> //
>
> // check if any id can be found
> if (any_match(smal_array, 30, large_array, 1000) )
> {
> dowork();
> }
> }
>
> Since I will do this very frequently I need something that takes little

cpu.
> The memory size is not a problem.
>
> /Dev
>
>

Severian
Guest
Posts: n/a

 05-18-2004
On Tue, 18 May 2004 10:40:08 +0200, "Devrobcom"
<(E-Mail Removed)> wrote:

>Hi
>I have an array with 30 int and another array with 1000 int.
>If any of the 30 intergers can be found in the 1000 int array I shall return
>true.
>The contents of the arrays will also change over time.
>I'm looking for a way to do this with good performance.
>
>One way could be to:
>
>bool any_match(int smal[], int smal_sz, int large[], int large_sz)
>{
> for(int i = 0; i < smal_sz; i++)
> {
> if ( binary_search(large, large_sz, smal[i]) >= 0) return true;
> }
> return false;
>}
>
>{
>//
>int large_array[1000];
>int smal_array[30]
>
>//
>// sort large array when updated
>//
>
>// check if any id can be found
>if (any_match(smal_array, 30, large_array, 1000) )
>{
> dowork();
>}
>}
>
>Since I will do this very frequently I need something that takes little cpu.
>The memory size is not a problem.

If the range of integers in large_array is reasonably constrained, you
could use a bit to represent each possibile value, making setting and
checking very fast. If the range is not limited, create a hash table.

--
Sev

Case
Guest
Posts: n/a

 05-18-2004
Devrobcom wrote:
> Hi
> I have an array with 30 int and another array with 1000 int.
> If any of the 30 intergers can be found in the 1000 int array I shall return
> true.
> The contents of the arrays will also change over time.
> I'm looking for a way to do this with good performance.
>
> One way could be to:
>
> bool any_match(int smal[], int smal_sz, int large[], int large_sz)
> {
> for(int i = 0; i < smal_sz; i++)
> {
> if ( binary_search(large, large_sz, smal[i]) >= 0) return true;

Is binary_search a standard C library function?

> }
> return false;
> }
>
> {
> //
> int large_array[1000];
> int smal_array[30]
>
> //
> // sort large array when updated
> //
>
> // check if any id can be found
> if (any_match(smal_array, 30, large_array, 1000) )
> {
> dowork();
> }
> }
>
> Since I will do this very frequently I need something that takes little cpu.
> The memory size is not a problem.

It depends how often your arrays are updated compared to how
often you do the match. So, could you give details about how
many items at a time and how often you update each array...
Also interesting to know might be the sizeof the ints (or the
range of values); small int/range might 'allow' other strategies.

Kees

Grumble
Guest
Posts: n/a

 05-18-2004
Devrobcom wrote:

> I have an array with 30 int and another array with 1000 int.
> If any of the 30 integers can be found in the 1000 int array
> I shall return true.
> The contents of the arrays will also change over time.
> I'm looking for a way to do this with good performance.

Alex
Guest
Posts: n/a

 05-18-2004
"Case" <(E-Mail Removed)> wrote in message
news:40aa0b2f\$0\$65124\$(E-Mail Removed)4all.nl...
> Is binary_search a standard C library function?

No, but bsearch() is.

Alex

Devrobcom
Guest
Posts: n/a

 05-19-2004
Thank you all!
I have been away from my computer the whole day and haven't been able to
join.
I will check if I can use a hash table.
/Dev