6

多くの整数範囲を管理する JavaScript プログラムがあります。このコンテキストでは、範囲は単に開始値と終了値 (または開始値と長さの値などの同等のもの) であり、別のオブジェクトへの参照があります。範囲はオーバーラップすることも、同一にすることもできます (ただし、参照されるオブジェクトは異なります)。

可能な開始値と終了値は 0 から 4294967295 (2 32 - 1 または0xFFFFFFFF) の間ですが、ドメインには部分的にであっても範囲がカバーされない大きな「穴」がいくつかあります。ほとんどの範囲は、可能性の領域に比べて非常に小さくなります。圧倒的多数の範囲の長さは 2000 未満になると予想されます。

この構造体の最も重要な使用例は、特定の整数値を含むすべての範囲を検索することです。ほとんどの場合、ルックアップが失敗することが予想されます (指定された値を含む範囲はありません)。

それ以外の場合は、明らかに要素を追加する必要があり (頻繁に)、そこから要素を削除する必要があります (めったにありません)。また、ときどき、単一の値を含むすべての範囲ではなく、特定の範囲と重複するすべての範囲を検索する必要があります。

そのためにどのようなデータ構造を使用できますか? ほとんどの場合、検索は失敗するため、範囲のリストでの線形検索は実用的ではありません。非常に頻繁にルックアップを行う必要があります。

4

4 に答える 4

1

キーが開始 (低) 値である二分木。キーを見つけたら、かなり簡単に広く（上下に）見ることができます。

于 2012-04-24T23:55:51.490 に答える
0

System.Tuple は、このようなもの [または F# のリストですが、F# を知っている人はほとんどいません] が好きです。

タプル nums = (start, end) として開始整数と終了整数を簡単に持つことができる範囲が連続している場合Tuple nums = ((start, end), List) があなたのために働くかもしれません。

于 2012-04-24T23:23:00.253 に答える
0

試行 1:

2 つのバイナリ ツリーを保持します。1 つは開始値用、もう 1 つは終了値用です。両方のツリー (または単に「終了」) のノードに、ID (範囲の開始値) によって一意の範囲を参照するプロパティを持たせます。

「開始」ツリーでバイナリ検索を実行して、開始が検索値以下の範囲にリストを絞り込みます。値が検索値以上の「終了」ツリーで同じことを行います。両方のツリーからノードの交点を見つけます。これらの範囲には検索値が含まれています。

最適なパフォーマンスを得るために、ハッシュ マップ/セットを使用して交差点を見つけることができます。

試行 2:

キーが最初であるが、開始値と終了値の両方で共有される多くのビットである間隔のハッシュ リストを保持するとどうなるでしょうか?

したがって、開始が「11001101」で終了が「11010010」の場合、キーは「110」です。各キーは、キーを共有する範囲 (開始と終了) のリストにマップされます。

たとえば、「00101111」のように値を検索して値の範囲を確認する場合、ハッシュ リストで n 個の異なる値を検索する必要があります。ここで、n はビット数 (この場合は 32) です。この場合、「00101111」、「0010111」、「001011」などを検索します。ヒットごとに、検索値が範囲内にあるかどうかを実際に確認する必要があります。

一見すると、平均して、ヒットごとに半分が誤検知になるように見えますが、ヒット数が少ない場合は問題にならず、キーが大きいほどヒット数が少なくなります。 .

たとえば、'00101110' の開始と '01100111' の終了では、キーが '0' になるため、かなりの数の '誤検知' が発生するため、若干の問題があります。'001' と '01' の 2 つの異なるキーがあった方がよいでしょうが、この最適化のためにコーディングする必要がある特定のアルゴリズムについてはわかりません。範囲が十分に小さく、この問題を解決または見落とすことができる場合は、ほとんどのキーが比較的長く、検索に一致しないため、非常に高速に検索できます。

于 2012-04-25T00:16:26.440 に答える
0

すべての範囲の開始と終了を 1 つのリストにマップとして保存すると、範囲インデックスに戻ることができます。ie mylist = [ {45: range1}, {47: range2}, {55: range1}, {57:range2} ] 次に、リストをスキャンして、最初にタグが表示されたときにブール値 true を設定し、タグが false に設定されます。見るのは二度目。自分の数値よりも高い数値を見つけた場合、自分がどの範囲内にいるかを知ることができます。bisect を使用して O(logn) を挿入できますが、削除と挿入は O(n) です。幸運を！〜ベン

于 2012-04-24T23:29:38.007 に答える