文字列をキーにした辞書の認識速度について、かなり一般的な質問がありますが、今のところ答えが見つかりませんでした。
現在のプログラムにはカスタムオブジェクトの辞書がありますが、使用するキーはファイルのパス全体を含むファイル名であるため、実際にはキーが2回発生することはありません。
私の質問は、辞書内で特定のオブジェクトを見つける時間は、キーとして使用される文字列の長さに大きく依存しますか？結局のところ、オブジェクト内に大量のデータが保存されていて、そのデータをループで使用し、を使用して毎回データにアクセスする場合myDictionary[Key]。単純な認識には時間がかかり、ループが長く続く可能性があります。
この問題の解決策は次のとおりです。たとえば、オブジェクト内で配列を使用する場合、double[,,]一時的に新しい配列を作成し、これを辞書内の配列と同じに設定するため、辞書を検索する必要はありません。ループの反復ごとに。
ディクショナリ内で特定のオブジェクトを見つけるまでの時間は、キーとして使用される文字列の長さに大きく依存しますか?
はい、そうです。ディクショナリ内の要素の検索は、CPU を集中的に使用する 2 つの手順で行われます。
ディクショナリは要素をバケットに格納します。O(1)ルックアップを実行できるようにするために、ディクショナリは を使用して内部配列内の位置を計算しhashCode modulo array.Lengthます。これにより、同じインデックスを持つ要素が発生する可能性があります。これらの要素は同じインデックスの下に格納されます。これはバケットと呼ばれます。
文字列の場合、ハッシュ コードは文字列内のすべての文字を使用して生成されます。つまり、文字列のハッシュ コードの生成には O(n) のパフォーマンス特性があります。文字列が大きい場合、ハッシュ コードの生成に時間がかかります。文字列との比較は、2 つの文字列を完全に比較することによって行われます。たとえば、これらの文字列に 100,000 文字が含まれていて、最後の文字だけが異なる場合、2 つの文字列の比較にはかなりの時間がかかる可能性があります。最初の文字が異なる場合、比較はすぐに false を返します。完全な文字列をトラバースする必要があるため、2 つの文字列が実際に等しい (参照が等しくない場合) ことを判断するには、最も時間がかかります。
可能であれば、ディクショナリがアプリケーションのパフォーマンス クリティカル パスにある場合は、キー文字列を短くします。
編集
私の答えの文言は少し誤解を招くものでした-それを解消しようとしています。
理論的には、ハッシュ関数が理想的なハッシュ コードを生成する場合 (一意の入力ごとに出力も一意であることを意味します)、辞書/ハッシュ テーブルの検索は O(1) プロセスである必要があります。2 つの入力文字列が同じハッシュ コードを生成する場合 (ハッシュ関数は理想的ではありません)、そのハッシュ コードに対してエントリのリスト (「バケット」) が作成され、アイテムごとに検索する必要があります。
したがって、ハッシュ コードが作成されると、理論上、バケットの検索は O(1) 操作になります。バケットの検索は O(n) 操作です。n はバケット内の要素の数です。
文字列の長さは以下に影響します。
そう:はい、文字列の長さは実際には重要です。
本当の問題は、ディクショナリ内のすべてのキーを頻繁に反復処理するということを考えると、ディクショナリが本当に適切なツールであるかどうかです。その場合、オブジェクトのリスト (ファイル名とその他のデータを含む) を使用し、挿入のたびにファイル名を検索して重複の挿入を防ぐと、挿入はめったになく頻繁に検索すると、はるかに高速になる可能性があります。
一般に、短い文字列は長い文字列よりもパフォーマンスが高くなります。ただし、パフォーマンスへの影響は非常に限定的です (何百万回も取得するまで)。マイクロベンチを試すか、ここで読むことができます