Re: [tlug] array duplicate check [C]

[Darren Cook <darren@example.com>]

> I have two integer arrays  of size N and M and I want to check if none
> of the elements in the first arrays are contained in the second array.

If the integers are of limited range (e.g. 1..100), and the array
duplicate check was the bottleneck in your system, then you could change
your data structure from being an array to being a bit field, where if
bit zero is set it means 1 is in the array, if clear it means it isn't
... if bit 99 is set it means 100 is in the array.

Then the check reduces to a simple logical OR, where a result of zero
means no overlap.

This method also saves memory unless your arrays are very sparse.

When you also need the list in some order, or need to iterate over the
list quickly, you can use a C array in parallel with the bitfield. (Easy
to get out of sync in C; better in C++ where you can have private data
members and get/set functions.)

Darren


-- 
Darren Cook
http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
http://dcook.org/work/ (About me and my work)
http://dcook.org/work/charts/  (My flash charting demos)