Geek Answers Handbook

Huge data set in memory. Requires fast search on integer property Id

I have a huge set in memory (e.g. ~ 100K entries) of simple CLR objects of a certain type. This type has the public property int Id {get; set;}. What is the best .NET framework that contains this huge dataset to provide quick access to any element by its identifier? More specifically, this data set is supposed to be used inside a loop to find an item by identifier, so the search should be performed as quickly as possible. The search might look like this:

// Find by id
var entity = entities.First(e => e.Id == id)

IEnumerable-based structures such as collections and lists will go through each data item until a search is found. What are the alternative ways? I believe that there should be a way to do a search for sorted arrays by identifier, like searching for an index in databases.

thank

Test results : FYI: The dictionary is not just fast, it is simply incomparable. My little test showed an increase in performance from about 3000+ ms (calling First () on IEnumerable) to 0 ([index] in the dictionary)!

+5
source share
5 answers

I would go with : Dictionary<TKey, TValue>

var index = new System.Collections.Generic.Dictionary<int, T>();

where Tis the type of objects you want to access.

-, .. - ( ) - . , , , — .

  • , index.Add(entity.Id, entity);

  • , , index.ContainsKey(id).

  • , index[id].

+8

Dictionary<TKey, TValue>, TKey - int, TValue - YourEntity.

var dictionary = new Dictionary<TKey, TValue>();
dictionary.Add(obj1.Id, obj1); 
// continue

, , ,

var dictionary = list.ToDictionary(obj => obj.Id, obj => obj);

: . , (, Distinct() . , , ContainsKey , Add.

+4

, HashTable, , . <T> . , . , , -:

. :

  • HashTable ( , )
  • ConcurrentDictionary
+2

It depends on your data. If there is a ceiling to the number of objects that you have and there are not many missing objects (which means that you cannot have more than X objects, and you are usually close to X objects), then a regular array is the fastest .

T[] itemList = new T[MAX_ITEMS];

However, if one of these two conditions is not met, then probably the best option is IDictionary.

Dictionary<int, T> itemList = new Dictionary<int, T>();
+1
source

More articles:


All Articles