5

特定の実装に適したコレクションの選択に関する記事をたくさん読みました。最終的には実際のデータのベンチマークになることを理解していますが、それを行うのに忙しい間は次のようになります。

  • 含まれているアイテムの変更を許可するc#の並べ替えられたコレクションは何ですか?何も見つからないようです?

  • これは、変更がおそらく削除してから再挿入として実装され、明示的な「変更」関数が無意味になるためですか?

コレクション(カスタムまたは標準ライブラリ)が必要で、次の操作が実行されます。

  • 挿入-頻繁に
  • 削除-頻繁に
  • 変更-非常に頻繁に
  • 上位X要素を選択します-上記のいずれかが発生するたびに、さらにそれ以上が同時に発生します。

現在、O(logn)挿入を提供するため、SortedSetを使用していますが、削除のパフォーマンスと、アイテムを最適に変更する方法がわかりません。

4

1 に答える 1

1

まず、コレクションを変更することの意味を明確にする必要があります。

一般に、コレクションの操作とは、リストからのアイテムの挿入/削除を指します。個々のアイテムを変更するには、基本的にアイテムにアクセスしてそのプロパティを変更します。アイテムにアクセスするためのコストはコレクションの実装によって異なりますが、アイテムのプロパティの変更はコレクションに依存しません。また、コレクションアイテムが変更可能でない場合は、コレクションアイテムを変更できないことに注意してください。

最適な組み込みコレクションを探しているだけの場合は、基本的に、SortedListとSortedSetのどちらかを選択します(SortedDictionaryはSortedSetと同じです)。

SortedListはデータを配列として内部に格納するため、インデックスによる効率的なアクセスが可能です(上位X個のアイテムを取得するため)。SortedSetは(一定の係数で)挿入と削除が高速ですが、インデックス付きアクセスでは、ツリーを検索して次のアイテムを探す必要があります。最悪の場合、O(log n)と最良のcaes O(1)です。

それを除けば、どちらも赤黒木を実装しているため、実装の詳細が異なるだけなので、両者の違いは非常に小さいです。

ユーザーの場合、実際のパフォーマンスを測定する必要があります。しかし、あなたはすでにそれを知っています。

于 2012-04-26T18:39:07.737 に答える