Algorithm to compare to arrays of int

[Devrobcom]

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;
}

void my_main_thread()
{
//
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]

"Devrobcom" <de*******@hotmail.com> wrote in message
news:40********@news1e1.seinf.abb.se...

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;
}

void my_main_thread()
{
//
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.]

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;
}

void my_main_thread()
{
//
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]

Hashing seems to be the only way to make this really fast IMHO.
"Devrobcom" <de*******@hotmail.com> wrote in message
news:40********@news1e1.seinf.abb.se...

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;
}

void my_main_thread()
{
//
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]

On Tue, 18 May 2004 10:40:08 +0200, "Devrobcom"
<de*******@hotmail.com> 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;
}

void my_main_thread()
{
//
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]

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;
}

void my_main_thread()
{
//
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]

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.

comp.programming could probably help you out.

[Alex]

"Case" <[e-mail]> wrote in message
news:40***********************@news.xs4all.nl...

Is binary_search a standard C library function?

No, but bsearch() is.

Alex

[Devrobcom]

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