7

I need to check whether an ID (a long integer) is in a list of ~10,000 IDs. I need to do this about 10^9 times over on a loop, and speed is relatively important. Is using a c++ set the quickest way to do this? Something like:

set<long> myset;

// (Populate myset)

long id = 123456789;

if(myset.find(id) != myset.end()) {
     // id is in set
}

Or is there a quicker way?

3
  • Unless you want to write your own data structure specifically optimized only for your program, then yes, this is the fastest way. Mar 9, 2011 at 14:01
  • 3
    If the population of the list is a one time activity and then there are multiple searches on the list, then binary search is the way to go as pointed out by @David. It offers a complexity of log2(n) (even in the worst case scenario). Only drawback is that the list needs to be sorted. Mar 9, 2011 at 14:05
  • Sorting 10000 numbers take no time at all compared to a billion searches. I would go for a vector<long>, which is way more compact than a set. Each set node generally contains three pointers in addition to the data. That increases pressure on the cache.
    – Bo Persson
    Mar 9, 2011 at 15:24

5 Answers 5

17

The quickest way, if your long has a limited range, is a bitmap (e.g. vector<bool>). If that's not doable, a unordered_set (hash_set) should be attempted. And if that keeps hitting worst-case, then use a set

8
  • @Frerich: It'd need to be measured. Cache thrashing vs the few extra operations.
    – Erik
    Mar 9, 2011 at 14:12
  • @Erik: Indeed, I just tried it; the std::vector<bool> variant is much faster with MSVC10 (compiling using /O2). I take it all back and claim the opposite. :) Mar 9, 2011 at 14:24
  • I'm not completely sure I understand the bitmap suggestion - do you suggest populating a vector<bool> (or similar) with an entry for every possible value of the long? I'm not sure this would be feasable given my IDs go up to about 1,000,000,000. But then I did ask for speed not space! I think the unordered_set sounds like the best suggestion. Mar 9, 2011 at 14:25
  • nick: If your IDs fall within a certain range, it may be feasible to use a vector<bool> (1 bit per element). 1 billion bits would be 256MB. If your ID's e.g never go below 900'000'000 then you'd only need a vector with 100 mill bits though.
    – Erik
    Mar 9, 2011 at 14:28
  • Also, if you have 1 bill possible IDs, but just 10k actual, a custom data structure (e.g. array of pointer to vector<bool>) where each array element covers e.g. 64k IDs and is NULL if all IDs in this subrange are not present. It may be worth the trouble to get constant-time access for this.
    – Erik
    Mar 9, 2011 at 14:32
4

Hm, depending on how you generate the numbers and how many there are, it might be faster to use an std::vector ,sort it (you can even keep it sorted while inserting the numbers), and the use binary search to check if the number is in there.

Generally, a set works fine, but there are tradeoffs. The vector has less memory overhead, and since all numbers are stored in a continuous block of memory, it might outperform a set in some situations, but you would have to test that.

3
  • Sounds to me exactly like what std::set is providing?
    – ypnos
    Mar 9, 2011 at 14:06
  • 1
    @ypnos: It is, with regard to complexity. However, which is faster in practice depends on other factors as well. For some sizes a naive search from begin to end could be the fastest approach. Mar 9, 2011 at 14:09
  • 3
    @ypnos - externally they work the same, internally the set is probably a tree structure which is probably suboptimal for your specific case
    – sdg
    Mar 9, 2011 at 14:09
1

You can build a hash table and check in O(1) if the ID exist.

3
  • I might be wrong but the computation of the hash + searching the hash in the list probably isn't done in constant time. Or am I missing something ?
    – ereOn
    Mar 9, 2011 at 14:19
  • 1
    @ereOn: The calculation of the hash should happen in constant time, and the 'searching' is just putting that hash value into an array index, that's how lookup tables work.
    – Xeo
    Mar 9, 2011 at 14:32
  • 1
    @Xeo: In (hopefully!) a few cases though, the hash function will cause collisions, so you're doing an array index and then traversing a single-linked list. So you have amortized constant time lookup (whereas a real lookup table gives real constant time). Mar 9, 2011 at 15:17
0

The standard, for best intentions, decided that vector<bool> should be specialized to be implemented as a bitset.

A bit-set is fast enough, and you have the choice also of std::bitset which is fixed size, and boost::dynamic_bitset of which the size is runtime defined, and is built on top of vector<unsigned int> anyway (It may be a template on what integral type is used).

There is no point optimising further to save you some bit-twiddling so the suggestion would be to use one of these.

By the way, I have seen a "scattered" bitmap, whereby if the value falls within a certain range it uses one, otherwise it will use a tree-style lookup. (This technique can also be used for Z-table (normal distribution CDF type) functions where you "cache" the table in memory for up to 95% or 99% of the density and use the slow-calculation for the extreme values (and I once actually had to do that).

0

If you really want to push it to the top, you also have the option to use a two stage approach.

  1. Use a bloom filter or similar probabilistic algorithm to find out if the value is definitively NOT in the set or "maybe" in the set.
  2. To see if step 1 produced a false positive, you then need to execute your more costly second stage only to those not filtered out with step 1. Over your many (you mentioned 10^9) queries, you should be done more quickly (if not too many queries are a hit...).

See http://en.wikipedia.org/wiki/Bloom_filter for details. Also see: Search algorithm with minimum time complexity

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.