CODEWITHSUNDEEP
c#collectionslookup-tables
Leonid
Leonid

Reputation: 81

Alternative to Dictionary for lookup

I have requirement to build lookup table. I use Dictionary It's contain 45M long and 45M int . long as key and int as value . the size of collection is (45M*12) where long is 8 byte and int is 4 byte The size about 515 Mbyte . But in fact the size of process is 1.3 Gbyte . The process contains only this lookup table. Mat be, is there alternative to Dictionary ??

Thx

Upvotes: 3

Views: 1131

Answers (5)

Henk Holterman
Henk Holterman

Reputation: 273169

How much effort are you willing to spend?
You could use a 

KeyValuePair<long,int>[] table = new KeyValuePair<long,int> [45 M];

then sort this on the first column (long Key) and use a binary search to find your values.

Upvotes: 3

hatchet - done with SOverflow
hatchet - done with SOverflow

Reputation: 16259

if your range is limited to max long values of 10^12, then a problem in regards to space is that you must use longs because you only need a few bits more than an int can hold. If that's the case you could do something like this: Store your data in an array of 512 Dictionary 

 var myData = new Dictionary<int,int>[512];

to reference the int associated with a long value (which I'll call "key" for this example), you would do the following:

myData[key & 511].Add((int) (key >> 9), intValue);
int result = myData[(int) (key & 511)][(int) (key >> 9)];

Just how many dictionaries you create and the number of bits used in the bit fiddling might need to be adjusted to fit the true contraints of your data. Using this approach would reduce your memory usage by about a third

Upvotes: 1

Servy
Servy

Reputation: 203802

Dictionaries have an underlying array that holds onto the data, but the size of the array must be larger than the number of items you have, this is where the lookup speed of a dictionary comes from. In fact, the size of the underlying array should be quite a bit larger than the number of items (25+%). Combine this with the fact that as you're adding items this underlying array is being de-allocated and recreated (to make it larger) you probably have a fair amount of memory ready to be garbage collected (meaning if you actually need more memory the GC will reclaim it, but since you currently have enough it's not bothering to).

Is this Dictionary consuming more memory than you can possibly allow it to, or are you just curious why it's more than you thought it would be? There are other options available to you (other answers and comments have listed some) that will use less memory but also be slower. Are you running into out of memory issues?

Upvotes: 1

Chris Shain
Chris Shain

Reputation: 51309

Another approach, assuming that the data is static: use two sorted arrays- one of long and one of int. Make sure that item at index N in one is the value for the key at index N in the other. Use Array.BinarySearch to find the key values that you are looking for.

Upvotes: 0

Martin Ernst
Martin Ernst

Reputation: 5679

You could use a SortedList instead of a Dictionary which will be more memory efficient but may be marginally less CPU efficient, ignoring issues about measuring memory and why you need to load so much data in 1 go in the first place :)

Upvotes: 1

Related Questions