0

SortedList や SortedDictionary などの C# の並べ替えられたコレクションについて理解しようとしています。私には 2 つの主要なメンタル ブロッカーがあり、それらを明確に説明している場所が見つかりません。これらのコレクション自体を並べ替えるデフォルトの方法があり、これを指定することもできることを理解しています。

私の質問は単純だと思います。これはどのように行われますか？これらの書き方の簡単な例が見つかりません。

たとえば、float から int までのキーと値のペアをコレクションに格納する必要があるとします。最小の float 値についてコレクションにクエリを実行して int を取得できるようにしたいと考えています。言い換えれば、関連付けられた最小のフロート キーで int を取得したいと考えています。コレクションがソートされているという事実が、この種のことをより効率的に行うと考えているのは正しいですか? これは、collection[0] のように、コレクションの最初の要素を取得できるという意味ですか? そしてそれは最低になりますか？（私がそのように並べ替えた場合）

申し訳ありませんが、この質問は簡潔ではありません。どこから始めればよいかわかりません。

4

4 に答える 4

1

SortedDictionary は、整数インデクサーも「最小キーを取得する」関数も提供しません。SortedList が行います。ただし、データを順不同で挿入する場合、SortedList は非常に非効率的です。最初に注文してから、リストを作成する必要があります。

SortedDictionary に欠けている唯一の必要な関数が「最小キーの取得」である場合は、列挙子がキーと値のペアをキー順に返すため、Firstまたはlinq メソッドを使用できます。FirstOrDefault他の同様の関数 (「最大キーの取得」など) が必要で、ランダムに分散された値のより効率的な挿入と削除も必要な場合は、これらの関数を公開するバイナリ ツリー (SortedDictionary) の独自の実装を作成する必要があります。 .

を実装IComparer<T>するには、新しいクラスを作成します。

public class FloatComparer : IComparer<float>
{
    public int Compare(float a, float b)
    {
        //your logic goes here; return -1 if a should be considered smaller or 1 if b should be considered smaller
    }
}

次に、通常の方法で並べ替えられたコレクションのコンストラクターに渡します。

var collection = new SortedDictionary<float>(new IComparer<float>());
于 2012-07-30T22:06:12.707 に答える
0

ツリーやヒープなどのデータ構造を読んでください。レッドブラックツリーから始めてください。典型的な例だと思います。グーグルとウィキペディアが役立ちます。

基本的に、挿入するものには、大きい、等しい、小さいと比較できる何らかの定義があります。挿入時に要素が比較され、並べ替えられます。したがって、最初または最後を検索すると、それらが最小または最大であることがわかります。たとえば、構造体に4に等しい整数があるかどうかを効率的に確認することもできます。

于 2012-07-30T21:57:29.117 に答える
0

SortedDictionaryはバランスの取れたツリーですが、SortedListは順序付けられた要素をたまたま含むメモリの連続したスラブです。どちらの場合も、「未満」の意味を定義する必要があるため、ツリーがノードを整理し、ソートされたリストがその要素を順序付けできるようにします。

  • IComparerを実装するオブジェクトをこれらのコンテナーのコンストラクターに渡すと、それが使用されます。厳密な弱い順序付けである限り、問題なく動作します。たとえば、「より大きい」比較子を指定することで、コンテナーを逆順にソートするのは簡単です。
  • それ以外の場合は、デフォルトの比較子が使用されます。

あなたの場合（floatキーはどこですか）、デフォルトの比較子は正しいことを行い、要素を最低値から最高値に並べ替えます。最初の要素を取得することは効率的であり、最初の要素もたまたま最小値になります。

于 2012-07-30T23:05:48.813 に答える