1

integer があるとしましょうn。たとえば、重複しない整数範囲のリストがあるとします。

1-9
99-105
160-205
503-600
// many more thousands of ranges, etc ....

これらすべてを非常に簡単に繰り返し処理し、n が各境界の間にあるかどうかを確認し、そうであれば true を返すことができます。それは O(n) であり、これは悪いことです。これは O(1) で実行できますか?

いくつかのルール:

  • 整数自体は非常に大きく、範囲も非常に広いため、受け入れ可能な整数の完全なリストを取得し、Set のようなものを使用して O(1) ルックアップを行うことは現実的ではありません。多くの整数をメモリに格納するのはコストがかかりすぎます。境界のリストしか保存できません。
  • このテストを何度も実行するので、リストを事前に何らかのデータ構造に作成できます。これにより、後続のルックアップがより効率的になります。

これらの範囲のバイナリ表現を取得し、O(log(n)) を生成するツリーを構築できると思います。

私の本当の質問

IP アドレス サブネットのリストがあります。特定の IP がこれらのサブネットのいずれかにあるかどうかをテストする必要があります。確認するIPがたくさんあります。IP を整数に変換できます (1.2.3.4 => 1*2^32 + 2*2^16 + 3*2^8 + 4)。サブネットも同様に変換できます。これは、上記の「説明しやすい」質問に相当します。

ありがとう！

4

1 に答える 1

0

並べ替えられたベクトルに範囲を格納し、std::lower_bound で値を検索するのは O(log(n)) です。

そのアルゴリズムで IP 200.200.200.200 に必要な整数のサイズは? 200200200200だけではないのはなぜですか？

サブネットを格納するための IP ABCD の 4 つのブランチ ツリーの方が適切と思われます。

于 2016-11-18T02:05:03.017 に答える