-3

For my project, I need to map integers so that inputting int X will output int Y where both X and Y are defined during runtime.

I've used Dictionary<int,int> in .NET but its memory use is too high and the access speed is too long for my case.

Instead, I want to make a custom class that essentially does what a Dictionary<int,int> does in that it maps an integer key to an integer value.

What is the underlying concept behind the Dictionary and how would I implement something like it?

Note: I don't need to remove elements or check if the collection contains an element. I only need to be able to define input-output pairs and access the outputs with inputs.

closed as too broad by amon, user40980, durron597, GlenH7, user22815 Aug 23 '15 at 23:49

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • So, you want to code a Dictionary, that isn't a Dictionary, but behaves like a Dictionary, without the memory use of a Dictionary that is somehow faster than O(1)... but isn't a Dictionary. Did I get that right? – user40980 Jul 14 '15 at 1:45
  • No, I want to code something that accomplishes one of the things a Dictionary accomplishes. – JPtheK9 Jul 14 '15 at 2:01
  • 1
    The thing you are asking for is a Dictionary. Remove, check, and contains are just bits you get on the side that come with the underlying data structure. ContainsKey is a trivial tweak to TryGetValue. Look at the reference code and see if you can make it faster or take less memory (I assure you that if you are able to do one, you will pay a heavy price for it in the other). – user40980 Jul 14 '15 at 2:09
  • 2
    Maybe you can use Binary Search Tree. It will use way less memory but it will be slower to access values (but can be faster to access sequential data). BTW which language are you using? Maybe you can use a compiled language instead of scripting language. – Mandrill Jul 14 '15 at 2:17
  • @MichaelIT I'd rather not prune through the 1148 lines of code in the Dictionary's source code. In any case, it'll be fun and edifying to make my own map. – JPtheK9 Jul 14 '15 at 2:24
4

This answer is merely provided to reduce the frustration. In general, a person is better advised to learn how to conduct performance benchmarking properly before asking such a question.

If your "keys" exclusively consist of consecutive integers, you can use an integer array. Zero-based consecutive integers can be used as array index as-is. Non-zero-based consecutive integers may require an index value adjustment before using it with an array.

Even if the keys are not strictly consecutive, in that there are a small amount of holes (unused integer values between the minimum and maximum keys), it might still be beneficial performance-wise to use an array.

Remember that using an array makes your code fragile (more easily broken) to changes. Therefore, carefully analyze your project's current and future needs, and document the limitations inside your code comments, or somehow make them obvious to your project's users.

If there is some magic mathematical functions that map your integer keys into your lookup values, test to see whether that will be faster.

If your dictionary is constructed incrementally (adding keys one by one), consider using the Dictionary constructor with the size preallocation option, with an estimate of the maximum size needed. This reduces the time spent in reallocating and rehashing.

As pointed out in others' comments, you can benchmark with SortedDictionary (docs), which is typically, but not guaranteed to be a binary search tree.

If you know that the distribution of your integer keys may have unusual statistical distribution characteristics (for example, all of your keys are even-numbered, and so on), you may have to implement a workaround:

  • Depending on the Dictionary implementation, a workaround might not be necessary if it is already implemented from within.
  • Otherwise, you will need to apply a "key diffusion / avalanche function" to your integer keys, and use the modified key as a hash table index inside a typical "modulo-N" hash table.
    • A typical good choice (for hash tables) is the MurmurHash3 function.

A sorted int-int dictionary that is initialized up-front and never changed can be re-implemented as an array of integer pairs, and lookup can be performed with binary search.

If the int-int mapping comes from some mathematical functions that has monotonic trends, it might be possible to perform the table lookup faster than binary search.

1

I looked at the source code of the dictionary and noticed the use of "buckets". I'm not exactly sure how a dictionary sorts objects into buckets but it's a simple task with integers.

The main problem, I've logiced, is converting the input into an index that's small as possible yet doesn't collide with other inputs' indexes to make the array the outputs are stored in as small as possible, which is where buckets come in.

If the input is 255, the array can't be that large to store the output in the index of 255. Instead, operations are done on the number to determine where its output is stored.

Here's my implementation. It's optimized for my particular use because the largest key is 255.

public class FastMap {
    //8 buckets because the maximum key is 255
    public int[][] Buckets = new int[][8];

    public void Add (int input, int output)
    {
        //Finding out which bucket output will be assigned in
        int bucketIndex = input % 32;
        //Finding out the index inside of the bucket the output will be assigned to
        int innerIndex = input / 32;
        //Dropping output into the necessary bucket
        int[] bucket = Buckets[bucketIndex];
        if (bucket == null) 
        {
            bucket = new int[8];
            Buckets[bucketIndex] = bucket;
        }
        bucket[innerIndex] = output;
    }
    public int GetValue (int input)
    {
        return (Buckets[input % 32][input / 32]);
    }
}

I'm going to be playing with this more but already, my implementation out-performs Dictionary<int,int> in both memory use and performance.

  • 5
    The reason your question was unanswerable was because you failed to mention the 255 constraint. – Robert Harvey Jul 14 '15 at 2:57
  • 2
    Chain bucket hash collision resolution. – user40980 Jul 14 '15 at 3:30
  • 2
    How the hell is a Dictionary's memory usage too high if you only have 255 int,int pairs? That is using somewhere around 2K. – Telastyn Jul 14 '15 at 11:39
  • 1
    @Telastyn I have about 2000 of those dictionaries. – JPtheK9 Jul 14 '15 at 17:55
  • 1
    @JPtheK9 - oh no! 4 meg! That is breaking the bank! – Telastyn Jul 14 '15 at 19:25

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