Struttura dati/Algoritmo per la ricerca di sezioni

Question

Che tipo di infrastruttura/algoritmo dovrei usare per cercare in quale sezione si trova attualmente, dato un elenco di endpoint di ogni sezione?

Per esempio, se ho una pagina web con le intestazioni delle sezioni e dei contenuti,

• Introduzione (termina a 100px)
• sezione 1 (termina a 350px)
• Sezione 2 (termina a 700px)
• Conclusione (termina a 1200px)
• commenti

e sono attualmente a 130px, dovrebbe restituire che sono attualmente in "Sezione 1".

Opzione 1

ricerca binaria attraverso gamma di endpoint

from bisect import bisect_left 

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

Tuttavia, questo potrebbe ancora prendere O (log n) per ogni cambiamento di posizione.

Opzione 2

tabella hash di ricerca della posizione corrente,

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

Questo è veloce, ma spreca un sacco di spazio

---

Esiste un generale dei dati struttura/algoritmo che si occupa di questo tipo di problema?

Answer 1

Mi piace la prima opzione, le ricerche binarie sono molto efficienti per la scansione e, come dici tu, la seconda opzione non è efficiente in termini di spazio.

La soluzione tradizionale e molto generica che si adatta alla grafica computerizzata è una 2d k-tree, che crea un albero che può essere consultato per coordinate senza sprecare memoria. Specificamente le sue complessità di ricerca, rimozione e inserimento sono tutte O (log n) e la sua complessità spaziale è O (n).

Dato che si sta facendo solo un asse e una pagina web tenderà ad avere 1-100 sezioni (ed è improbabile che abbia migliaia, figuriamoci milioni o miliardi di sezioni), allora personalmente prenderei in considerazione l'idea di array molto semplice e quindi passare a un k-tree più complesso quando c'è un beneficio/bisogno misurabile. Se stai scrivendo questo in C o in un'altra lingua che ti dà un po 'di controllo sul layout della memoria, allora una serie di strutture sarebbe eccezionalmente veloce da scansionare a causa del design delle moderne cpu e gerarchie di memoria (in particolare prefetcher e caching).

Answer 2

Più semplice ed efficace è utilizzare una ricerca binaria con complessità O (LogN).

La seconda opzione ha una maggiore complessità O (1), ma presenta uno svantaggio con la pre-popolazione. Pre-popolazione per la ricerca binaria più semplice.

Entrambi questi approcci sono i migliori se non si aggiornano le sezioni in fase di esecuzione.

Strutture dati necessarie se è necessario aggiungere/eliminare/aggiornare il tempo di esecuzione delle sezioni. Poiché ci si avvicina al necessario aggiornare i dati pre-compilati con O (N). Significa che le operazioni di aggiornamento/aggiunta/eliminazione della sezione possono richiedere fino a O (N).