4

I'm aware there may not be a good solution to this problem. I'm looking for a fast algorithm that determines whether or not a value (let's say an integer) exists in a set of values, however I need the algorithm to also be fast if the value is not in the set. I.e.: Most methods I can think of right now that determine if a value is in a list will take longer to determine that it is not as they will not exit early.

I've been experimenting with using the keys of an unordered set but found them to actually be rather slow to verify. I'm not really sure what's going on behind the scenes with this data type. I'm aware that a straight forward array search might be faster than looking up a key but the size of the array is not properly known yet, only that it will be very large.

Properties and assumptions:

  • Assume all the values are integers between 0 and N, where N is likely to be in the millions.
  • The list will need to be checked very quickly, several 100 times per millisecond, but usually roughly in the same place each time with only a gradual deviation in the target area.
  • There is no constraint on the preparation time available for setting up a data structure, i.e.: the list could be organised specially somehow before hand.
  • There will be no duplicate values in the data.
  • 9
    Hashing. (Comments must be 15 characters.) – Kilian Foth Apr 28 '15 at 7:27
  • 2
    unordered_map should not be slow at all; perhaps you are doing something wrong. Or could it be perhaps that you have an inordinate amount of duplicates and you have not stated so in the wording of the question? – Mike Nakis Apr 28 '15 at 7:32
  • 1
    What is the density of the set? (set size divided by the potential number of distinct values allowed in the set) If the density is very low, (and given that preparation time is not constrained), bloom filter comes to mind. – rwong Apr 28 '15 at 8:28
  • 1
    Given that you want to reject non-existing elements quickly, then a bloom filter is exactly what you need and you definitely want to use it in addition to whatever exact data structure you end up using. – user7043 Apr 28 '15 at 8:40
  • 1
    Just to be clear; hash tables and trees become more useful the more sparse your data. If your density really is around 0.2 (as in, 20% of numbers in the range are members), hash tables and trees are pointless. They will use at least 10x the memory of bit arrays and will be decidedly slower. – Artelius Apr 28 '15 at 10:36
11

If there is a known maximum N, you can use a Bit array for really fast lookup time.

Simply keep an array of size N/8 (rounded up) around, with each bit corresponding to a number, 1 if it is in the set, 0 if it isn't. Lookup the relevant bit to check whether a number is in the set.

If this is too slow, and you have the megabytes ("millions" doesn't sound very high), then just keep a boolean array of size N.

Edit: for much larger values of N this won't fit into memory, and you probably need some sort of hashing. It'd still be nice to use the fact that subsequent calls are likely to be close to each other, though.

So a sketch of an idea: use the number divided by 256 as the key, and store a 256-bit bit array as the value (for all the numbers that divide to this key). Store the most recently retrieved key and bit array. If the next call divides to the same key, you can look it up in the cache bit array immediately. The number 256 can be tweaked a lot, of course. I'm not sure this is actually faster than just using map without extra gimmicks, so profile it.

For large values of N it's going to depend on lot on the sparseness of the data; clearly if you have max N 10^12 and a lot of the values are in the set, then it's not going to fit into memory anyway.

  • 4
    Even if you have the megabytes, consider packing eight bits into one byte. Reading the packed table needs about three extra ALU instructions (table[i] versus table[i >> 3] >> (i & 7)). Because it is more compact, it will use the cache up to eight times more effectively, which will more than make up for the extra instructions if access is indeed "usually roughly in the same place each time with only a gradual deviation in the target area." – user7043 Apr 28 '15 at 7:45
  • The numbers will be very sparse but this could do the trick, especially due to the speed of look up. The millions was a lower bound, the problem would be possible to solve with millions of values. Probably more likely to expect between 10^9 and 10^12. Sadly this is not yet fully known. I'm going to experiment with implementing your answer. – sydan Apr 28 '15 at 7:49
  • 1
    If the numbers go to 10^12 then you need other things of course, but for the question as it stands (fastest way for values up to millions) then I think this is hard to beat. – RemcoGerlich Apr 28 '15 at 7:56
  • The vast range in the possible size of the data set is a problem. Nothing I'd very much like to narrow down. – sydan Apr 28 '15 at 8:05
  • Then off to hashes it is. – RemcoGerlich Apr 28 '15 at 8:06
4

You could generate a binary tree (radix tree aka trie). To prepare for the search, for each number in your array, starting with the least significant bit, if it is 0, you look to the left node. If it is 1, you look to the right node. You follow the tree until you find no more nodes, and from there you create the tree one node at a time.

To search, taking each bit, starting with the least significant bit, if bit is 0, go left. if bit is 1, go right. No node found? Your number isn't in the tree, you're done. Otherwise, continue with the next bit on that node. If you run out of bits and you are on a node, then you've found your number.

It takes O(nlog n) to construct binary tree and O(log n) to determine if any number exists. It should be faster than a traditional hash map, but it is also more restrictive so this implementation would only work with numbers.

The reason why you'd start with the least significant bit is to keep the table somewhat balanced (otherwise a good many of the numbers would likely start with 0). Hope that helps!

  • Hi Neil! I think I understand where you're going with this, I'm familiar with trees, but unfamiliar with how to setup this tree. Is each node a bit representing whether or not a number exists in the set or something else? – sydan Apr 28 '15 at 8:27
  • @sydan Let me expand my answer and I'll explain better. – Neil Apr 28 '15 at 8:28
  • Example: radix tree (en.wikipedia.org) – rwong Apr 28 '15 at 8:29
  • Faster than a traditional hashmap? Are you sure? You have only a heuristic argument guaranteeing balance, based on an implicit assumption, and unless you have a clever way to layout out the tree consecutively in memory, lookup will cause about log n cache misses, or in any case more than one (especially if the access pattern is n, n+1, n+2, ... because then search paths already diverge at the root node because you start with the lsb). – user7043 Apr 28 '15 at 8:37
  • @delnan I won't say that in the worst of cases for this algorithm or the best of cases for hashmap that there won't be an improvement in hashmap, however I can say this with confidence because hashmap is checking the entire number multiple times, while this doesn't even necessarily require that you check every single bit in the number. It is useful only in checking the existence of a number, not really for anything else. – Neil Apr 28 '15 at 9:04
1

I would try to go for the bitfield too, but if the data is sparse and the range too great to make this work, a splay tree might be a good data structure to use.

Splay trees are modified on each access (so they are not thread-safe, which could be an exclusion reason for you) to optimize repeated access to the same element. Often-used elements bubble to the top. If your access pattern really stays in the same area for a while then this could make for fast lookup in your case.

But this depends on usage pattern. You still have to traverse the entire tree height for non-existent elements.

0

We were told numbers could be up to about 10^12 and about 20% of numbers would be used. That is 2 * 10^11 numbers actually used. With these numbers, the best you can do is a bitmap of about 125 GBytes, and if you can't afford the RAM, an SSD drive and virtual memory will have to do. You should probably measure whether "normal" file access is faster than relying on virtual memory. Obviously a bitmap that exceeds physical memory will be slooooooow. It's still the fastest that you can do.

If the map is less dense then you can do it quicker. Say you have a billion numbers from 0 to 10^12. So on average a range of thousand numbers only contains one number. You could have a bitmap to represent the fact that "the range 128k to 128k + 127 contains at least one number". That takes 8 billion bits or one GB, fitting into RAM, so you check this map first, chance is 87% that you find there is no number, so whatever slower algorithm you wanted to use will only be used for one in eight numbers.

Obviously your access pattern will be incredibly important. If 99% of the time you are searching for numbers that are actually present then the method described above will be useless.

0

The most efficient and general-purpose solution I've come up with for this problem, and it works specifically for integers (though still widely applicable in my case since I refer to just about everything by index when using auxiliary data structures to accelerate searches), is what I call a "sparse bit tree". I don't know if there's a formal name for this data structure. It can perform set operations in better than linear time, without having to inspect all elements (bits) of both sets, since it can, say, skip over a million elements if it just finds a set bit (1) at the root level in both sets and know immediately that both sets have a million elements in common with a test for a single bit.

As a result it has a best case performance of something like Log(N) / Log(64), where it can find the set intersection between two dense sets containing a million elements each in 3-4 iterations, with each iteration only having to check one bit. The worst case scenario is N * Log(N) / Log(64), where it might have to perform around 3 to 4 million iterations to determine the set intersection between both sets, but that's still linear-time and it doesn't happen unless the data is very awkwardly sparse with no contiguous indices (like a case where every integer in the set is an even number).

I wouldn't be surprised if someone else has already come up with the same idea long before me (if anyone knows the name if so, I'd much appreciate it). It's just something I made up and have been using for ages (the original version used 16-bit words and has evolved towards 64-bit).

enter image description here

It is not the most trivial data structure to implement, but has served me well as the backbone for so many projects. The diagram should give enough of an idea to implement for those who are interested. It can be used as an integer/index set with set operations. Unlike most sets, it can also be used to rapidly find an unused integer/index (rapidly find the first integer not in the set) using ffs instructions with the complement and figure out what index to to insert an element to in an array with "holes" in it to allow rapid removal and to avoid invalidating indices to other elements, etc.

I actually found it so useful that I think it has shaped the way I design codebases against it to the point where I now want to store indices to everything stored in central arrays and avoid pointers when possible. There's that whole tendency to see everything as a nail when you're wielding a hammer, but in this case it's an extremely efficient hammer that trivializes getting a performant solution. I ended up finding even more use for it than ever before after working my way towards entity-component systems which want to perform set intersections all the time ("find all entities that implement X,Y,Z components").

Loop Acceleration

The rapid linear traversal as noted on the bottom right is a huge one for me, since I have many loops in many projects I've made where they inevitably can't do better than linear (for each element in the set, do some light work type loops). This often makes the loop cheaper than iterating through an array of indices because it can often do it while accessing so little memory when a single bit set towards the top of the hierarchy can indicate that indices in the range, [8388608,16777216) are in the set by just inspecting one bit, e.g., as opposed to over 8 million bits or, worse, over 8 million integers.

As a result I often use this structure even when I don't need a set as a replacement for, say, an array of integers (int[]) or vector<int> if I'm going to be looping over the result many times over. It serves as a loop accelerator when the indices consist predominantly of contiguous ranges since in those cases, it's much faster to iterate through than an array of integers. Even disregarding that, it also means the loop will access the original elements in sorted order which is typically the most cache-friendly access pattern as opposed to sporadic random access you might get by just looping through an array of unsorted indices.

Sparse Data

And because it's reasonably well-suited for sparse data, you don't have to worry too much about hogging a boatload of memory if the indices/integers are very sparse and have a huge range (as long as it's not too huge, a range in the millions is perfectly fine, billions or trillions might call for something better suited for extremely sparse representations).

Temporal Locality

Now funnily enough to test the presence of a single integer, it has a worse algorithmic complexity with a worst case of something like log(N) / log(64) iterations (or bitwise operations) than a simple huge array of bits (bitset) for which you can test a specific bit in constant time with a single bit operation and some arithmetic (or a bit shift and a bitwise and). However, it tends to still be faster because of the temporal locality associated with being able to often determine whether an nth bit is set without drilling down to the leaves, especially in cases which the indices are reasonably dense (for super sparse cases, you might just go straight to the leaf nodes and treat this like it's a gigantic array of bits instead of a tree).

-2

Just to add a suggestion to the other solutions.

In the biomedical world we often search for specific strings of data (ie genetic patterns).

Research has shown that attacking the parent string in the reverse direction, the last entry to the first, is faster that going forward through the string.

I guess this is some how related to slurping in all the data into memory, it then being quicker to pop the last entry off the end.

I remember being really chuffed when I had this idea, I thought I was thinking well outside the box.

I expect the same principle would apply to simple arrays also where the search time is proportional to the size.

  • this reads more like a comment, see How to Answer – gnat Apr 28 '15 at 9:50
  • 1
    DaveM, this is well-known behaviour due to CPU caches which cannot be leveraged here. The effect only works immediately after reading data into memory, but OP has a fixed set of data which will be queried over and over. – Artelius Apr 28 '15 at 10:04
  • @gnat true, I should have asked for a mod to convert it to a comment. – DaveM Apr 29 '15 at 10:17
  • @Artelius Cool, I've learnt something, in 2 somethings, with the info for a fixed data set. This is why I love SO. As I said, I was really chuffed when I thought it up on my own... and felt I was rightly chuffed when I descovered it was quite a high end solution to the problem, well outside of my principle domain. – DaveM Apr 29 '15 at 10:22

protected by gnat Oct 26 '17 at 5:16

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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