0

I want to have around 20,000 complex objects sitting in memory at all times (app will run in indefinite loop). I am considering using either List<MyObject> and then converting the list to Dictionary<int, MyObject> or just avoiding List alltogether and keeping the objects in dictionary. I was wondering, is it pricey to convert list to dictionary each time i need to look up an object? What would be better? Have them stored as Dictionary at all times? Or have List and using lambdas to get the needed object? Or should i look at other options?

Please note, I don't need queue or stack behavior when object retrieval causes dequeuing.

Thanks in advance.

Dimitri
  • 6,923
  • 4
  • 35
  • 49

2 Answers2

2

Using a lambda lookup against the list is O(N), which for 20,000 items is not inconsiderable. However, if you know you'll always need to fetch the object by a known key, you can use a dictionary which is O(1) - that's as fast as algorithms go. So if there's some way you can structure your data/application so that you can base retrieval around some sort of predictable, repeatable, unique key, that will maximize performance. The worst thing (from a performance standpoint) is some complex lookup routine against a list, but sometimes it is unavoidable.

Rex M
  • 142,167
  • 33
  • 283
  • 313
  • Is there a way to have dictionary with two keys and lookup done by either of those keys? I tried Tuples but they require both values for the tuple items. – Dimitri May 18 '11 at 02:34
  • @Dimitri keep three dictionaries - `Dict`, `Dict` and `Dict`. Lookup as `commonDict[key2Dict[key]]` – Rex M May 18 '11 at 02:46
  • @Dmitri, depending upon your need, you could roll your own collection class to support this. See http://stackoverflow.com/questions/5382299/retrieval-of-items-from-custom-collection/5382893#5382893 for a possible idea. – Anthony Pegram May 18 '11 at 02:47
  • @Rex M: why not just 2 dictionaries (Dict and Dict )? – phoog May 18 '11 at 04:16
  • @phoog the values might not be reference types – Rex M May 18 '11 at 12:30
  • That's true, but if they are, two dictionaries would require roughly two thirds the memory and half as many key lookups compared to the three-dictionary approach. – phoog May 18 '11 at 15:02
  • Thanks everyone for the input. I have decided not to use two keys after all. – Dimitri May 18 '11 at 15:14
2

Regardless of what you're doing, if you need to access the List, then you are going to need to loop through it to find whatever you want.

If you need to access the Dictionary, then you have the option to use the key value to immediately retrieve what you are looking for, or, if you must, you can still loop through the Dictionary's Values.

Just use the Dictionary.

pickypg
  • 22,034
  • 5
  • 72
  • 84