CODEWITHSUNDEEP
c#searchdata-structures
ganeshran
ganeshran

Reputation: 3512

Fast In-memory search for multiple attributes

I have a list of in memory objects (around 50000-1 million) which have 6-7 properties (attributes).

the requirement is to filter this in-memory list with multiple attributes. A linear search allows me to do a O(N) seach on the list. Is there any faster way to do it with better data structure than a generic list?

I am using C#.NET 4.0.

Upvotes: 1

Views: 2574

Answers (3)

Bashir
Bashir

Reputation: 11

You can use a helper library named IndexedList, you can download it from http://indexedlist.codeplex.com/ With this library you can add indexes on any field(s) of your object then perform fast searches in your list. Default index implementation uses Dictionary for storing index data, you can change it too. I have created this library for my own projects then i published that as an open source project newly. I will be happy to hear your feedback about this library.

Upvotes: 1

Анатолий
Анатолий

Reputation: 2867

Best I can suggest:

  1. Make dictionary for each required attribute (separate dictionaries)
  2. When you search, lookup each required dictionary separately one by one and choose list of minimal size
  3. Iterate list of minimal size

If Attribute values without big amount of duplicates, this approach will be very usefull. But if each attribute has a lot of duplicates this approach will be very bad.

Possible improvement: each list into dictionary possible sort and after use it for binary search by one of attributes.

Upvotes: 0

dutzu
dutzu

Reputation: 3920

Just a few seconds ago i read this: http://blog.bodurov.com/Performance-SortedList-SortedDictionary-Dictionary-Hashtable/

Seems the SortedDictionary might be your best bet as searching goes but since you want to search by multiple attributes this drops so if you want a good balance between searching and inserting for that large amount of data maybe a SortedList will yield better results at the cost of memory usage.

Upvotes: 0

Related Questions