13

これよりも効率的/高速な最小値インデックスを見つける方法はありますか?

int minimumValueIndex = List.IndexOf(List.Min());
4

10 に答える 10

10

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;
}
于 2013-05-01T17:47:23.533 に答える
5

私自身の経験では、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;}
}

System.Diagnostics.StopWatch を使用して、環境で両方のアプローチの速度をいつでもテストできます。

于 2013-05-01T17:47:10.297 に答える
2

@cdhowie によって投稿された回答には問題がありIList<T>、インデクサーを介して特定のアイテムに効率的にアクセスできると想定しています。配列 および についてはそれが当てはまりますがList[T]、それはまったく保証されていません (例として、 を実装する単方向リンク リストを取り上げますIlist<T>)。

これを一般的な 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 ;
}

または、ループの本体で無関係な初期化と無関係な比較を取り除くため、間違いなくクリーンです。

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 ;
}

ストックのLinqAggregate()オーバーロードを使用することもできますが、ブルートフォースメソッドよりもクリーンでもシンプルでもありません(おそらく効率も悪いです、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 ;
于 2013-05-01T19:47:01.517 に答える
1

@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;
}
于 2015-01-14T11:02:56.097 に答える
1

可能であれば、値がリストに配置されるときに最小値/インデックスを追跡して、完全なリストをループする必要がないようにしてください。次に、新しい値がリストに追加された場合は、保存した最小値と照合し、必要に応じて新しい最小値を変更します。

もちろん、それはあなたの状況に適していないかもしれません。

于 2013-05-01T18:07:00.773 に答える
0

最小計算:コレクション内のMin値の検索は O(n) よりも高速に実行できないため、それよりも優れた方法ではないかもしれませんが、コード スタイルが異なるだけです。

検索手順:問題によっては、特別なデータ構造 (バイナリ ツリー、ヒープ ツリーなど) を使用して、インデックスをより高速に見つけることができます。

min-heap tree のようなものを使用すると、いくつかの特別な Add、Remove 関数を犠牲にして、O(1) で最小値を取得できます。

于 2013-05-01T17:43:06.820 に答える
0

もちろん。MinLINQ を使用する代わりに、現在の最小値のインデックスを追跡する独自の関数を作成するだけです。そうすることで、アイテムの最小値に基づいてアイテムのインデックスを見つける必要がなくなります。

于 2013-05-01T17:47:18.110 に答える
-2

私は怠け者なので、次を使用します：

List.Sort();/* sorts the values least to greatest */
List[0];/* first item has the least value */
于 2015-12-01T22:24:29.473 に答える