Fastest C# collection for searching by property
c#, collections, optimization, search
Solution
The ranges do not overlap, but may be sparse.
If I'm understanding correctly, this means that if you sort them by StartRange, and then identify the first item with `value >= d.StartRange`, you can immediately know that you've either found your item (if `value <= d.EndRange`), or there is no match, right?
So you can cut your time in half just by doing this:
public MyClass Lookup(long value){
var candidate = _set.FirstOrDefault(d => value >= d.StartRange);
if(candidate != null && value <= candidate.EndRange)
{
return candidate;
}
return null;
}
And, since searching in a sorted collection can easily be done in `O(log n)` time, you should be able to get significant performance gains with just a binary search. Here's some sample code that should get you on the right track.
List<MyClass> _set = new[]{
new MyClass{StartRange = 18, EndRange = 18},
new MyClass{StartRange = 10, EndRange = 15},
new MyClass{StartRange = 20, EndRange = 21}
}.OrderBy(m => m.StartRange).ToList();
public class StartRangeComparer : IComparer<MyClass>
{
public int Compare(MyClass first, MyClass second)
{
return first.StartRange.CompareTo(second.StartRange);
}
}
StartRangeComparer startRangeComparer = new StartRangeComparer();
public MyClass Lookup(long value){
var index = _set.BinarySearch(new MyClass{StartRange = value}, startRangeComparer);
int candidateIndex = index >= 0 ? index : (~index) - 1;
if(candidateIndex < 0)
{
// the given value is before any start-ranges in the list
return null;
}
MyClass candidate = _set[candidateIndex];
if(candidate.EndRange >= value)
{
return candidate;
}
else
{
return null;
};
}
Problem
I have the following simple class: ``` public class MyClass{ public long StartRange { get; set; } public long EndRange { get; set; } public int Id { get; set; } } ``` I need to store many, 10^5 to 10^6, of these in a in-memory cache. There will be a single write to this cache at app start and many reads. This cache will be accessed in an ASP.NET environment, so many threads. I need to lookup a row in this cache where my value is between StartRange and EndRange inclusive. The ranges do not overlap, but may be sparse. Simplest way I have found to do this is the following: ``` public MyClass Lookup(long value){ return _set.FirstOrDefault(d => value >= d.StartRange && value <= d.EndRange); } ``` I have tried this with storing the set as `IOrderedEnumerable<T>` and `SortedSet<T>`. The SortedSet is an order of magnitude faster. `HashSet<T>` is slightly faster than the SortedSet somehow. Any suggestions on the most efficient collection class to use or a better lookup would be most appreciated.