Che collegata Lista regolazioni struttura dei dati mi avrebbe dato ricerca veloce casuale?

Question

Attualmente sto usando una lista doppiamente collegata (C ++ std::list) a tenere una serie di record che hanno ciascuno un identificativo unico intero. La lista collegata si crea in modo ordinato in modo tale che nella lista, la voce successiva ha sempre un identificatore univoco più grande rispetto al suo predecessore.

Il problema che sto affrontando è che di tanto in tanto ho bisogno di essere in grado di inserire rapidamente un elemento nella sua posizione relativa e ordinato con una pianura mezzo lista collegata di questa operazione è di $ O (n) $ che sta causando problemi di prestazioni per me . In generale, questo vorrebbe dire che voglio usare qualcosa di simile a un albero binario (C ++ std::map), però, sono anche a seconda della seguente caratteristica di una lista doppiamente collegata per ottenere buone prestazioni:

• Possibilità di unire una sezione contigua fuori da una lista concatenata in un altro a $ O (1) $ tempo. (Ammortizzato $ O (1) $ o $ O (\ log \ log n) $ sarebbe abbastanza buono.)

Una caratteristica dei miei dati che vorrei leva finanziaria è che ho spesso lunghi intervalli di record contigui, dove di ciascuno unico intero è esattamente uno in più rispetto al suo predecessore. Durante la ricerca per la posizione ordinata relativa di un elemento, sarebbe sempre essere al di fuori di tali dischi contigui poiché non ci sono identificatori duplicati.

Mi piacerebbe trovare una struttura di dati sostituzione o l'aumento di una doppia lista collegata che mi permetterà di continuare a unire intere sezioni da una lista all'altra in tempo costante, ma mi permette di individuare la posizione ordinata in cui inserire un nuovo record nel migliore di $ O (n) $ tempo.

Altre operazioni sono in avanti e all'indietro l'iterazione tra gli elementi. Gli indici di registrazione iniziano a zero e si sviluppano verso l'alto di 64 bit, generalmente in sequenza, e il codice funziona bene in questi casi. Di tanto in tanto alcuni record non sono disponibili prima di quelli successivi, è l'inserimento di questi record mancanti che causano i problemi di prestazioni ora.

Un possibile approccio che viene in mente è quello di memorizzare nella cache la posizione dei diversi indici. La cache otterrebbe invalidato ogni volta che una giunta di rimuovere gli elementi che potrebbero sovrapporsi le voci memorizzate nella cache. Con questa cache, invece di fare una ricerca lineare, la ricerca potrebbe invece iniziare dal iteratore punto di cache di cui indice unico è più vicino a quello la cui posizione viene cercato. Tuttavia, mi piacerebbe utilizzare più pienamente la caratteristica dei record contigui. Ho anche pensato di una lista collegata gerarchico dove ho un livello superiore lista concatenata di regioni contigue, in cui ogni regione è una lista concatenata di record che sono consecutivi, ma non ho visto un modo pulito per adattare una lista collegata di fornire questo funzionalità. Forse qualcosa di simile è stato fatto prima? Trovo skip list per essere vicino, ma non vedo la funzionalità di giunzione (), oltre a un elenco di salto generica non vorrei sfruttare il fatto che l'inserimento non si verifica all'interno record contigui.

Answer 1

Un approccio semplice potrebbe essere quella di utilizzare una lista doppiamente concatenata di estensioni, in cui ogni misura rappresenta una sequenza di record contigui. I record all'interno di ogni misura potrebbero a loro volta essere rappresentati con una doppia lista collegata.

Ciò preserva la capacità di fare $ O (1) $ tempo splicing, e ora l'operazione di inserimento prende $ O (k) $ tempo, dove $ k $ è il numero di estensioni (invece di $ O (n) $ , dove $ n $ è il numero di record). Se si dispone di molti meno estensioni di record, questo potrebbe essere un parziale miglioramento.

Non so se questo sarà meglio di un semplice elenco di salto o un albero binario.

Si noti che se si utilizza un albero binario, si può ancora fare splicing efficiente. L'operazione di giunzione non è più $ O (1) $ tempo, ma può essere fatto in $ O (\ log \ ell) $ tempo, dove $ \ ell $ è il numero di record nel segmento impiombato. Questo non è così veloce da $ O (1) $ tempo tranciati, ma a seconda della frequenza relativa delle vostre diverse operazioni, è un'altra struttura dati che si potrebbe prendere in considerazione (ad esempio, punto di riferimento su insiemi di dati realistici).

E, naturalmente, è possibile combinare queste idee, per esempio, con un albero binario di estensioni, in cui ogni punto è a sua volta una lista doppiamente concatenata di record contigui. Inserti prenderanno $ O (\ lg k) $ tempo, e la giunzione può essere realizzata in $ O (\ lg \ ell) $ tempo (entrambi i quali potrebbe potenzialmente essere migliore di $ O (\ lg n) $ realizzato attraverso un semplice albero binario).