4 ms·
How important is it that you get every unique line? Is it ok for some small percentage of unique lines to not appear in the output? How much memory do you hav
by davidst 16y ago
How important is it that you get every unique line? Is it ok for some small percentage of unique lines to not appear in the output?
How much memory do you have available?
The Bloom filter is a good way to go. Here is one possibility:
If you have 2 billion unique lines here's how much memory you need for a Bloom filter:
Error rate Memory
------------ --------
1 / thousand 3.35 GB
1 / million 6.70 GB
1 / billion 10.05 GB
1 / 10 billion 11.16 GB
1 / 100 billion 12.28 GB
If you have 12 GB available you can reduce the chance of missing a unique string down to almost zero.
- davidst 16y agoBTW, as you desire to decrease your error rate Cuckoo hashing starts to become an attractive alternative to Bloom filters: http://en.wikipedia.org/wiki/Cuckoo_hashing http://en.wikipedia.org/wiki/Cuckoo_hashing http://www.ru.is/faculty/ulfar/CuckooHash.pdf http://www.ru.is/faculty/ulfar/CuckooHash.pdf You can get your hash table utilization to almost 100%. If you're willing to accept a 64-bit hash function and you have 2 billion unique strings you'll need just over 16GB to do it all in one pass. A 64-bit hash is is just barely enough for 2 billion items. You might get a handful of collisions. Add more bits to reduce the probability. 128-bits would double the required size to 32GB but you're unlikely to ever see a collision in your life time. If 16GB or 32GB is too much you could do it in multiple passes. Make N passes through the text file and adjust the range of hash values you accept to test only 1/N each time. 8 passes through the original file with a generous 128-bit hash would take only 4GB of RAM. I have the feeling this is more work than you would want to put into the problem, though.