5

C#でルックアップテーブルを実行する最も効率的な方法は何ですか?

ルックアップテーブルがあります。みたいな

0 "Thing 1"
1 "Thing 2"
2 "Reserved"
3 "Reserved"
4 "Reserved"
5 "Not a Thing"

したがって、誰かが「Thing 1」または「Thing 2」を必要とする場合、0 または 1 を渡します。しかし、他の何かを渡す場合もあります。私はこれらのタイプのものを256個持っており、おそらく200個は予約されています。

では、これを設定する最も効率的な方法は何ですか?

  • すべての値を取得する文字列配列または辞書変数。そして、整数を取り、その場所の値を返します。

このソリューションで私が抱えている問題の 1 つは、すべての「予約済み」値です。これらの冗長な「予約済み」値を作成したくありません。または、「予約済み」のさまざまな場所のすべてに対してifステートメントを作成できますが、それらは現在2〜3、2〜3、40〜55、およびバイト内のすべての異なる場所である可能性があります。このifステートメントは手に負えないほど速くなります

  • 私が考えていた他のオプションは、switch ステートメントでした。そして、50 個の既知の値をすべて取得し、フォールスルーして、予約済みの値をデフォルトに設定します。

これは、文字列配列または辞書を作成して適切な値を返すよりもはるかに多くの処理であるかどうか疑問に思っています。

  • 他の何か？他に検討する方法はありますか？
4

9 に答える 9

14

「Dictionary(TKey, TValue) クラスがハッシュ テーブルとして実装されているため、キーを使用して値を取得するのは非常に高速で、O(1) に近いです。」

var things = new Dictionary<int, string>();
things[0]="Thing 1";
things[1]="Thing 2";
things[4711]="Carmen Sandiego";
于 2009-12-06T16:48:57.470 に答える
6

C＃で整数値のルックアップを行うための絶対最速の方法は、配列を使用することです。これは、一度に数万のルックアップを実行しようとしている場合は、辞書を使用するよりも望ましいでしょう。ほとんどの場合、これはやり過ぎです。プロセッサ時間よりも開発者時間を最適化する必要がある可能性が高くなります。

予約済みのキーがルックアップテーブルにないすべてのキーではない場合（つまり、キーのルックアップで検出された値、見つからないステータス、または予約済みのステータスが返される場合）、保存する必要があります。どこかに予約されたキー。マジック値を持つディクショナリエントリとして保存する（たとえば、値がnullのディクショナリエントリのキーは予約されている）場合は、ディクショナリのエントリをフィルタリングせずに繰り返すコードを記述しない限り、問題ありません。

この問題を解決する方法はHashSet<int>、予約済みのキーを格納するために別のキーを使用し、場合によってはすべてをクラスにベイクすることです。

public class LookupTable
{
   public readonly Dictionary<int, string> Table { get; }
   public readonly HashSet<int> ReservedKeys { get; }

   public LookupTable()
   {
      Table = new Dictionary<int, string>();
      ReservedKeys = new HashSet<int>();
   }

   public string Lookup(int key)
   {
      return (ReservedKeys.Contains(key))
         ? null
         : Table[key];
   }
}

これにはまだマジック値の問題があることに注意してください-Lookupキーが予約されている場合はnullを返し、テーブルにない場合は例外をスローします-少なくとも今はTable.Valuesマジック値をフィルタリングせずに繰り返すことができます。

于 2009-12-06T19:05:43.123 に答える
3

予約済みの (現在は使用されていない) 値が多数ある場合、または整数値の範囲が非常に大きくなる可能性がある場合は、一般的な辞書 (Dictionary) を使用します。

var myDictionary = new Dictionary<int, string>();
myDictionary.Add(0, "Value 1");
myDictionary.Add(200, "Another value");
// and so on

それ以外の場合、固定数の値があり、現在使用されていないのはごくわずかである場合は、文字列配列 (string[200]) を使用し、予約されたエントリを null に設定/そのままにします。

var myArray = new string[200];
myArray[0] = "Value 1";
myArray[2] = "Another value";
//myArray[1] is null
于 2009-12-06T16:50:02.227 に答える
3

HybridDictionary をチェックアウトします。最大の効率を得るために、サイズに基づいて基盤となるストレージ メカニズムを自動的に調整します。

http://msdn.microsoft.com/en-us/library/system.collections.specialized.hybriddictionary.aspx

于 2009-12-06T16:52:12.060 に答える
0

組み込みのDictionaryオブジェクト (できれば一般的な辞書) はこれに最適で、キーに関連する値を高速かつ効率的に取得できるように特別に設計されています。

リンクされた MSDN の記事から:

Dictionary<(Of <(TKey, TValue>)>) クラスがハッシュ テーブルとして実装されているため、キーを使用して値を取得するのは非常に高速で、O(1) に近くなります。

「予約済み」キーに関する限り、数百のキー/値について話しているだけであれば、まったく心配する必要はありません。より効率的なものを実装する必要があるのは、数十、おそらく数十万の「予約済み」キー/値に達したときだけです。

そのような場合、おそらく最も効率的なストレージ コンテナーはSparse Matrixの実装になります。

于 2009-12-06T16:50:06.453 に答える
0

あなたの問題を正しく理解しているかどうかはよくわかりません。文字列のコレクションがあります。各文字列はインデックスに関連付けられています。インデックスが予約されていない限り、消費者リクエストはインデックスを提供し、対応する文字列を返します。右？

配列で予約済みアイテムをnullとして単純に設定できませんか。

そうでない場合は、予約項目を含まない辞書を使用するのが合理的な解決策のようです。

とにかく、問題を明確にすれば、おそらくより良い答えが得られるでしょう。

于 2009-12-06T16:50:11.143 に答える
0

すべての値をロードします

var dic = new Dictionary<int, string>();

そして、これを検索に使用します：

string GetDescription(int val)
{
     if(0 <= val && val < 256)
        if(!dic.Contains(val))
           return "Reserved";
        return dic[val];
    throw new ApplicationException("Value must be between 0 and 255");
}
于 2009-12-06T16:50:56.657 に答える
0

辞書を使用して検索を行います。これは、ルックアップを行う最も効率的な方法です。文字列を使用すると、オブジェクトを見つけるために O(n) の領域のどこかで実行されます。

必要に応じて逆引きを行うために、2 番目の辞書を用意しておくと便利な場合があります。

于 2009-12-06T16:51:54.823 に答える
0

あなたの質問は、クエリ キーが整数であることを暗示しているようです。最大で 256 個のアイテムがあるため、クエリ キーは 0..255 の範囲になりますよね? その場合は、256 個の文字列の文字列配列を用意し、キーを配列のインデックスとして使用します。

クエリ キーが文字列値の場合、実際のルックアップ テーブルに似ています。Dictionary オブジェクトを使用するのは簡単ですが、実際の回答が 50 個ほどしかない場合に生の速度を求めている場合は、二分探索やトライなどの自分で行うアプローチの方が速い場合があります。二分探索を使えば、項目数が少ないので展開できます。

アイテムのリストはどのくらいの頻度で変更されますか? めったに変更されない場合は、検索を実行するコードを生成し、それをコンパイルして実行して各クエリを実行することで、さらに高速化できます。

一方、プロファイリングまたはスタックショットの取得によって、このルックアップがボトルネックであることを証明したと思います。time-when-slow の 10% 未満がこのクエリに費やされている場合、それはボトルネックではないため、コーディングが最も簡単な方法を実行することもできます。

于 2009-12-06T22:28:46.573 に答える