Intersection algorithm for two unsorted, small array

Question

I'm looking for an algorithm for intersection of two small, unsorted array in very specific condition.

• Type of array item is just integer or integer-like type.
• Significant amount of time (about 30~40%?), one or both array might be empty.
• Arrays are usually very small - usually 1~3 items, I don't expect more than 10.
• The intersection function will be called very frequently.
• I don't care about platform dependent solution - I'm working on x86/windows/C++

Both brute-force/sort-and-intersect solutions are not that bad, but I don't think that they're fast enough. Is there more optimal solution?

Answer 1

As the arrays are of primitive types, and short enough to be in cache lines, a fast implementation would focus on the tactical mechanics of comparisons rather than the big O complexity e.g. avoid hash-tables as these would generally involve hashing and indirection and would always involve a lot of management overhead.

If you have two sorted arrays, then intersection is O(n+m). You say that sort-then-intersect is 'brute-force' but you can't do it quicker.

If the arrays are stored sorted, of course, you gain further as you say you are calling the intersection often.

The intersection itself can be done with SSE.

Answer 2

Here's a potential optimization: check whether both arrays have max element <=32 (or 64, or maybe even 16). If they do, then fill two bitmaps of that size (of type uint32_t, etc.) and intersect using a binary AND, &. If they're not, resort to sorting.

Or, instead of sorting, use the highly efficient integer set representation due to Briggs and Torczon that allows linear time intersect with O(m + n) construction and O(min(m, n)) intersect. That should be much faster than a hash table with better bounds than sorting.