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) >= 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]

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) >= 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.]

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) >= 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.

 

[Severian]

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) >= 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.

 

[Case]

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) >= 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]

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]

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