オブジェクトの静的セット (一度読み込まれるとほとんど変更されないという意味での静的) が与えられた場合、最適なパフォーマンスで繰り返し同時ルックアップが必要な場合、HashMapカスタム コンパレータを使用したバイナリ検索を使用する配列と、どちらが優れているでしょうか?
答えはオブジェクトまたは構造体型の関数ですか? ハッシュおよび/または等価関数のパフォーマンス? ハッシュの一意性? リストサイズ？ Hashsetサイズ/セットサイズ?
私が検討しているセットのサイズは、500k から 10m の範囲です (その情報が役立つ場合)。
私は C# の答えを探していますが、真の数学的答えは言語にはないと思うので、そのタグは含めません。ただし、C# 固有の注意事項がある場合は、その情報が必要です。
非常に小さなコレクションの場合、違いはごくわずかです。範囲の下限 (500k アイテム) では、多くのルックアップを行っている場合に違いが見え始めます。バイナリ検索は O(log n) になりますが、ハッシュ ルックアップは O(1), amortizedになります。これは真の定数と同じではありませんが、バイナリ検索よりもパフォーマンスを低下させるには、かなりひどいハッシュ関数が必要です。
（「ひどいハッシュ」と言うとき、私は次のようなことを意味します：
hashCode()
{
return 0;
}
ええ、それ自体は非常に高速ですが、ハッシュマップがリンクされたリストになります.)
ialiashkevichは、配列と Dictionary を使用して 2 つのメソッドを比較する C# コードを書きましたが、キーに Long 値を使用していました。ルックアップ中に実際にハッシュ関数を実行するものをテストしたかったので、そのコードを変更しました。String 値を使用するように変更し、populate セクションと lookup セクションを独自のメソッドにリファクタリングして、プロファイラーで見やすくしました。比較のポイントとして、Long 値を使用するコードも残しました。最後に、カスタムの二分探索関数を取り除き、Arrayクラス内のものを使用しました。
そのコードは次のとおりです。
class Program
{
private const long capacity = 10_000_000;
private static void Main(string[] args)
{
testLongValues();
Console.WriteLine();
testStringValues();
Console.ReadLine();
}
private static void testStringValues()
{
Dictionary<String, String> dict = new Dictionary<String, String>();
String[] arr = new String[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " String values...");
stopwatch.Start();
populateStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
Array.Sort(arr);
stopwatch.Stop();
Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with random values. */
private static void populateStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness
}
}
/* Populate a dictionary with values from an array. */
private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(arr[i], arr[i]);
}
}
/* Search a Dictionary for each value in an array. */
private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
String value = dict[arr[i]];
}
}
/* Do a binary search for each value in an array. */
private static void searchStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
private static void testLongValues()
{
Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue);
long[] arr = new long[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " Long values...");
stopwatch.Start();
populateLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with long values. */
private static void populateLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = i;
}
}
/* Populate a dictionary with long key/value pairs. */
private static void populateLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(i, i);
}
}
/* Search a Dictionary for each value in a range. */
private static void searchLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
long value = dict[i];
}
}
/* Do a binary search for each value in an array. */
private static void searchLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
/**
* Generate a random string of a given length.
* Implementation from https://stackoverflow.com/a/1344258/1288
*/
private static String generateRandomString(int length)
{
var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
var stringChars = new char[length];
var random = new Random();
for (int i = 0; i < stringChars.Length; i++)
{
stringChars[i] = chars[random.Next(chars.Length)];
}
return new String(stringChars);
}
}
いくつかの異なるサイズのコレクションの結果を次に示します。(時間はミリ秒単位です。)
500000 Long 値...
Long ディクショナリの入力: 26
Long 配列の入力: 2
Long ディクショナリの検索: 9
Long 配列の検索: 80500000 文字列値...
文字列配列の入力: 1237
文字列辞書の入力: 46
文字列配列の並べ替え: 1755
文字列辞書の検索: 27
文字列配列の検索: 15691000000 長い値...
長い辞書の入力: 58
長い配列の入力: 5
長い辞書の検索: 23
長い配列の検索: 1361000000 文字列値...
入力文字列配列: 2070
入力文字列ディクショナリ: 121
ソート文字列配列: 3579
検索文字列ディクショナリ: 58
検索文字列配列: 32673000000 長い値...
長い辞書の入力: 207
長い配列の入力: 14
長い辞書の検索: 75
長い配列の検索: 4353000000 文字列値...文字列配列の入力
: 5553文字列辞書の入力
: 449
文字列配列の並べ替え: 11695
文字列辞書の検索: 194
文字列配列の検索: 1059410000000 長い値...
長い辞書の入力: 521
長い配列の入力: 47
長い辞書の検索: 202
長い配列の検索: 118110000000 文字列値...入力
文字列配列: 18119入力
文字列ディクショナリ: 1088
ソート文字列配列: 28174
検索文字列ディクショナリ: 747
検索文字列配列: 26503
比較のために、最後にプログラムを実行したときのプロファイラーの出力 (1,000 万件のレコードとルックアップ) を示します。関連する機能を強調しました。上記のストップウォッチのタイミング指標とほぼ一致しています。
ディクショナリ ルックアップは二分探索よりもはるかに高速であり、(予想どおり) その違いはコレクションが大きいほど顕著であることがわかります。したがって、妥当なハッシュ関数 (競合がほとんどなくかなり高速) を使用している場合、ハッシュ ルックアップは、この範囲内のコレクションのバイナリ検索よりも優れているはずです。
ボビー、ビル、コービンの答えは間違っています。O(1) は、固定/有界 n の場合、O(log n) よりも遅くありません。
log(n) は定数なので定数時間に依存します。
遅いハッシュ関数については、md5 について聞いたことがありますか?
デフォルトの文字列ハッシュ アルゴリズムはおそらくすべての文字に影響し、長い文字列キーの平均的な比較よりも簡単に 100 倍遅くなる可能性があります。そこに行って、それをしました。
（部分的に）基数を使用できる場合があります。256 個のほぼ同じサイズのブロックに分割できる場合、2k から 40k のバイナリ検索を見ていることになります。これにより、はるかに優れたパフォーマンスが得られる可能性があります。
[編集] 理解できないことに投票する人が多すぎます。
ソートされたセットをバイナリ検索するための文字列比較には、非常に興味深い特性があります。ターゲットに近づくほど遅くなります。最初は最初の文字で壊れ、最終的には最後の文字でのみ壊れます。それらの時間が一定であると仮定するのは正しくありません。
この質問に対する唯一の合理的な答えは、次のとおりです。それは、データのサイズ、データの形状、ハッシュの実装、バイナリ検索の実装、およびデータが存在する場所 (質問には記載されていませんが) によって異なります。他のいくつかの回答が同じことを言っているので、これを削除するだけです。ただし、フィードバックから学んだことを元の回答に共有するとよいでしょう。
コメントを考えると、ハッシュ テーブルを使用する人は気が狂っていると思うかもしれません。ハッシュテーブルは無謀で危険ですか? これらの人々は正気ですか？
そうではないことがわかりました。バイナリ ツリーが特定の処理 (データの順序どおりのトラバーサル、ストレージの効率化) に優れているのと同様に、ハッシュ テーブルにも活躍の場があります。特に、データのフェッチに必要な読み取り回数を減らすのに非常に優れています。ハッシュ アルゴリズムは場所を生成し、メモリまたはディスク上でその場所に直接ジャンプできます。一方、二分探索は各比較中にデータを読み取り、次に何を読み取るかを決定します。各読み取りには、CPU 命令よりも 1 桁 (またはそれ以上) 遅いキャッシュ ミスが発生する可能性があります。
ハッシュ テーブルが二分探索より優れていると言っているわけではありません。そうではありません。また、すべてのハッシュとバイナリ検索の実装が同じであると示唆するものでもありません。そうではありません。言いたいことがあるとすれば、それは次のとおりです。両方のアプローチには理由があります。どちらがニーズに最適かを判断するのはあなた次第です。
元の答え:
ハッシュ アルゴリズムは O(1) ですが、二分探索は O(log n) です。したがって、n が無限大に近づくにつれて、バイナリ検索に比べてハッシュのパフォーマンスが向上します。走行距離は、n、ハッシュの実装、バイナリ検索の実装によって異なります。
O(1) に関する興味深い議論。言い換え:
O(1) は瞬時という意味ではありません。これは、n のサイズが大きくなってもパフォーマンスが変わらないことを意味します。誰も使用しないほど遅いハッシュ アルゴリズムを設計できますが、それでも O(1) になります。ただし、.NET/C# が法外なコストのかかるハッシュに悩まされていないことはかなり確信しています;)
わかりました、私は短くしようとします。
C# の短い答え:
2 つの異なるアプローチをテストします。
.NET は、1 行のコードでアプローチを変更するためのツールを提供します。それ以外の場合は、System.Collections.Generic.Dictionary を使用し、必ず初期容量として大きな数で初期化してください。そうしないと、古いバケット配列を収集するために GC が行う必要がある仕事のために、残りの人生をアイテムを挿入して過ごすことになります。
より長い答え：
ハッシュテーブルのルックアップ時間はほぼ一定であり、現実の世界でハッシュテーブル内のアイテムに到達するために必要なのは、ハッシュを計算することだけではありません。
アイテムに到達するために、ハッシュテーブルは次のようになります。
ルックアップ時間は、「良い」(出力がどれだけスパースであるか) ハッシュ関数の速さ、使用しているバケットの数、およびキー比較子の速さによって異なります。常に最適なソリューションとは限りません。
より良い、より深い説明: http://en.wikipedia.org/wiki/Hash_table
最悪の場合の特性はバイナリ検索の方が優れていますが、通常はハッシュの方が高速です。ハッシュ アクセスは通常、ハッシュ値を取得してレコードがどの「バケット」にあるかを判断するための計算であるため、パフォーマンスは通常、レコードがどの程度均等に分散されているか、およびバケットの検索に使用される方法に依存します。バケットの線形検索を使用した不適切なハッシュ関数 (大量のレコードを含むいくつかのバケットを残す) は、検索が遅くなります。(第 3 に、メモリではなくディスクを読み取っている場合、ハッシュ バケットは連続している可能性が高く、バイナリ ツリーは非ローカル アクセスをほぼ保証します。)
一般的に速くしたい場合は、ハッシュを使用してください。限られたパフォーマンスを保証することが本当に必要な場合は、バイナリ ツリーを使用できます。
驚いたことに、Cuckoo ハッシュは O(1) を保証し、完全ハッシュとは異なり、割り当てられたすべてのメモリを使用できます。完全ハッシュは O(1) を保証しますが、その大部分を無駄にする可能性があります。割り当て。警告？すべての最適化は挿入段階で実行されるため、挿入時間は非常に遅くなる可能性があります。特に、要素の数が増えると顕著になります。
これのいくつかのバージョンは、IP ルックアップのためにルーター ハードウェアで使用されていると思います。
リンクテキストを見る
サイズが ~1M の問題セットでは、ハッシュの方が高速であると強く思います。
数字だけ：
バイナリ検索には ~ 20 回の比較が必要です (2^20 == 1M)
ハッシュ ルックアップでは、検索キーに対して 1 つのハッシュ計算が必要であり、衝突の可能性を解決するために後でいくつかの比較が必要になる可能性があります。
編集：数字：
for (int i = 0; i < 1000 * 1000; i++) {
c.GetHashCode();
}
for (int i = 0; i < 1000 * 1000; i++) {
for (int j = 0; j < 20; j++)
c.CompareTo(d);
}
回: c = "abcde"、d = "rwerij" ハッシュコード: 0.0012 秒。比較: 2.4 秒。
免責事項: 実際にはハッシュ ルックアップとバイナリ ルックアップのベンチマークを行う方が、この完全に関連性のないテストよりも優れている可能性があります。GetHashCode が内部でメモ化されるかどうかさえわかりません
主にハッシュと比較メソッドのパフォーマンスに依存していると思います。たとえば、非常に長いがランダムな文字列キーを使用する場合、比較では常に非常に迅速な結果が得られますが、デフォルトのハッシュ関数は文字列全体を処理します。
しかし、ほとんどの場合、ハッシュ マップの方が高速です。
なぜ誰も完璧なハッシュについて言及しなかったのだろうか。
データセットが長期間固定されている場合にのみ関連しますが、データを分析し、衝突がないことを保証する完全なハッシュ関数を構築します。
データセットが一定で、関数の計算時間がアプリケーションの実行時間に比べて短い場合は、非常に便利です。
ハッシュテーブルの重複をどのように処理するかによって異なります (存在する場合)。ハッシュ キーの重複を許可したい場合 (完全なハッシュ関数はありません)、主キーの検索は O(1) のままですが、「正しい」値を後ろから検索するとコストがかかる場合があります。答えは、理論的にはほとんどの場合、ハッシュの方が高速です。あなたがそこに置くデータに応じてYMMV ...
ここでは、ハッシュがどのように構築されるかを説明します。キーのユニバースはかなり大きく、ハッシュ関数は「非常に単射」になるように構築されているため、衝突がめったに起こらないため、ハッシュ テーブルのアクセス時間は実際には O(1) ではありません ...ある確率に基づくもの。しかし、ハッシュのアクセス時間は、ほとんどの場合、時間 O(log_2(n)) よりも短いと言っても過言ではありません。
答えは場合によります。要素数「n」が非常に大きいと考えてみましょう。衝突の少ない、より優れたハッシュ関数を作成するのが得意な場合は、ハッシュが最適です。
なお、
ハッシュ関数は検索時に一度だけ実行され、対応するバケットに誘導されます。したがって、n が高くても大きなオーバーヘッドにはなりません。
ハッシュ テーブルの問題:
しかし、ハッシュ テーブルの問題は、ハッシュ関数が適切でない場合 (より多くの衝突が発生する場合)、検索が O(1) ではないことです。バケット内の検索は線形検索であるため、O(n) になる傾向があります。二分木よりも悪い場合があります。
バイナリ ツリーの問題:
バイナリ ツリーでは、ツリーのバランスが取れていないと、O(n) になる傾向があります。たとえば、リストである可能性が高い二分木に 1,2,3,4,5 を挿入した場合。
したがって、
適切なハッシュ手法が見られる場合は、ハッシュテーブルを使用してください。そうでない場合は、バイナリ ツリーを使用することをお勧めします。
もちろん、このような大きなデータセットではハッシュが最速です。
データがめったに変更されないため、さらに高速化する 1 つの方法は、アドホック コードをプログラムで生成して、検索の最初の層を巨大な switch ステートメントとして実行し (コンパイラがそれを処理できる場合)、分岐して検索することです。結果のバケット。