C# 在 List<T> 中获取最小值索引的快速/有效方法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16323386/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fast/efficient way to get index of minimum value in List<T>?
提问by Kamil
Is there any way to find minimum value index more efficient/faster than this?
有什么方法可以找到比这更有效/更快的最小值索引？
int minimumValueIndex = List.IndexOf(List.Min());
采纳答案by cdhowie
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 originalelement by key instead of selecting a transformation. This oversight is particularly painful in situations like this.)
是的，您可以List.IndexOf()通过构建自定义Min()扩展来消除开销。（真的，Enumerable.Min()应该有一个通过键选择原始元素而不是选择转换的扩展。这种疏忽在这种情况下特别痛苦。）
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;
}
回答by Hossein Narimani Rad
Min Calculation:Finding the Minvalue in a collection cannot be done faster than O(n) so it may be no better way than that but just a different in the code style.
最小计算：Min在集合中查找值不能比 O(n) 更快，因此它可能没有比这更好的方法，而只是代码风格的不同。
Finding Step:depending on your problem you may use some special data structure (such as binary tree, heap tree, ...) so you can find the index more faster.
查找步骤：根据您的问题，您可能会使用一些特殊的数据结构（例如二叉树，堆树，...），以便您可以更快地找到索引。
Using something like min-heap tree you can get the min value with O(1) in expense of some special Add, Remove functions.
使用诸如最小堆树之类的东西，您可以获得 O(1) 的最小值，但要花费一些特殊的添加、删除功能。
回答by Prahlad Yeri
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:
根据我自己的经验，诸如 Array.Max() 和 Array.Min() 之类的 LINQ 聚合方法通常比手动 for 循环慢。因此，您可以考虑将这样的事情作为替代方法：
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.
您始终可以使用 System.Diagnostics.StopWatch 在您的环境中测试这两种方法的速度。
回答by Servy
Sure. Just write your own Minfunction, instead of using LINQ, that keeps track of the index of the current minimum value. By doing that you can avoid needing to find the index of the item based on it's min value.
当然。只需编写您自己的Min函数，而不是使用 LINQ，它会跟踪当前最小值的索引。通过这样做，您可以避免需要根据项目的最小值来查找项目的索引。
回答by Colton
If possible, keep track of the min value/index as the values are placed in to the list, so you do not need to loop through a full list. Then if new values are added to the list, check them against the min value that you saved, and change the new min value as necessary.
如果可能，请在将值放入列表时跟踪最小值/索引，因此您无需遍历完整列表。然后，如果新值添加到列表中，请根据您保存的最小值检查它们，并根据需要更改新的最小值。
Of course that might not be suitable for your situation.
当然，这可能不适合您的情况。
回答by Nicholas Carey
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>).
@cdhowie 发布的答案存在一个问题，因为它假定 anIList<T>可以通过其索引器有效地访问特定项目。虽然它对于数组 andList[T]是正确的，但它绝对没有保证（例如，一个实现 的单链表Ilist<T>）。
If i was going to do this in a generic, Linqy way, I'd do something like:
如果我打算以通用的 Linqy 方式执行此操作，我会执行以下操作：
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):
您也可以使用股票 LinqAggregate()重载，尽管它并不比蛮力方法更干净或更简单（恕我直言，效率也可能更低）：
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 ;
回答by pengdlzn
I improved @cdhowie's answera little bit to make it more powerful. If there are more than one minimum elements, then this method will return the first one.
我稍微改进了@cdhowie 的答案，使其更强大。如果有多个最小元素，则此方法将返回第一个。
public static T GetMin<T, TOrder>(this IEnumerable<T> self, Func<T, TOrder> orderFunc,
out int minIndex, IComparer<TOrder> cmp = null)
{
if (self == null) throw new ArgumentNullException("self");
IEnumerator<T> selfEnumerator = self.GetEnumerator();
if (!selfEnumerator.MoveNext()) throw new ArgumentException("List is empty.", "self");
if (cmp == null) cmp = Comparer<TOrder>.Default;
T min = selfEnumerator.Current;
minIndex = 0;
int intCount = 1;
while (selfEnumerator.MoveNext ())
{
if (cmp.Compare(orderFunc(selfEnumerator.Current), orderFunc(min)) < 0)
{
min = selfEnumerator.Current;
minIndex = intCount;
}
intCount++;
}
return min;
}
回答by user3574895
I'm lazy so I would use:
我很懒，所以我会使用：
List.Sort();/* sorts the values least to greatest */
List[0];/* first item has the least value */
