3

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?

Improve this question
6
  • 1
    What's "fast enough" for scenario? Commented Feb 5, 2013 at 7:26
  • Sort-and-intersect starting with if (a.empty || b.empty) return emptySet;. Also, if there's only 1 element you can just look for that in the other array. Commented Feb 5, 2013 at 7:35
  • one very significant question: how much such distinct sets may exists? (it very much dependent on the values in the set) if there are small amount of distinct values, you have very good solution. Commented Feb 5, 2013 at 7:38
  • Ameen // I expect several millions call per sec, and shouldn't occupy significant amount of runtime. (< 0.1%?) Commented Feb 5, 2013 at 7:40
  • Michael // I expect two arrays are tend be to correlated to each other, but don't have any statistics yet. Commented Feb 5, 2013 at 7:44

4 Answers 4

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

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.

Improve this answer

Comments

1

In order to determine the intersection of both sets you have to inspect all elements at least once, so that means the most optimal class of solutions yield O(n + m) where n is the number of elements in one set and m the number of elements in the other.

You can achieve that by using a hash table. Given that your items are of type integer, you can count on finding a fast hash function. A simple algorithm would be:

  • Iterate first set and add all elements to hash table
  • Iterate second set and for each element, check if it exists in the hash table, if so, add it to the intersection set or just print it.

This would be O(n + m) assuming your hashing and your hash lookup are O(1).

Given that you know the sets are frequently empty, you can optimize this by first checking to see if one of the sets is empty, if so, just return an empty set. That's of course assuming that you know the count upfront and can calculate it without iterating the set. If that happens to be the case, you can optimize further by always first reading and hashing the smaller set, ensuring that your hash table memory usage will be the smaller of the two.

Improve this answer

4 Comments

Yet another optimization, you can stop checking once your intersection set reaches the size of the smaller of the two sets.
Thanks for your answer. I think using hash table would be good solution if the input size is more larger(100~), but it seems to be too costly to use hash table in my case, especially in C++ (dynamic allocation isn't cheap)
If you are expecting millions of calls per second, then you certainly should not be using hash tables I agree. That was missing from the original question.
Aside from the "quick outs" (exiting early if a set is empty, etc.), given that you don't expect more than 10 elements, I'd just write a brute force method. If you use -O3 and above in your compiler, you should get loop unrolling which should bring you significant performance improvements (as long as all the elements of a set fit within one cache line you should get great performance).
1

Well, since your arrays are quite small, using insertion sort will be the fastest way to sort these two arrays, C++ STL uses insertion sort for arrays smaller than 16 items as well. Then you can use iterators over these two arrays to compare and intersect the arrays.

There may be other algorithms which would perform faster, however the overhead of these algorithms will probably be too large for 3-4 items per array.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.