Datenstruktur/Algorithmus für Abschnittsübersichten

Question

Welche Art von Datenstruktur/Algorithmus sollte ich verwenden, um in einer Liste der Endpunkte jedes Abschnitts nachzuschlagen, in welchem ​​Abschnitt Sie sich gerade befinden?

Zum Beispiel, wenn ich eine Webseite mit Abschnittsüberschriften und Inhalt haben,

• Einführung (endet bei 100px)
• Abschnitt 1 (endet bei 350px)
• Abschnitt 2 (endet bei 700px)
• Schlussfolgerung (endet bei 1200px)
• Kommentare

und ich bin momentan bei 130px, sollte es zurückgeben, dass ich gerade in "Section 1" bin.

Option 1

Binary Durchsuchung Array von Endpunkten

from bisect import bisect_left 

arr = [100, 350, 700, 1200] 
pos = bisect_left(arr, 130, 0, arr[-1]) 

Dies könnte jedoch noch nehmen O (log n) für jede Änderung in der Position.

Option 2

Hash Lookup-Tabelle der aktuellen Position,

lookup = {0: "Introduction" 
      1: "Introduction" 
      ... 
      10: "Section 1" 
      11: "Section 1" 
      ... 
     } 
section = lookup[130/10] 

Dies ist schnell, aber es verschwendet viel Platz

---

Gibt es eine Struktur allgemeine Daten/Algorithmus das geht mit dieser Art von Problem?

Answer 1

Ich mag Ihre erste Option, binäre Suchen sind sehr effizient zum Scannen und wie Sie sagen, die zweite Option ist nicht platzsparend.

Die traditionelle und sehr generische Lösung, die in Computergrafiken skaliert ist eine 2d k-tree, die einen Baum erstellt, der nach Koordinaten gesucht werden kann, ohne Speicher zu verschwenden. Insbesondere sind seine Such-, Entfernungs- und Einfügekomplexitäten alle 0 (log n) und seine Raumkomplexität ist O (n).

Vorausgesetzt, dass Sie nur eine Achse tun, und eine Webseite wird in der Regel 1-100 Abschnitte haben (und ist unwahrscheinlich, Tausende zu haben, geschweige denn Millionen oder Milliarden von Abschnitten), dann würde ich persönlich mit einem gehen sehr einfache Array und dann bewegen sich zu einem komplexeren k-Baum, wenn es einen messbaren Nutzen/Bedarf gibt. Wenn Sie dies in C oder in einer anderen Sprache schreiben, die Ihnen eine gewisse Kontrolle über das Speicherlayout gibt, wäre ein Array von Strukturen aufgrund des Designs moderner CPU- und Speicherhierarchien (insbesondere Vorablesefunktionen und Caching) außergewöhnlich schnell zu scannen.

Answer 2

Am einfachsten und effektivsten ist eine binäre Suche mit O (LogN) Komplexität.

Sie zweite Option haben eine bessere Komplexität O (1), aber haben Nachteile mit der Vor-Population. Pre-Population für die binäre Suche einfacher.

Diese beiden Ansätze eignen sich am besten, wenn Sie Abschnitte in der Laufzeit nicht aktualisieren.

Datenstrukturen erforderlich, wenn Sie die Laufzeit der Abschnitte hinzufügen/löschen/aktualisieren müssen. Weil Sie erforderliche ODBC-Daten mit O (N) aktualisieren. Dies bedeutet, dass die Operationen zum Aktualisieren/Hinzufügen/Löschen von Abschnitten bis zu O (N) dauern können.