Elegant way to retrieve the index of the max element from a List in C#

Question

I am discovering the tools C# provides to work with collections.

Suppose I have a List of elements, and I want to retrieve the one that most satisfies a property. Basically a elements.Max(predicate), except that I am interested in the index of the best element. The reason I want the index and not the element itself is there might not be such element, and the type is non-nullable.

Writing a function doing this is trivial, but I am interested in using the expressiveness of the tools C# provides to get a solution that is both concise, clear, and optimal (O(n)).

At this point I have the following code, which still looks cluttered, and evaluates the property twice.

List<foo> elements;
private int getBest(object x)
{
  var indices = Enumerable.Range(0, elements.Count);
  return indices.Aggregate(-1, (best, next) =>
    (-1 == best || eval(x, elements[next]) > eval(x, elements[best])) ? next : best);
}

How can I make this piece of code better?

Addendum: I didn't put it in the code for the sake of clarity, but if eval() is below a certain threshold the element is discarded.

You should be able to cache the score of the best as well as its index, so you only have to do the property evaluation once. — zebediah49, May 24 '12 at 07:46
I think you'll find your answer [here](http://stackoverflow.com/questions/2471588/how-to-get-index-using-linq) — Marko Juvančič, May 24 '12 at 07:47
Presumably the only way there could not be such an element is for the list to be empty, or did you mean something else? — AakashM, May 24 '12 at 07:48
possible duplicate of [How do I get the index of the highest value in an array using LINQ?](http://stackoverflow.com/questions/462699/how-do-i-get-the-index-of-the-highest-value-in-an-array-using-linq) — Darin Dimitrov, May 24 '12 at 07:49
Makes sense. Following the approach in the proposed duplicate will still work, I think. — AakashM, May 24 '12 at 07:59
See [get-list-element-position-in-c-sharp-using-linq?](http://stackoverflow.com/questions/1110789/get-list-element-position-in-c-sharp-using-linq?lq=1) — nawfal, May 19 '14 at 17:17

score 2 · Accepted Answer · answered May 24 '12 at 08:09

2

I'd recommend using the Select in conjunction with Aggregate LINQ extension methods. Using the Select method you can create an anonymous type which houses the index and value of each item within your collection. Then using the LINQ Aggregate method, you can narrow down the item with the greatest value. Some like this should work I think:

private int GetIndexOfHighestValue(IEnumerable<int> list)
{
    return list.Select((i, v) => new { Index = i, Value = v })
        .Aggregate((a, b) => (a.Value > b.Value) ? a : b)
        .Index;
}

answered May 24 '12 at 08:09

Richard

8,110
3
36
59

Certainly much cleaner than my code snippet already, thanks! (there is still the double evaluation problem though) – Julien Guertault May 24 '12 at 19:20
Forget my remark on evaluation. Applied to my example, in the `Select` part we have `Value = eval(x, v)` and we're happy. Thanks again! – Julien Guertault May 29 '12 at 02:41

score 1 · Answer 2 · answered May 24 '12 at 08:06

1

Doing it with LINQ is fun, but doing it without LINQ makes it more intuitive:

int bestIndex = -1;
int bestResult = -1;
for(int i = 0; i < elements.Count; ++i)
{
    int currentResult = eval(x, elements[i]);
    if (currentResult > bestResult)
    {
        bestResult = currentResult;
        bestIndex = i;
    }
}

answered May 24 '12 at 08:06

Davio

4,609
2
31
58

1

This is what I want to avoid. Writing it is easy, but it takes some time to read and figure out. I am looking for what the language offers to write something really elegant and crystal clear, like for example `var best = elements.MaxBy(y => eval(x, y))`. – Julien Guertault May 24 '12 at 08:14
You can do `elements.Max(e => eval(x, e))`, but this will always yield an element. I would split the eval into some filter method and an actual calculation. This way you can do `elements.Where(e => qualifies(e)).Max(e => eval(x, e))` for example. – Davio May 24 '12 at 08:27
1

@JulienGuertault Wrap this in a suitable extension method and you're done. Note that your example is NOT something "the language offers" - it's something a *library* offers. And the internals of that library look like this code. – AakashM May 25 '12 at 11:02

Daren Thomas · Answer 3 · 2012-05-24T08:07:49.767

Something like ~~this could work~~:

// OOPS: This won't work because Max is defined the way it is. Always bugged me...
var result = elements.Select((e, i) => new {Element = e, Index = i}).Max(x => x.Element).Select(x => x.Index);

oh rats. Right. This will not work. So: Let's pull out our allrounder: Aggregate. Here we go:

var elements = new List<int>{1, 7, 2, 5};
var result = elements.Select((e, i) => new {Element = e, Index = i})
    .Aggregate(
        new { Element = elements.First(), Index = -1}, // gotta start somewhere and Element is non-nullable according to OP
        (max, next) => (max.Element > next.Element) && max.Index >= 0 ? max : next,
        max => max.Index);

This results in 1. Did that help?

No, it will not work. The `.Max` extension method returns directly the maximum element. There's no longer an `Index` property so your final `.Select` statement won't compile. The .Select extension method operates on `IEnumerable` but `.Max` returns `T`. — Darin Dimitrov, May 24 '12 at 07:56

Elegant way to retrieve the index of the max element from a List in C#

3 Answers3