-2

I have a list of around 2 billion distinct numbers stored in memory for some computation. Currently, every time I need to add a new entry I have to search the entire list for a potential duplicate.

I have 18 digit, 2 billion numbers to be stored in memory. Some of the numbers are repeated. So, I want to load new number in the memory and ignore if the number already exists. Right now, I append the number in the list if it does not exist already.

This process of linear scan of the already existing number is taking long time. What can I do to get around this performance problem?

5
  • 1
    Unclear what help you need. Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it’s hard to tell what problem you are trying to solve or what aspect of your approach needs to be corrected or explained. See the How to Ask page for help clarifying this question.
    – gnat
    Jan 26, 2015 at 10:40
  • Please See, I have 18 digit, 2 billion numbers to be stored in memory. Some of the numbers are repeated. So, I want to load new number in the memory and ignore if the number already exists. Right now, I append the number in the list if it does not exist already. This linear scan of the already existing number takes too much time.
    – Saurabh
    Jan 26, 2015 at 10:45
  • 4
    docs.python.org/3.5/library/bisect.html
    – Hey
    Jan 26, 2015 at 10:45
  • 1
    Sort them, then do a binary search. Jan 26, 2015 at 15:12
  • set is a better option than trying to sort in memory or using bisect. set gives you uniqueness directly, and like bisect, it sorts on insertion. Jan 27, 2015 at 0:15

3 Answers 3

1

Linear search of 2 billion numbers is going to be painful. On average, you'll scan almost a billion numbers before finding the one you want. Even if the numbers are in memory, that's got to take some time.

A better approach is to sort those numbers as you load them into memory and then use a Binary Search algorithm to quickly find the number you want in O(log n) time.

I'm not going to repeat Wikipedia's excellent write up of the algorithm here, but the general idea is to sample the middle of the list and compare it to the number you're looking for. If your number is higher, you can immediately discard the smaller half of the list and try again with what's left.

  • Your first sample would either find the number or eliminate 1 billion numbers.
  • Your second sample would either find the number or eliminate 500 million numbers
  • Your 3rd sample would either find the number or reduce the search set to 250 million numbers.

... and so on. As you can see, this converges on a solution (either the number is found or you know it's not there) very quickly. There's the overhead of initially sorting the numbers, but that's peanuts compared to the time you'll save on the search.

If you can store the numbers on disk sorted, you'll be even that much more ahead of the game.

1

You could use a hash table using the number itself as the key.

This means lookups and insertions would both be constant in time. If you know you have approximately two billion records you can pre-allocate that much space ahead of time so resizing is not an issue.

0

Use a set.

It has many of the semantic properties of list, but only stores unique values. To be honest, I have am unsure if it will perform reasonably for billions of elements, but it is backed by hash tables, and I have successfully used it to do unions and intersections of sets with over 10 million entries.

Your Answer

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

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