So suchen Sie nach einem Bereich aus einer Reihe zusammenhängender Bereiche für eine bestimmte Zahl

Question

Also einfach gesagt, das ist es, was ich zu tun versuche:

Ich habe eine Sammlung von Range Aneinandergrenzende Objekte (nicht überlappend, ohne Lücken zwischen ihnen), die jeweils ein enthalten start Und end int und ein Verweis auf ein anderes Objekt obj.Diese Bereiche haben keine feste Größe (der erste könnte 1–49 sein, der zweite 50–221 usw.).Diese Sammlung könnte recht groß werden.

Ich hoffe, eine Möglichkeit zu finden, den Bereich (oder genauer gesagt das Objekt, auf das er verweist) nachzuschlagen, der eine bestimmte Zahl enthält, ohne die gesamte Sammlung durchlaufen zu müssen und jeden Bereich daraufhin zu prüfen, ob er die Zahl enthält.Diese Suchvorgänge werden häufig durchgeführt, daher ist Geschwindigkeit/Leistung von entscheidender Bedeutung.

Kennt jemand einen Algorithmus/eine Gleichung, die mir hier weiterhelfen könnte?Ich schreibe in Java.Ich kann bei Bedarf weitere Details bereitstellen, aber ich dachte, ich würde versuchen, es einfach zu halten.

Danke.

Answer 1

Wenn es so klingt, als ob Sie a verwenden möchten TreeMap, wobei der Schlüssel das untere Ende des Bereichs und der Wert der ist Range Objekt.

Um dann den richtigen Bereich zu ermitteln, verwenden Sie einfach das floorEntry() Methode, um sehr schnell den nächsten (kleineren oder gleichen) Wert zu erreichen Range, die den Schlüssel enthalten sollte, etwa so:

    TreeMap<Integer, Range> map = new TreeMap<>();
    map.put(1, new Range(1, 10));
    map.put(11, new Range(11, 30));
    map.put(31, new Range(31, 100));

    // int key = 0; // null
    // int key = 1; // Range [start=1, end=10]
    // int key = 11; // Range [start=11, end=30]
    // int key = 21; // Range [start=11, end=30]
    // int key = 31; // Range [start=31, end=100]
    // int key = 41; // Range [start=31, end=100]
    int key = 101; // Range [start=31, end=100]
    // etc.

    Range r = null;
    Map.Entry<Integer, Range> m = map.floorEntry(key);
    if (m != null) {
        r = m.getValue();
    }
    System.out.println(r);

Da der Baum immer nach der natürlichen Reihenfolge der unteren Bereichsgrenze sortiert wird, werden alle Ihre Suchvorgänge im schlimmsten Fall O(log(n)) sein.

Sie sollten eine Plausibilitätsprüfung hinzufügen, wenn Ihr Schlüssel vollständig außerhalb der Grenzen liegt (wenn sich der Schlüssel beispielsweise außerhalb des Endes der Karte befindet, wird der letzte zurückgegeben). Range in der Karte), aber dies sollte Ihnen eine Vorstellung davon geben, wie es weitergeht.

Answer 2

Unter der Annahme, dass Ihre Suchvorgänge von größter Bedeutung sind und Sie O(N) Speicher und ungefähr O(N^2) Vorverarbeitungszeit einsparen können, würde der Algorithmus wie folgt aussehen:

• eine Klasse vorstellen ObjectsInRange, was beinhaltet:Bereichsanfang (int startOfRange) und eine Reihe von Objekten (Set<Object> objects)
• einführen ArrayList<ObjectsInRange> oir, die enthalten wird ObjectsInRange sortiert nach startOfRange
• für jede Range r, stellen Sie sicher, dass es vorhanden ist ObjectsInRange (nennen wir sie a Und b) so dass a.startOfRange = r.start Und b.startOfRange = b.end.Dann für alle ObjectsInRange x zwischen a, und bis (aber nicht einschließlich) b, hinzufügen r.obj zu ihren x.objects Satz

Die Suche sieht dann wie folgt aus:

• für Ganzzahl x, finde solche i Das oir[i].startOfRange <= x Und oir[i+1].startOfRange > x
• Notiz: i kann mit Halbierung in O(log N)-Zeit gefunden werden!
• Deine Objekte sind oir[i].objects

Answer 3

Wenn die Sammlung in Ordnung ist, können Sie eine binäre Suche implementieren, um den richtigen Bereich in O(log(n))-Zeit zu finden.Es ist nicht so effizient wie Hashing für sehr große Sammlungen, aber wenn Sie weniger als etwa 1000 Bereiche haben, ist es möglicherweise schneller (weil es einfacher ist).