2

互いに素な整数区間のセットがあり、特定の整数がこれらの区間の1つにあるかどうかを確認したいと思います。もちろん、これは対数時間での二分探索によって達成できます。ただし、クエリの大部分は戻りfalseます。つまり、任意の間隔に存在する整数はごくわずかです。アプリケーションを高速化するために、与えられた整数が間違いなくないか、あるいは間隔内にあるかどうかを教えてくれる確率的で一定時間のアルゴリズム（ある種のハッシュ関数）を探しています。これは、目的のアルゴリズムのスケッチです。ここでは、にmagic_data_structure格納されている間隔で初期化されtreeます。

x = some_integer;
if(!magic_data_structure.find(x))
  return false; // definitely not in any interval
return tree.find(x); // binary search on tree

文学のアイデアやヒントはありますか？よろしくお願いします！

PS：（上記のものとは異なり）他の区間を含む可能性のある重複しない区間の区間木の改善を知っている人はいますか？

4

1 に答える 1

1

これは素朴な解決策ですが、一定です。

非常に大量の数値を扱っていない場合は、キーが数値で、値がそれらが含まれるセットへのポインターであるハッシュ テーブルを使用できます。もちろん、大量のデータがある場合は、この方法で索引付けするには、時間がかかりすぎる (そしてメモリが多すぎる) 場合があります。

それらを保存/検索するためのさまざまな素集合のデータ構造とアルゴリズムがあるように見えますが、それらのいずれかが一定の時間を持っているかどうかは疑問です。

于 2013-06-12T03:00:33.620 に答える