Take the 2-minute tour ×

I'm searching through a generic list (or IQueryable) which contains 3 columns. I'm trying to find the value of the 3 column, based on 1 and 2, but the search is really slow. For a single search, the speed isn't noticeable, but I'm performing this search on a loop, and for 700 iterations, it takes a combined time of over 2 minutes, which isn't any use. Columns 1 and 2 are int and column 3 is a double. Here is the linq I'm using:

public static Distance FindByStartAndEnd(int start, int end, IQueryable<Distance> distanceList)
    Distance item = distanceList.Where(h => h.Start == start && h.End == end).FirstOrDefault();
    return item ;

There could be up do 60,000 entries in the IQueryable list. I know that is quite a lot, but I didn't think it would pose any problem for searching.

So my question is, is there a better way to search through a collection when needing to match 2 columns to get value of a third? I guess I need all 700 searches to be almost instant, but it takes about 300ms for each which soon mounts up.

UPDATE - Final Solution #######################

I've now created a dictionary using Tuple with start and end as the key. I think this could be the right solution.

var dictionary = new Dictionary<Tuple<int, int>, double>();

var key = new Tuple<int, int>(Convert.ToInt32(reader[0]), Convert.ToInt32(reader[1]));
var value = Convert.ToDouble(reader[2]);

if (value <= distance)
    dictionary.Add(key, value);
var key = new Tuple<int, int>(5, 20);

Works fine - much faster

share|improve this question
Seems like the obvious problem of indexing. What if the values where in a dictionary and were sorted wouldn't that be faster? –  awright18 Oct 24 '12 at 9:06
Yes I think the 2 column key in a dictionary could be a good way to do it. I'll need to look into it –  e-on Oct 24 '12 at 9:30
add comment

5 Answers

up vote 5 down vote accepted

Create a dictionary where columns 1 and 2 create the key. You create the dictionary once and then your searches will be almost instant.

share|improve this answer
Ok, I've got this up and running now and it populates the dictionary fine. I'll add the code to the original post as an update. However, it doesn't recognise the key and can't find the right entry. Do you know how to create an equality comparer for this? –  e-on Oct 24 '12 at 12:01
@e-on: try the simplest solution - create the key as a string col1-col2. If this starts working try experimenting with e.g. Tuple. –  empi Oct 24 '12 at 12:20
Thanks empi - I got that working. As it turned, the problem wasn't with Tuple, but with some of my rows of data. It's a really fast solution now :) –  e-on Oct 25 '12 at 9:43
add comment

If you have control over your collection and model classes, there is a library which allows you to index the properties of the class, which can greatly speed up searching.


share|improve this answer
add comment

I'd give a hashSet a try. This should speed up things ;)

share|improve this answer
add comment

Create a single value out of the first two columns, for example by concatenating them into a long, and use that as a key in a dictionary:

public long Combine(int start, int end) {
  return ((long)start << 32) | end;

Dictionary<long, Distance> lookup = distanceList.ToDictionary(h => Combine(h.Start, h.End));

Then you can look up the value:

  Distance item;
  if (!lookup.TryGetValue(Combine(start, end), out item) {
    item = null;
  return item;

Getting an item from a dictionary is close to an O(1) operaton, which should make a dramatic difference from the O(n) operaton to loop through the items to find one.

share|improve this answer
add comment

Your problem is that LINQ has to execute the expression tree everytime you return the item. Just call this method with multiple start and end values

public static IEnumerable<Distance> FindByStartAndEnd
    (IEnumerable<KeyValuePair<int, int>> startAndEnd,
    IQueryable<Distance> distanceList)

        from item in distanceList
            startAndEnd.Select(s => s.Key).Contains(item.Start)
            && startAndEnd.Select(s => s.Value).Contains(item.End)
        select item;
share|improve this answer
Hi Jan, thanks for this - daft question, but how would I pass a KeyValuePair to the method? I was trying this, but getting an error: FindByStartAndEnd(new IEnumerable<KeyValuePair<5, 20>>, distanceList)? –  e-on Oct 24 '12 at 9:28
You create a List of KeyValuePair with all your start and end integers and pass it to the method. –  Jan P. Oct 24 '12 at 9:37
add comment

Your Answer


