Biorąc pod uwagę poniższą listę, jeśli zakresy adresów IP.

LOW           HIGH
192.168.10.34 192.168.11.200
200.50.1.1    200.50.2.2

Zakładając, że iterowanie wszystkich adresów we wszystkich zakresach i przechowywanie ich w HashSet spowoduje zbyt duże zużycie pamięci.

Musimy więc zachować zakresy, które i tak są po prostu przesuniętymi liczbami (niskie i wysokie). W jaki sposób można przechowywać zakresy w drzewie, a następnie użyć wydajnego wyszukiwania, aby sprawdzić, czy określony adres należy do zakresu (zakresów).

Sprawdziłem RangeTree, ale wydaje się, że szukam punktów w samolot kartezjański i wydaje się, że nie pasuje do mojego przypadku użycia. KDTree pozwala na wyszukanie najbliższego sąsiada, a gdy k == 2 to w zasadzie to samo, co drzewo zasięgu.

Chciałbym wszystkie dopasowania, ponieważ może być wiele trafień.

Co by tu działało? Jestem przekonany, że jest to rozwiązany problem.

5
Jim 13 marzec 2020, 12:17

2 odpowiedzi

Najlepsza odpowiedź

Standardowa TreeMap będzie tak, zakładając, że nie masz nakładających się zakresów.

Po prostu utwórz TreeMap, z kluczem dolnym końcem zakresu, z pełnym zakresem jako wartością. Znajdź zakres za pomocą {{X1 }} i sprawdź, czy wartość mieści się w zakresie.

Przykład użycia prostego obiektu Integer zamiast IpAddress, ale dowolny obiekt Comparable może być użyty jako granice zakresu.

public final class RangeMap<T extends Comparable<T>> {
    private TreeMap<T, Range<T>> map = new TreeMap<>();
    public void add(Range<T> range) {
        Entry<T, Range<T>> entry = this.map.floorEntry(range.getUpperInclusive());
        if (entry != null && entry.getValue().overlaps(range))
            throw new IllegalArgumentException("Overlap: " + range + " vs " + entry.getValue());
        entry = this.map.ceilingEntry(range.getLowerInclusive());
        if (entry != null && entry.getValue().overlaps(range))
            throw new IllegalArgumentException("Overlap: " + range + " vs " + entry.getValue());
        this.map.put(range.getLowerInclusive(), range);
    }
    public boolean contains(T value) {
        Entry<T, Range<T>> entry = this.map.floorEntry(value);
        return (entry != null && entry.getValue().contains(value));
    }
    public Range<T> get(T value) {
        Entry<T, Range<T>> entry = this.map.floorEntry(value);
        return (entry != null && entry.getValue().contains(value) ? entry.getValue() : null);
    }
}
public final class Range<T extends Comparable<T>> {
    private final T lowerInclusive;
    private final T upperInclusive;
    public Range(T lowerInclusive, T upperInclusive) {
        this.lowerInclusive = lowerInclusive;
        this.upperInclusive = upperInclusive;
    }
    public T getLowerInclusive() {
        return this.lowerInclusive;
    }
    public T getUpperInclusive() {
        return this.upperInclusive;
    }
    public boolean contains(T value) {
        return (value.compareTo(this.lowerInclusive) >= 0 &&
                value.compareTo(this.upperInclusive) <= 0);
    }
    public boolean overlaps(Range<T> that) {
        return (this.lowerInclusive.compareTo(that.upperInclusive) <= 0 &&
                this.upperInclusive.compareTo(that.lowerInclusive) >= 0);
    }
    @Override
    public String toString() {
        return "(" + this.lowerInclusive + "-" + this.upperInclusive + ")";
    }
}

Testuj

RangeMap<Integer> map = new RangeMap<>();
map.add(new Range<>(50, 59));
map.add(new Range<>(70, 79));
for (int i = 40; i <= 90; i += 3)
    System.out.println(i + ": " + map.contains(i));

Wyjście

40: false
43: false
46: false
49: false
52: true
55: true
58: true
61: false
64: false
67: false
70: true
73: true
76: true
79: true
82: false
85: false
88: false
2
Andreas 13 marzec 2020, 10:17

Jeśli dobrze to rozumiem, masz listę zakresów i chcesz umieścić je w strukturze, aby można było szybko znaleźć zakresy, w których znajduje się dana wartość.

Możesz utworzyć pojedyncze drzewo wyszukiwania binarnego, które przechowuje każdą wartość, która jest końcem zakresu (prawdopodobnie wraz z 0.0.0.0) i zapętlać do przodu po utrzymaniu zestawu zakresów, w których znajduje się bieżąca wartość i ustawieniu kopii tego ponieważ dane każdego węzła po osiągnięciu go, a następnie aby znaleźć zakresy, w których znajduje się dany adres IP, po prostu użyj wyszukiwania binarnego, aby znaleźć najwyższą wartość graniczną poniżej, a zestaw powiązany z tą wartością byłby zbiorem zakresy, w których znajduje się dany adres IP.

Wymagałoby to O (n ^ 2) użycia pamięci (i prawdopodobnie O (n ^ 2) czasu na zbudowanie struktury, przy założeniu, że kopiowanie trwa liniowo w zależności od rozmiaru kopiowanych danych, czego nie pamiętam) , ale pojedyncze zapytanie byłoby O (logn) czas.

Oto zdjęcie, ponieważ czuję, że to nie jest świetne wyjaśnienie:

A graphical representation of the data structure

1
The Zach Man 13 marzec 2020, 09:58