CODEWITHSUNDEEP
c#sorting
Fredou
Fredou

Reputation: 20100

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

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?

Upvotes: 2

Views: 275

Answers (3)

Fredou
Fredou

Reputation: 20100

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

Upvotes: 0

spender
spender

Reputation: 120450

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();

Upvotes: 4

Marc Gravell
Marc Gravell

Reputation: 1062755

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.

Upvotes: 9

Related Questions