Fast/efficient way to get index of minimum value in List<T>?
Yes, you can remove the overhead of List.IndexOf()
by building a custom Min()
extension. (Really, Enumerable.Min()
should have an extension that selects the original element by key instead of selecting a transformation. This oversight is particularly painful in situations like this.)
public static int IndexOfMin(this IList<int> self)
{
if (self == null) {
throw new ArgumentNullException("self");
}
if (self.Count == 0) {
throw new ArgumentException("List is empty.", "self");
}
int min = self[0];
int minIndex = 0;
for (int i = 1; i < self.Count; ++i) {
if (self[i] < min) {
min = self[i];
minIndex = i;
}
}
return minIndex;
}
In my own experience the LINQ aggregation methods such as Array.Max() and Array.Min() are typically slower than a manual for loop. So, you can consider something like this as an alternative approach:
int minima=0;
int mindex=0;
for(int i=0;i<List.Count;i++)
{
if (List[i]<minima)
{minima=List[i]; mindex=i;}
}
You can always test the speeds of both approaches on your environment by using System.Diagnostics.StopWatch.
There's a problem with answer posted by @cdhowie in that it assumes that an IList<T>
can efficiently access a particular item via its indexer. While that it true for arrays and List[T]
, it is in nono way guaranteed (take for an example, a singly-linked list that implements Ilist<T>
).
If i was going to do this in a generic, Linqy way, I'd do something like:
public static IndexOfMinValue<T>( this IList<T> list ) where T:IComparable
{
if ( list == null ) throw new ArgumentNullException("list") ;
int? offset = null ;
T min = default(T) ;
int i = 0 ;
foreach ( T item in list )
{
if ( !offset.HasValue || item.CompareTo(min) < 0 )
{
offset = i ;
min = item ;
}
++i ;
}
if ( !offset.HasValue ) throw new ArgumentOutOfRangeException("list","list is empty") ;
return offset.Value ;
}
Or, arguably cleaner, since we get rid of extraneous initialization and an extraneous compare in the body of the loop:
public static int IndexOfMin<T>( this IList<T> list ) where T:IComparable
{
if ( list == null ) throw new ArgumentNullException("list") ;
IEnumerator<T> enumerator = list.GetEnumerator() ;
bool isEmptyList = ! enumerator.MoveNext() ;
if ( isEmptyList ) throw new ArgumentOutOfRangeException("list","list is empty") ;
int minOffset = 0 ;
T minValue = enumerator.Current ;
for ( int i = 1 ; enumerator.MoveNext() ; ++i )
{
if ( enumerator.Current.CompareTo(minValue) >= 0 ) continue ;
minValue = enumerator.Current ;
minOffset = i ;
}
return minOffset ;
}
You could also use the stock Linq Aggregate()
overload, though it's no cleaner or simpler than the brute force method (probably less efficient, too, IMHO):
IList<int> = GetSomeIntegers() ;
int minIndex = list.Aggregate( (Tuple<int,int,int>)null,
( acc , item ) => {
int offset = 0 ;
int minValue = item ;
int minOffset = 0 ;
if ( acc != null )
{
offset = acc.Item3 + 1 ;
minValue = item < acc.Item1 ? item : acc.Item1 ;
minOffset = item < acc.Item1 ? offset : acc.Item2 ;
}
return new Tuple<int, int, int>( minValue , minOffset , offset ) ;
}).Item2 ;