34

Dictionary<K,V>.NETコレクションクラス（など）のメソッドの漸近的な複雑さ（big-Oおよびその他）に関するリソースはありますList<T>か？

C5ライブラリのドキュメントにそれに関する情報が含まれていることは知っていますが（例）、標準の.NETコレクションにも興味があります...（そしてPowerCollectionsの情報もいいでしょう）。

4

6 に答える 6

33

MSDNはこれらをリストします：

など。例：

SortedList（TKey、TValue）ジェネリッククラスは、O（log n）検索を使用するバイナリ検索ツリーです。nはディクショナリ内の要素の数です。この点では、SortedDictionary（TKey、TValue）ジェネリッククラスに似ています。2つのクラスには類似したオブジェクトモデルがあり、どちらにもO（log n）検索があります。2つのクラスが異なるのは、メモリの使用と挿入と削除の速度です。

SortedList（TKey、TValue）は、SortedDictionary（TKey、TValue）よりも少ないメモリを使用します。

SortedDictionary（TKey、TValue）は、SortedList（TKey、TValue）のO（n）とは対照的に、ソートされていないデータO（log n）の挿入および削除操作が高速です。

ソートされたデータからリストに一度にデータが入力される場合、SortedList（TKey、TValue）はSortedDictionary（TKey、TValue）よりも高速です。

于 2009-05-12T09:34:00.170 に答える
32

このページでは、Javaを使用したさまざまなコレクションタイプの複雑な時間の一部を要約していますが、.NETでもまったく同じである必要があります。

そのページからテーブルを取得し、.NETFramework用に変更/拡張しました。さまざまな操作に必要な時間の複雑さについて詳しく説明しているSortedDictionaryおよびSortedListのMSDNページも参照してください。

検索

検索/コレクションの種類の種類複雑さのコメント
線形検索Array/ArrayList / LinkedList O（N）ソートされていないデータ。
二分探索ソートされたArray/ArrayList / O（log N）ソートされたデータが必要です。
Search Hashtable / Dictionary <T> O（1）ハッシュ関数を使用します。
二分探索SortedDictionary/SortedKey O（log N）ソートは自動化されています。

検索と挿入

操作Array/ArrayList LinkedList SortedDictionary SortedList
アクセスバックO（1）O（1）O（log N）O（log N）
アクセスフロントO（1）O（1）NANA
アクセスミドルO（1）O（N）NANA
後ろに挿入O（1）O（1）O（log N）O（N）
前面に挿入O（N）O（1）NANA
真ん中に挿入O（N）O（1）NANA

削除は、関連するコレクションの挿入と同じ複雑さである必要があります。

SortedListには、挿入と取得に関していくつかの注目すべき特性があります。

挿入（メソッドの追加）：

このメソッドは、ソートされていないデータのO（n）演算です。ここで、nはカウントです。リストの最後に新しい要素が追加された場合、これはO（log n）操作です。挿入によってサイズ変更が発生する場合、操作はO（n）です。

取得（アイテムプロパティ）：

このプロパティの値を取得するのはO（log n）操作です。ここで、nはCountです。キーがすでにSortedList<（Of <（TKey、TValue>）>）にある場合、プロパティの設定はO（log n）操作です。キーがリストにない場合、プロパティの設定は、ソートされていないデータに対するO（n）操作、または新しい要素がリストの最後に追加された場合はO（log n）です。挿入によってサイズ変更が発生する場合、操作はO（n）です。

これは、すべての操作の複雑さの点でArrayList同等であることに注意してください。List<T>

于 2009-05-12T09:38:48.870 に答える
2

私は一般的にはわかりません（投稿された他の回答はおそらくあなたが何を求めているのかを正確に示しています）-しかし、もちろんILSpyを使用してこれと他の方法を反映することができます（FSharpコードでは少し厄介です、本当です）そしてこれは最終的に得ますこの関数はC＃として機能します。

internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
  while (true)
  {
    SetTree<a> setTree = s;
    if (setTree is SetTree<a>.SetOne)
    {
      break;
    }
    if (setTree == null)
    {
      return n;
    }
    SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
    SetTree<a> arg_23_0 = setNode.item3;
    n = setNode.item1;
    s = arg_23_0;
  }
  return ((SetTree<a>.SetOne)s).item;
  return n;
}

さて、これはC＃用語では正確に「適切な」コードではありませんが、while(true)ループが存在するということは、少なくともO（1）にすることはできないことを意味します。それが実際に何であるかについては...まあ、私の頭はあまりにも痛いのでわかりません:)

于 2011-06-15T12:45:35.683 に答える
2

このページでは、ほとんどの.NETコレクションの主な長所と短所について簡単に説明します。

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

コレクション 注文 連続ストレージ 直接アクセス ルックアップ効率 効率を操作する ノート
辞書 注文なし はい キー経由 キー：O（1） O（1） 高性能ルックアップに最適です。
SortedDictionary ソート済み いいえ キー経由 キー：O（log n） O（log n） 辞書の速度と順序の妥協、二分探索木を使用します。
SortedList ソート済み はい キー経由 キー：O（log n） の上） SortedDictionaryと非常に似ていますが、ツリーが配列に実装されているため、プリロードされたデータのルックアップは高速になりますが、ロードは遅くなります。
リスト ユーザーは要素の順序を正確に制御できます はい インデックス経由 インデックス：O（1）
値：O（n）		 の上） 直接アクセスが必要で、並べ替えが不要な小さなリストに最適です。
LinkedList ユーザーは要素の順序を正確に制御できます いいえ いいえ 値：O（n） O（1） 途中での挿入/削除が一般的で、直接アクセスする必要がないリストに最適です。
HashSet 注文なし はい キー経由 キー：O（1） O（1） キーと値が同じオブジェクトであることを除いて、辞書のような一意の順序付けられていないコレクション。
SortedSet ソート済み いいえ キー経由 キー：O（log n） O（log n） キーと値が同じオブジェクトであることを除いて、SortedDictionaryのような一意のソートされたコレクション。
スタック LIFO はい トップのみ 上：O（1） O（1）* LIFOとしてのプロセスのみを除いて、基本的にリストと同じです
列 FIFO はい フロントのみ フロント：O（1） O（1） FIFOとしてのプロセスのみを除いて、基本的にリストと同じです
于 2015-08-18T07:58:34.597 に答える
0

ドキュメントには、バイナリツリー上に構築されていると記載されており、最大要素の追跡については言及されていません。ドキュメントが正しい場合、それはO（log n）である必要があることを意味します。コレクションのドキュメントには少なくとも1つの間違いがありましたが（配列に裏打ちされたデータ構造をバイナリ検索ツリーと呼んでいます）、それは修正されました。

于 2011-06-29T13:56:21.767 に答える
0

「コレクションクラスの複雑さ」のようなものはありません。むしろ、これらのコレクションに対する操作が異なれば、複雑さも異なります。たとえば、要素をDictionary<K, V>...に追加します。

... O（1）操作に近づきます。新しい要素に対応するために容量を増やす必要がある場合、このメソッドはO（n）操作になります。ここで、nはですCount。

一方、 ...から要素を取得するDictionary<K, V>

... O（1）操作に近づきます。

于 2009-05-12T09:35:58.593 に答える