Reputation: 3512
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
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:
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
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