[SOLVED] What collection should I use for combining fastest key retrieval, but also fastest sorted enumeration in c#?

Issue

Please can somebody recommend me some collection in c# (or maybe a hint how I can implement it myself) for storing key-value pairs, where I will always have at maximum let’s say 50 of those key-value pairs. But usually there are only something like 5-20 key-value pairs. And I need absolutely fastest retrieval of a value for a given key. First I thought about Dictionary, because it has retrieval access time of O(1). But still I am not sure about the overhead of using dictionary for such small collections. But I guess Dictionary provides the best speed even for small collections like these?

Then I have another requirement, I need to be able to tell the next bigger key for a given key (For example I have keys with values 2,4,6,8,10,11,12,15 and when I say let’s say 7, I need to be able to quickly tell, that the next bigger key than 7 is 8). So I thought about the collection of these keys to be sorted, then I would be able to quickly tell the next bigger key). I thought about using SortedDictionary then, but I found, it then have slower access speed O(log(n)), but would provide me this other benefit of finding next bigger key.

And by the way, through the whole use of this collection, it will never be modified, it just needs to be built at the beginning, which may be slow, it doesn’t matter for me the speed of bulding it. Also I don’t care for memory usage at all.

So for example, my solution could also as well combine Dictionary and let’s say SortedList. It would be 2 collections combined just to maximize that retrieval speed and also that "getNextBiggerKey" speed.

Or now I am also thinking about just storing nextBiggerKey in a value of that key-value pair. So it would give me next bigger key at least for those keys already in collection.

So does anybody have some good ideas please, how to totally maximize the performance in this situation?

UPDATE: Keys I am talking about are actually of Fraction type. But with low values, neither numerator, nor denominator would ever be greater than 256, so bytes should (with high probability) be enough for both of them.

Thanks sooo much for any help, it would be greatly appreciated 🙂

Solution

This answer assumes that the range of possible keys is small (a few thousands at most). In this case you could implement a solution based on a lookup table. Let’s say that the range of fractional keys is between 10 and 14, and includes halves and quarters. Also let’s say that you have 4 keys in this range with the values 10, 10 3/4, 12 1/2 and 13. First you’ll need a way to translate a key to an integer that will be used as an index in an array. In this case the translation function would be:

f(x) = (x - 10) * 4

So the key 10 is translated to the index 0, and the key 14 is translated to the index 16. Next you’ll need to construct an array with length 17 (from 0 to 16). Below is a table showing the values of this array:

|   Key   | Translated |  Index  |  Value  |
|---------|------------|---------|---------|
| 10      | 0          | 0       | 0       |
| 10 1/4  | 1          | 1       | 3       |
| 10 1/2  | 2          | 2       | 3       |
| 10 3/4  | 3          | 3       | 3       |
| 11      | 4          | 4       | 10      |
| 11 1/4  | 5          | 5       | 10      |
| 11 1/2  | 6          | 6       | 10      |
| 11 3/4  | 7          | 7       | 10      |
| 12      | 8          | 8       | 10      |
| 12 1/4  | 9          | 9       | 10      |
| 12 1/2  | 10         | 10      | 10      |
| 12 3/4  | 11         | 11      | 12      |
| 13      | 12         | 12      | 12      |
| 13 1/4  | 13         | 13      | -1      |
| 13 1/2  | 14         | 14      | -1      |
| 13 3/4  | 15         | 15      | -1      |
| 14      | 16         | 16      | -1      |

No let’s use this array to make some searches.

  1. Does the key 12 exist? We apply the translation function (12 - 10) * 4 and we get the index 8. The value of the array[8] is 10. 10 is different from
    8, so the key 12 does not exist.
  2. What is the next bigger key of the key 10 3/4? We apply the translation function and we get the index 3. The array[3] is 3, so the key exists, but we are not interested in that. We need to look at the next array element, the array[4]. This has the value 10, which is a translation of the key 12 1/4. So the next bigger key of 10 3/4 is 12 1/4.

Now that you have a way to search this structure by key, you can think about how to associate each key with a value, to end up with a proper dictionary. The simplest way could be to add another array in the mix, with equal length, storing the value of each key in the same index.

Answered By – Theodor Zoulias

Answer Checked By – Mary Flores (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *