CODEWITHSUNDEEP
c#.netlinqsortingsql-order-by
Louis Rhys
Louis Rhys

Reputation: 35627

How to optimize LINQ OrderBy if the keySelector is slow?

I want to sort a list of objects using a value that can take some time to compute. For now I have code like this:

public IEnumerable<Foo> SortFoo(IEnumerable<Foo> original)
{
    return foos.OrderByDescending(foo => CalculateBar(foo));
}

private int CalculateBar(Foo foo)
{
    //some slow process here
}

The problem with the above code is that it will call calculate the value several times for each item, which is not good. The possible optimization is to use cached value (maybe a dictionary), but it will mean that SortFoo will have to clear the cache after each sorting (to avoid memory leak, and I do want the value to be recalculated on each SortFoo call).

Is there a cleaner and more elegant solution to this problem?

Upvotes: 3

Views: 5154

Answers (2)

ESV
ESV

Reputation: 7730

It appears that .OrderBy() is already optimized for slow keySelectors.

Based on the following, .OrderBy() seems to cache the result of the keySelector delegate you supply it.

var random = new Random(0);
var ordered = Enumerable
    .Range(0, 10)
    .OrderBy(x => {
        var result = random.Next(20);
        Console.WriteLine("keySelector({0}) => {1}", x, result);
        return result;
    });
Console.WriteLine(String.Join(", ", ordered));

Here's the output:

keySelector(0) => 14
keySelector(1) => 16
keySelector(2) => 15
keySelector(3) => 11
keySelector(4) => 4
keySelector(5) => 11
keySelector(6) => 18
keySelector(7) => 8
keySelector(8) => 19
keySelector(9) => 5
4, 9, 7, 3, 5, 0, 2, 1, 6, 8

If it were running the delegate once per comparison, I'd see more than just one invocation of my keySelector delegate per item.

Upvotes: 8

Dave Bish
Dave Bish

Reputation: 19646

Because each item is compared against other items multiple times in a sort, you can cheaply cache the computation at least one-per-item. If you're often running the calculation against the same values, Memoizing the function would be your best bet,

public IEnumerable<Foo> SortFoo(IEnumerable<Foo> original)
{
    return foos
        .Select(f => new { Foo = f, SortBy = CalculateBar(f) })
        .OrderByDescending(f=> f.SortBy)
        .Select(f => f.Foo);
}

This will reduce the calculations to once per item

Upvotes: 3

Related Questions