4

約90000のIPv4アドレス範囲があり、各範囲にデータが関連付けられています

例えば

1.0.0.0 - 1.1.0.0 ->  "foo"
2.0.0.0 - 10.0.0.0 -> "bar"

IPアドレスを指定して、関連データを取得する必要があります。どうすればこれを効率的に行うことができますか？

アドレスを単一の整数に変換することで作業が簡単になると思いますが、高速検索を可能にするためにこれを格納するためにどのデータ構造を使用するのが最適でしょうか？

明確化-範囲ではなく単一のIPで検索しています（例：「192.168.0.1」）

ありがとう

4

3 に答える 3

4

重複しない間隔の終わりを単一の配列に並べ替えます。次のように、間隔の開始か終了かを示すフラグで各終了をマークします。

1.0.0.0 1.1.0.0 2.0.0.0 10.0.0.0
 start   end     start    end

次に、ターゲットアドレス（たとえば、）を使用してバイナリ検索を実行します3.2.1.0。挿入ポイントは2.0.0.0、としてマークされているになりstartます。これは、それ3.2.1.0が間隔の1つであることを意味します。

次に、の検索を検討して1.2.3.4ください。その挿入ポイントは1.1.0.0、としてマークされているになりendます。1.2.3.4はに等しくないので、それは区間の1つではない1.1.0.0ことがわかります。1.2.3.4

検索のコストはですLog(N)。ここNで、は間隔の数です。

冒険心がある場合は、の実装を検討してinterval treeください。ただし、これは重複しない間隔ではおそらく価値がありません。

于 2012-05-19T21:11:33.580 に答える
1

IPv6 アドレスではなく IPv4 アドレスのみをサポートする必要がある場合は、各アドレスをUInt32. これにより、それらを非常に簡単かつ効率的に比較できます。

IP 範囲が重複しておらず、リスト内でソートしておくことができる場合は、バイナリ検索のバリエーションを使用して範囲をすばやく見つけることができます。

于 2012-05-19T21:02:00.697 に答える
0

次の範囲で、0 から 20 までの数値を検索します。

2-5 -> "a"
6-7 -> "b"
9-11 -> "c"
12-12 -> "d"
15-18 -> "e"
19-19 -> "f"

RangeCollection の作成と初期化を 1 回含む 1,000,000 回のループ内: わずか 3 秒!

あとは、Tuple の IEnumerable を準備するだけです。ここで、最初の int は最小 IP int 値、2 番目は最大値、TValue はその min~max 範囲に関連付けられたデータです。

これが私の実装です：

public class RangeCollection<TValue>
{
    private readonly int[] _mins;
    private readonly int[] _maxs;
    private readonly TValue[] _values;

    public RangeCollection(params Tuple<int, int, TValue>[] input)
        : this((IEnumerable<Tuple<int, int, TValue>>)input)
    {
    }

    public RangeCollection(IEnumerable<Tuple<int, int, TValue>> input)
    {
        var tuples = input.OrderBy(tuple => tuple.Item1).ToArray();

        for (var i = 1; i < tuples.Length; i++)
        {
            if (tuples[i].Item1 <= tuples[i - 1].Item2)
            {
                throw new ArgumentException("Ranges should not overlap.");
            }
        }

        this._mins = new int[tuples.Length];
        this._maxs = new int[tuples.Length];
        this._values = new TValue[tuples.Length];

        for (var i = 0; i < tuples.Length; i++)
        {
            var tuple = tuples[i];

            this._mins[i] = tuple.Item1;
            this._maxs[i] = tuple.Item2;
            this._values[i] = tuple.Item3;
        }
    }

    public bool TryGetValue(int key, out TValue value)
    {
        if (this.Contains(key, out key))
        {
            value = this._values[key];
            return true;
        }

        value = default(TValue);
        return false;
    }

    public bool Contains(int key)
    {
        return this.Contains(key, out key);
    }

    private bool Contains(int key, out int index)
    {
        index = 0;

        if (this._mins.Length == 0 || key < this._mins[0] || key > this._maxs[this._maxs.Length - 1])
        {
            return false;
        }

        var low = 0;
        var high = this._mins.Length - 1;

        while (high >= low)
        {
            index = (low + high) / 2;

            var cmp = this._mins[index].CompareTo(key);

            if (cmp == 0)
            {
                return true;
            }

            if (cmp == 1)
            {
                high = index - 1;
            }
            else
            {
                low = index + 1;
            }
        }

        if (this._mins[index] > key)
        {
            index--;
        }
        else if (this._mins[index + 1] <= key)
        {
            index++;
        }

        return this._maxs[index] >= key;
    }
}

使用法：

var collection = new RangeCollection<string>(new Tuple<int, int, string>(2, 5, "a"),
                                             new Tuple<int, int, string>(6, 7, "b"),
                                             new Tuple<int, int, string>(9, 11, "c"),
                                             new Tuple<int, int, string>(12, 12, "d"),
                                             new Tuple<int, int, string>(15, 18, "e"),
                                             new Tuple<int, int, string>(19, 19, "f"));

for (var i = 0; i <= 20; i++)
{
    string val;
    if (collection.TryGetValue(i, out val))
    {
        Debug.WriteLine("Contains {0}. Value: {1}", i, val);
    }
    else
    {
        Debug.WriteLine("Doesn't contain " + i);
    }
}

/* Output:

Doesn't contain 0
Doesn't contain 1
Contains 2. Value: a
Contains 3. Value: a
Contains 4. Value: a
Contains 5. Value: a
Contains 6. Value: b
Contains 7. Value: b
Doesn't contain 8
Contains 9. Value: c
Contains 10. Value: c
Contains 11. Value: c
Contains 12. Value: d
Doesn't contain 13
Doesn't contain 14
Contains 15. Value: e
Contains 16. Value: e
Contains 17. Value: e
Contains 18. Value: e
Contains 19. Value: f
Doesn't contain 20

*/
于 2012-05-19T22:50:45.063 に答える