1
$\begingroup$

Given a 64 bit positive integer. How to determine in the most efficient way whether the given integer has ever been seen or not?

Implementation in C++11 (Please do include this fact, while suggesting your opinions)

Intent: I am generating numbers randomly, by flipping one bit at a time. I need to check every time on generation of a number whether it has been previously generated or not? ex: 1,4,8,16,3,5,9,11,12, .... .

Current Solution:
1.I can create an unordered_map. However, I would be wasting memory for storing the value part which is boolean in this case. And also hashing isnt the cheapest operation and also their is a penalty of rehasing.

  1. Can create a list and keep it sorted. Too expensive operations --Sorting and lookup.
$\endgroup$
1
$\begingroup$

You could use a hashtable to keep track of all values you've seen before. (You could also use a balanced binary tree data structure, but it will probably be less efficient in practice, due to the overhead of the pointer traversals.)

If you don't mind occasional false positives, you could use a Bloom filter, and that might be even more efficient -- at the cost of occasionally declaring "I've seen this number before!" when you actually haven't.

Questions about specific C++ libraries are off-topic here but can be asked on Stack Overflow once you know what data structure you want to use.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.