in reply to Comparing two arrays

I would try to use a hash to some advantage. For example, total up the sum of the entries and perhaps the index of the leftmost '1', then make that into a hash-key. The essential goal is to minimize the number of arrays that you actually search, no matter how you go about searching or representing them. The hash won't tell you which one (if any) matches, but only entries in that chosen bucket need be considered.

Replies are listed 'Best First'.
Re^2: Comparing two arrays
by fullermd (Priest) on Dec 16, 2013 at 11:45 UTC

The essential goal is to minimize the number of arrays that you actually search, no matter how you go about searching or representing them.

This was my thought too; with that many items to cross-compare, doing various "cheats" to cut down on how many you actually need to search is profitable. Even something as simple as just keeping counts of the number of 1's in each array can give you a real cheap method of asking "is it possible that these two arrays are the same?"

You'll get false positives (probably a lot of them), but you can guarantee no false negatives, so that can chop orders of magnitude off the problem. With a 15,000-element array, you know there's some number between 0 and 15000 1's; if they're evenly distributed (which they won't be even close, but it's a starting point to guess) then you're immediately dropping from "test these 5 million" to "test these 333", which is a huge speedup. Even if the distribution is off by an order or two of magnitude, dropping to 3 or 30,000 comparisons is a giant gain from 5 million.

Then adding some additional cheap to store/compare (maybe not necessarily calculate, but you may be able do this at the same time as the arrays get built for minimal added expense) hints like the leftmost-1-index or rightmost-1-index or longer-run-of-1's or some other thing meaningful to your data set, can chop that down even further. At what point the diminishing returns start hurting you is situation specific; it would take knowing your data and possibly some experimentation to find it.

In essence, these sort of universe-narrowing tricks can be seen as variations on the theme of Bloom filters. A quick glance at cpan shows up some Bloom filter implementations, but it's hard to say whether they're well suited to this particular type/scale of usage. But they may on deeper investigation prove to be so...