Searching with Linq

Question

I have a collection of objects, each with an int Frame property. Given an int, I want to find the object in the collection that has the closest Frame.

Here is what I'm doing so far:

public static void Search(int frameNumber)
{
    var differences = (from rec in _records
                       select new { FrameDiff = Math.Abs(rec.Frame - frameNumber), Record = rec }).OrderBy(x => x.FrameDiff);

    var closestRecord = differences.FirstOrDefault().Record;

    //continue work...
}

This is great and everything, except there are 200,000 items in my collection and I call this method very frequently. Is there a relatively easy, more efficient way to do this?

Answer 1

What you might want to try is to store the frames in a datastructure that's sorted by Frame. Then you can do a binary search when you need to find the closest one to a given frameNumber.

Answer 2

var closestRecord = _records.MinBy(rec => Math.Abs(rec.Frame - frameNumber));

using MinBy from MoreLINQ.

Answer 3

you can combine your statements into one ala:

var closestRecord = (from rec in _records
                   select new { FrameDiff = Math.Abs(rec.Frame - frameNumber), 
                   Record = rec }).OrderBy(x => x.FrameDiff).FirstOrDefault().Record;

Answer 4

Maybe you could divide your big itemlist in 5 - 10 smaller lists that are ordered by their Framediff or something ?

this way the search is faster if you know in which list you need to search

Answer 5

I don't know that I would use LINQ for this, at least not with an orderby.

static Record FindClosestRecord(IEnumerable<Record> records, int number)
{
    Record closest = null;
    int leastDifference = int.MaxValue;

    foreach (Record record in records)
    {
        int difference = Math.Abs(number - record.Frame);
        if (difference == 0)
        {
            return record; // exact match, return early
        }
        else if (difference < leastDifference)
        {
            leastDifference = difference;
            closest = record;
        }
    }

    return closest;
}