9

に挿入するときはいつでもSortedList、アイテムが存在するかどうかを確認してから挿入します。これは同じ検索を 2 回実行していますか? アイテムがそこにあるかどうかを確認するために一度、アイテムを挿入する場所を見つけるためにもう一度? これを最適化して高速化する方法はありますか、それともこれを行う方法であり、変更は必要ありませんか?

if( sortedList.ContainsKey( foo ) == false ){
    sortedList.Add( foo, 0 );
}
4

5 に答える 5

6

項目を HashSet と List に追加できます。値をリストに追加する必要があるかどうかを確認するには、ハッシュ セットを検索するのが最も速い方法です。

if( hashSet.Contains( foo ) == false ){
    sortedList.Add( foo, 0 );  
    hashSet.Add(foo);
}
于 2012-11-08T16:13:43.787 に答える
1

インデクサーを使用できます。インデクサーは、最初にバイナリ検索を使用してキーに対応するインデックスを検索し、次にこのインデックスを使用して既存の項目を置き換えることにより、内部的に最適な方法でこれを行います。それ以外の場合は、既に計算されたインデックスを考慮して、新しい項目が追加されます。

list["foo"] = value;

キーが既に存在するかどうかに関係なく、例外はスローされません。

更新：

新しい値が古い値と同じである場合、古い値を置き換えると、何もしないのと同じ効果があります。

二分探索が行われることに注意してください。これは、1000 個のアイテムの中からアイテムを見つけるのに約 10 ステップかかることを意味します。log2(1000) ~= 10. したがって、余分な検索を行っても、速度に大きな影響はありません。1,000,000 個のアイテムを検索しても、この値は 2 倍になります (~ 20 ステップ)。

ただし、インデクサーを介して値を設定すると、いずれの場合も 1 回の検索しか実行されません。Reflector を使用してコードを調べたところ、これを確認できます。

于 2012-11-08T16:22:16.887 に答える
0

ContainsKeyO(log n) であるバイナリ検索を行うので、リストが大量でない限り、あまり心配する必要はありません。そして、おそらく、挿入時に別のバイナリ検索を実行して、挿入する場所を見つけます。

これを回避する (検索を 2 回行う)方法の 1つは、ListのBinarySearchメソッドを使用することです。アイテムが見つからない場合、これは負の値を返します。その負の値は、アイテムを挿入する場所のビットごとの補数です。そのため、アイテムを探すことができ、それがまだリストにない場合は、リストをソートしておくためにどこに挿入する必要があるかを正確に知ることができます。

于 2012-11-08T16:19:07.143 に答える
0

SortedList<Key,Value>おそらくまったく使用すべきではない遅いデータ構造です。既に使用を検討しているかもしれSortedDictionary<Key,Value>ませんが、アイテムにはインデックスがなく ( を書き込むことはできませんsortedDictionary[0])、最も近いキーの検索操作を記述できるが を記述できSortedListないため、不便であることがわかりましたSortedDictionary。

ただし、サードパーティのライブラリに切り替える場合は、別のデータ構造に変更することでパフォーマンスを向上させることができます。

Loyc Core ライブラリには、 と同じように機能するSortedList<Key,Value>が、リストが大きい場合に劇的に高速になるデータ型が含まれています。と呼ばれていBDictionary<Key,Value>ます。

ここで、元の質問に答えます。はい、コードを記述した方法で、2 つの検索と 1 つの挿入を実行します (挿入は最も遅い部分です)。に切り替えると、この 2 つの操作を 1 つの操作にまとめるBDictionary方法があります。bdictionary.AddIfNotPresent(key, value)指定された項目が追加された場合は true を返し、既に存在する場合は false を返します。

于 2016-02-26T05:40:33.323 に答える