Dictionary style look up for millions of keys corresponding to a small set of values?

Question

I have a number of indices.

There is a particular group that corresponds to a range of indices

For example:

Range      Group

0-100        A
101-220      B
221-543      C
 ...        ...
3K-40K       DF

I need a way to look up a corresponding group, given a particular index. For example, I need a method:

(Group)groupForIndex:(index)

So if I called groupForIndex:(115) , the result would be B

I'm looking for a way to improve on what I have now.

I won't use just an NSDictionary (or map), since that would be an entry for every id, which could be millions, and would be a waste of space since many keys would have the same value.

I decided to use a combination of an array, and a dictionary. For each "upper limit", there will be an entry in the array

Example:

[0] = 100
[1] = 220
[2] = 543

And for each upper limit, there will be an entry in the dictionary

Key           Value
100             A
220             B
543             C

This way, using binary search, given an index I can look up an upper limit. Once I have the upper limit, I have the key for the dictionary.

This is the most efficient lookup scheme I could come up with. What would be a more efficient way to do this ?

Answer 1

Binary search in a (sorted) array is very fast, so your method looks good to me if the groups and indices are fixed, so that the array has to be built only once (or infrequently, compared to the number of lookups).

If the set of groups changes frequently then a different data structure (e.g. some tree) might be better suited instead of rebuilding the array on each change.

As I said in the comment, I would replace the dictionary by another array (of the same size as the first one)

[0] = "A"
[1] = "B"
[2] = "C"
...

and then just map the index found in the first array to the corresponding group via the second array.

This may be marginally faster, and may be easier to maintain because the "upper limits" for each group are not stored in two places.