trying to figure out how to do a fast complex sorting without LINQ

Question

I guess I'm too used to use LINQ but this is slow, I did use a profiler and it consume 65% of the time for what I'm trying to do

var unlock = Locked.OrderBy(x => x.Weight) //double
                   .ThenByDescending(x => x.Stuff?.Level ?? 100) //int
                   .ThenBy(x => x.Penalty) //double
                   .FirstOrDefault();

Locked is a list, I know the sort will change the list but I don't really care, I just want to make it work (if possible), the code below doesn't give the same result as the LINQ above;

Locked.Sort(delegate (Node a, Node b)
{
    int xdiff = a.Weight.CompareTo(b.Weight);

    if (xdiff != 0) return xdiff;

    var aStuff = a.Stuff?.Level ?? 100;
    var bStuff = b.Stuff?.Level ?? 100;

    xdiff = -1 * aStuff.CompareTo(bStuff);

    if (xdiff != 0) return xdiff;

    return xdiff = a.Penalty.CompareTo(b.Penalty);
});

var unlock = Locked[0];

first thing is, is it possible with the List.Sort to do that complex sorting? asc / then desc / then asc ?

if yes, where is my error?

next is, is there a faster way of doing what I'm trying to do?

It would be awesome if you could provide a [mcve] (with sample data) so we can repo the issue at our end. — mjwills, Jul 04 '18 at 23:20
Linq is usally faster than any other method. So where is the data coming from? Also if you watch Task Manager while sort is being performed is memory being swapped? If the data is coming from a DataBase like SQL Server consider using a stored procedure to perform the sort. Also consider putting results into a view. — jdweng, Jul 04 '18 at 23:21
@Fredou I suspect the lack of a [mcve] may be part of the issue. If you provide a solution that can be easily copied and pasted into a console app and run, then people can debug it quickly and try and spot the issue. In effect, you make it easy for people to help you. For me to verify your above code I need to create a few classes with the relevant properties _and hope I defined them the same way you do_. The friction is too high - so people don't bother trying it. — mjwills, Jul 04 '18 at 23:42

score 9 · Accepted Answer · answered Jul 04 '18 at 23:19

9

If you're just after the "first or default" (min/max), you don't need to sort - you can do this in a single O(N) pass. Pick the first item and store it in a variable; now loop over all the other items in turn: if it is preferable by your criteria: shove it in the variable. When you get to the end, you have your winner.

answered Jul 04 '18 at 23:19

Marc Gravell

1,026,079
266
2,566
2,900

very good point, i'm making something easy ... complex, always good to have a second opinion! – Fredou Jul 04 '18 at 23:23
for my own personal learning, can the list.sort replace the linq? (without firstordefault() ( – Fredou Jul 04 '18 at 23:25
@Fredou they do different things, so... probably not fair to compare – Marc Gravell Jul 05 '18 at 14:40

spender · Answer 2 · 2018-07-05T01:12:30.080

4

You could create a custom comparer:

var comparer = Comparer<SomeItem>.Create((a, b) => 
    a.A == a.B 
        ? a.B == b.B 
            ? a.C == b.C 
                 ? 0 
                 : b.C - a.C //the order of these subtractions will affect the order
            : a.B - b.B 
        : a.A - b.A);

then use morelinq's MinBy:

IEnumerable<SomeItem> items = ...;
var best = items.MinBy(x => x, comparer); //.First() if it's morelinq3

...or if creating that comparer looks scary, I wrote a ComparerBuilder library for making it a bit easier:

var builder = new ComparerBuilder<Item>();
var comparer = builder
    .SortKey(x => x.A)
    .ThenKeyDescending(x => x.B)
    .ThenKey(x => x.C)
    .Build();
var selectedItem = items.MinBy(x => x, comparer).First();

edited Jul 05 '18 at 01:12

answered Jul 04 '18 at 23:38

spender

117,338
33
229
351

`MaxBy` is a great suggestion. – mjwills Jul 04 '18 at 23:45
1

@mjwills Yeh, but writing the comparer is a PITA. Makes me think that a ComparerBuilder class might be useful that supports the same syntax as OrderBy and OrderByDescending. Might give it a crack now. – spender Jul 04 '18 at 23:47
1

@mjwills That was a fun project before bedtime :) https://github.com/biggyspender/ComparerBuilder/blob/master/ComparerBuilderTest/UnitTest1.cs – spender Jul 05 '18 at 00:57
@Fredou It's basically the same technique (and complexity) as that outlined by MarcGravell, but giving you something reusable at the end. – spender Jul 05 '18 at 13:06

score 0 · Answer 3 · answered Jul 05 '18 at 12:33

based on Mark answer I came up with this;

    Node unlock = null;
    Node locked = null;

    if (Locked.Count > 0)
    {
        unlock = Locked[0];
        for (var i = 1; i < Locked.Count; ++i)
        {
            locked = Locked[i];
            if (unlock.Weight > locked.Weight)
            {
                unlock = locked;
            }
            else if (unlock.Weight == locked.Weight)
            {
                var unlockStuffLevel = unlock.Stuff?.Level ?? 100;
                var lockedStuffLevel = locked.Stuff?.Level ?? 100;

                if (unlockStuffLevel < lockedStuffLevel)
                {
                    unlock = locked;
                }
                else if (unlockStuffLevel == lockedStuffLevel )
                {
                    if (unlock.Penalty > locked.Penalty)
                    {
                        unlock = locked;
                    }
                }
            }
        }
    }

profiling show that this now take about 15% instead of 65% before, this seem to replicate the same result as the LINQ, I might refine it more later but for now I got what I wanted

trying to figure out how to do a fast complex sorting without LINQ

3 Answers3