タプルを格納し、次のようなクエリを実行できるデータ構造が必要です。(x,y,z)整数のタプルを指定して、次のタプルを見つけます (その上向きの境界)。つまり、自然順序付けを考慮するということ(a,b,c)<=(d,e,f) <=> a<=d and b<=e and c<=fです。アイテムをバケットに分割してソートするMSD基数ソートを試しました（タプルのすべての位置に対して再帰的に実行します）。他に何か提案はありますか？理想的には、上記のクエリが O(log n) 内で発生するようにしたいと思います。ここで、n はタプルの数です。
質問する
221 次
1 に答える
2
2 つのオプション。
ソートされた配列で二分探索を使用します。(a<<64)|(b<<32)|c を使用してキー (32 ビット int を想定) を構築し、それらを単純な配列に保持し、一方を他方の横にパックすると、バイナリ検索を使用して値を見つけることができます。あなたが探しているのは（Cを使用している場合、これを行うためのライブラリ関数さえあります）、次のものは単に1つの位置にあります。最悪の場合のパフォーマンスは O(logN) です。http://en.wikipedia.org/wiki/Interpolation_searchを実行できる場合は、O(log log N) に近づく可能性もあります。
バイナリ キーの問題は、新しい値を追加するのが難しい場合があり、使用可能なメモリを超える場合は回転が必要になる場合があります。しかし、それは高速で、平均して数回のランダム メモリ アクセスしかありません。
または、何らかの形式で a|b|c を使用してキーを生成してハッシュ テーブルを作成し、次の値を含む構造体を指すハッシュ データを作成することもできます。テーブルを生成するときは、次の値をすでに知っている必要があるため、最初に作成するのが少し難しいかもしれません。
ハッシュ アプローチの問題点は、二分探索法よりも多くのメモリを使用する可能性が高いことです。ハッシュの衝突が発生しなければパフォーマンスは優れていますが、場合によってはこのアルゴリズムに役立つバリエーションがありますが、パフォーマンスは低下し始めます。ハッシュ アプローチは、新しい値を挿入するのがおそらくはるかに簡単です。
また、これらの行に沿って同様の質問があったこともわかりました。私が言っていることの本質は、A、b、c を組み合わせて単一の長いキーを生成し、それをバイナリ検索、ハッシュ、または b ツリーで使用することだと思います。キーの長さが問題 (言語) である場合、それを文字列として扱うことができますか?
この回答が完全にベースから外れている場合は、お知らせください。この回答を削除できるかどうかを確認します。そのため、役に立たない回答ではなく、回答されていないままになります。
于 2013-03-21T08:05:30.083 に答える