Efficient way to determine highest value (with or without offset)

Question

I'm currently using a SortedList in a loop to sort some values in descending order:

for(...)
{
    float rawValue;
    float offset;
    sortedList.Add(rawValue + offset, index);
}

I'm interested in finding out if sortedList[0] (i.e. the entry with the highest rawValue+offset) is also the highest entry if we had sorted the entries by their raw values without the offsets?

The obvious solution is to have another sortedRawValuesList populated in the same loop, but I think there are quicker and more memory efficient ways of achieving that?

Thanks!

Answer 1

Could you not simply keep track of the highest rawValue as you iterated? If the offsets change through each iteration, you would probably want to save the offset as well.

float highestRawVal = float.MinVal;
float offset_ForHighestRawVal = float.MinVal;
for(...)
{
    float rawValue;
    float offset;
    sortedList.Add(rawValue + offset, index);
    if(highestRawVal < rawVal)
    {
        highestRawVal = rawValue;
        offset_ForHighestRawVal = offset;
    }
}

if (highestRawVal + offset_ForHighestRawVal == sortedList[0])
    Console.WriteLine("They Match");

Then you could simply check afterwards if they match.

Answer 2

It's rather inefficient to add a bunch of values to a SortedList just to sort that data. You're effectively doing an "insertion sort", which is O(n^2). Most widely used sorting algorithms are O(n*log(n)).

On top of that, if you just need the max value you can loop over the data just once and compute the max in O(1) time.

To find the Max value simply use LINQ's Max function:

IEnumerable<X> data = ...;

float max = data.Max(item => doSomeComputation(item));

To get the item that generate the max value you can use MaxBy. (Unfortunately .NET doesn't ship it directly, you need to write/add it yourself.)

X maxItem = data.MaxBy(item => doSomeComputation(item));

public static TSource MaxBy<TSource, TKey>(this IEnumerable<TSource> source
    , Func<TSource, TKey> selector
    , IComparer<TKey> comparer = null)
{
    if (comparer == null)
    {
        comparer = Comparer<TKey>.Default;
    }
    using (IEnumerator<TSource> iterator = source.GetEnumerator())
    {
        if (!iterator.MoveNext())
        {
            throw new ArgumentException("Source was empty");
        }

        TSource maxItem = iterator.Current;
        TKey maxValue = selector(maxItem);

        while (iterator.MoveNext())
        {
            TKey nextValue = selector(iterator.Current);
            if (comparer.Compare(nextValue, maxValue) > 0)
            {
                maxValue = nextValue;
                maxItem = iterator.Current;
            }
        }
        return maxItem;
    }
}

Answer 3

Why not simply utilize LINQ to do this sort for you?

var sortedList = // Get List

var withOffsets = sortedList.Select(x => new { Original = x, Offset = x + offset }).OrderBy(x => x.Offset);

if(sortedList.First() == withOffsets.First())
   // True!