14

リスト内のオブジェクトのインデックスを取得できるように、順序を保持する必要がある汎用リストがあります。問題は、IndexOfが遅すぎることです。IndexOfをコメントアウトすると、コードは可能な限り高速に実行されます。c＃の保存された順序付きハッシュリストなど、より良い方法はありますか？

ありがとう、ネイト

  • 編集-アイテムが追加/挿入される順序は、必要な順序です。それらを並べ替える必要はありません。また、このリストは頻繁に更新され、追加、削除、挿入される可能性があります。基本的に、オブジェクトはグリッドコントロールで表されるため、インデックスに変換する必要があります。これにより、インデックスに基づいてグリッドコントロールで操作を実行できるようになります。
4

9 に答える 9

14

ソートされていないが、順序を保持する必要があるDictionary<YourClass, int>場合は、各要素のインデックスを含む個別のものを作成できます。

並べ替えられたリストが必要な場合は、以前の投稿を確認してくださいSortedList<Tkey, TValue>。.Net 3.5 で使用するか、古い .Net バージョンで並べ替えて BinarySearch を使用できます。

[編集] Web で同様の例を見つけることができます (例: OrderedList )。これは内部的に ArrayList と HashTable を使用しますが、簡単に汎用にすることができます。

[Edit2] おっと..私があなたに与えた例は、私が最初に説明した方法で IndexOf を実装していません.しかし、あなたは要点を理解します.

于 2009-07-02T17:53:12.073 に答える
7

を使用して並べ替えてから、次のメソッドList<T>.Sortを使用します。 「並べ替えられた要素全体を検索します[...]このメソッドはO（log n）操作です。ここで、nは範囲内の要素の数です。」List<T>.BinarySearchList(T)

于 2009-07-02T17:45:28.857 に答える
6

こちらの記事の下部をご覧ください。

タイプに応じて仮想メソッドを呼び出すため、IndexOfメソッドを使用するよりも、独自のメソッドを記述してインデックスを取得する方がはるかに高速であるように見えます。

したがって、このようなものを使用すると、パフォーマンスが向上する可能性があります。これにより検索のパフォーマンスが向上することを確認するために、小さな単体テストを作成しました。これにより、10,000アイテムのリストで約15倍になりました。

static int GetIndex(IList<Item> list, Item value)
{
    for (int index = 0; index < list.Count; index++)
    {
        if (list[index] == value)
        {
             return index;
        } 
    }
    return -1;
}
于 2011-11-25T09:21:31.203 に答える
3

おそらくあなたは探していSortedList<TKey, TValue>ますか？

于 2009-07-02T17:43:48.640 に答える
2

アイテムをソートする必要がある場合は、 SortedList<TKey, TValue>orクラスを使用することをお勧めします。SortedDictionary<TKey, TValue>相違点は次のとおりです。

  • SortedList<TKey, TValue>は より少ないメモリを使用しますSortedDictionary<TKey, TValue>。

  • SortedDictionary<TKey, TValue>は、ソートされていないデータの挿入および削除操作を高速化します: の O(n) とは対照的に、O(log n) SortedList<TKey, TValue>。

  • リストが並べ替えられたデータから一度に入力される場合、SortedList<TKey, TValue>は よりも高速ですSortedDictionary<TKey, TValue>。

順序を維持したいだけの場合は、 aDictionary<TKey, TValue>を使用して、アイテムをキーとして、インデックスを値として保存できます。欠点は、項目の並べ替え、挿入、または削除を行うには非常にコストがかかることです。

于 2009-07-02T17:51:06.383 に答える
1

ハッシュリストを注文しなければならない理由はありません...それがポイントです。ただし、ハッシュリストは非常に簡単にトリックを実行する必要があります。

于 2009-07-02T17:43:22.993 に答える
1

Listクラスを使用している場合は、Sortメソッドを使用して、最初に入力された後にソートし、次にBinarySearchメソッドを使用して適切な要素を見つけることができます。

于 2009-07-02T17:46:23.830 に答える
1

C# の詳細についてはわかりませんが、並べ替え (QuickSort?) を行ってからバイナリ検索を使用することができるかもしれません (BinarySearch のパフォーマンスは O(log2(N)) であり、indexOf などのシーケンシャルではありません)。は O(n)) です。(重要: 二分探索の場合、構造をソートする必要があります)

アイテムをデータ構造に挿入するときは、変更されたバイナリ検索を試して挿入ポイントを見つけることもできます。または、大きなグループを追加する場合は、それらを追加してから並べ替えます。

唯一の問題は、挿入が遅くなることです。

于 2009-07-02T17:53:13.790 に答える