Are there algorithms that can find the most repeated values in a very large array in a millisecond?

Question

As the title says, I've developed my own algorithm that can do so, however mine would take 1-2 seconds searching through an array with 1 million length, however I am very curious if this can be made so much faster like 0.01s or even 0.001 is this mathematically impossible? I've used C++ with vectors and jsons to create mine, were these the right way to build such algorithms? or are there algorithms already out there?

Also there is a limit on how many values there would be, for my example I've calculated there would be atleast 100k-1M unique values in a single array with a length of 1 million. I've also tried threading but since you have to sync the variables you need to count the repetitions I find this not a "good" way of implementing things

Answer 1

If you can define by yourself what “most repeated” values means, then you can use the Space Saving algorithm. See the paper available here for the details.

The Space Saving algorithm allows you to determine all of the frequent items, also known as heavy hitters, without incurring in false negative (i.e. it’s recall is always equal to 1); however, there can be false positives (it’s precision may not be necessarily 1, but it is usually quite close to 1).

In this context, letting $n$ be the length of your dataset, frequent items are defined by a threshold $0 < \phi < 1$ so that an item is frequent if it appears in your dataset at least $\phi n$ times.

You can find C/C++ implementations which implement correctly the summary data structure (i.e. they are capable of processing in constant time an item when the item must be inserted into the summary: the implementation is really tricky when done correctly, since it requires, along with other things, to determine the minimum of $k$ counters in constant time; here $k$ is the size of the summary, its number of counters. It’s easy of course to implement the algorithm so that finding the minimum is done in $O(k)$, but the algorithm is fast only if the summary data structure is implemented correctly as described in the paper) and are fast enough to process tens of millions of items per second.

Answer 2

One approach is to sort the list, which brings duplicated together. Then you can count the number of duplicates of each item with a simple linear scan. Good sorting algorithms should be extremely fast.

Another approach is to use a hashtable: store each item in a hashtable, along with a count, and when you see an item that you've already seen before, increment the count. Then a linear scan through the hashtable suffices to find the item whose count is the largest.

Answer 3

Milliseconds for a million elements means nanoseconds per elements. One nanosecond may be half a dozen instructions. That’s difficult. Let’s set a goal of few (less than ten) milliseconds.

For a generic algorithm that handles all kind of data this is tough. But let’s say your million numbers were picked at random from 0 to M-1, with M = ten million or 50 million, “at random” means some numbers but not many turn up repeatedly.

We create a bitset with M elements, then process the numbers in sequence. If a number X is not in the bit set, then we set bit X. With M = 10 million that’s what happens in 90% of all cases. If X is already set, then we do two things: We add X to a hash set if not present yet, and either initialise a counter to 2 if X wasn’t present, or increase the counter. We also maintain an array that tells us how often each count >= 2 happened.

This is all more time consuming than just checking and setting one bit, but is much more rare, so instead of nanoseconds we can spend tens of nanoseconds.

After processing all numbers, we determine how many numbers with “largest count” we want and extract them.

If we have more than say 200 million numbers, we set a bit for x % 100,000,000 do only one in 100 would get a count of 2. If M is smaller, the number of different X occurring twice or more often will still be much less than a million.

So the idea is to remove numbers occurring 0 or 1 times very quickly, and hoping the number of duplicates is much less (it’s less than 500,000 in the worst case, but likely less).