Che cos'è una lista quad-linked?

Question

Attualmente sto lavorando all'implementazione di una struttura di tipo lista al lavoro, e ho bisogno che sia pazzesca efficace. Nella mia ricerca di strutture di dati efficaci mi sono imbattuto in un brevetto per una lista di quad mi piace, e questo ha suscitato il mio interesse abbastanza da farmi dimenticare il mio compito attuale e iniziare a studiare la lista quad invece. Sfortunatamente, internet era molto riservato riguardo al tutto, e Google non ha prodotto molto in termini di risultati utilizzabili. L'unica spiegazione che ho ottenuto è stata la descrizione del brevetto che ha dichiarato:

Una struttura di dati quad collegata che fornisce funzionalità di ricerca bidirezionale per più campi correlati all'interno di un singolo record. La base di dati viene ricercata fornendo serie di puntatori a intervalli di voci di dati N per soddisfare una ricerca binaria dei puntatori seguita da una ricerca lineare della gamma risultante per individuare una voce di interesse e il relativo campo correlato.

Questo, purtroppo, solo mi rende più perplesso, come non posso avvolgere la mia testa intorno la spiegazione non-laico. Quindi, quindi, mi rivolgo a tutti voi nella speranza che possiate spiegarmi cosa sia veramente questa storia legata al quad, poiché so che non sapendo mi guiderà su e giù abbastanza velocemente.

Sai cosa è una lista quad-linked?

Answer 1

Non ho mai visto il termine formalmente prima, ma dalla descrizione del brevetto, posso fare un'ipotesi plausibile.

Una lista concatenata è quella in cui ciascun nodo ha un collegamento al successivo ...

a -->-- b -->-- c -->-- d -->-- null 

Una lista doppia significa che ogni nodo contiene un collegamento al suo predecessore pure.

--<-- --<-- --<-- 
|  |  |  | 
a -->-- b -->-- c -->-- d -->-- null 

Assumiamo l'elenco è ordinato. Se voglio eseguire la ricerca binaria, normalmente andrò a metà dell'elenco per trovare il nodo centrale, quindi andare nell'intervallo appropriato e ripetere. Tuttavia, l'attraversamento dell'elenco collegato è sempre O (n) - Devo seguire tutti i collegamenti. Dalla descrizione, penso che stiano semplicemente aggiungendo collegamenti aggiuntivi da un nodo per "saltare" un numero fisso di nodi più avanti nell'elenco. Qualcosa di simile ...

--<-- --<-- --<-- 
|  |  |  | 
a -->-- b -->-- c -->-- d -->-- null 
|      | 
|----------->-----------| 
-----------<----------- 

ora posso attraversare l'elenco più rapidamente, soprattutto se ho scelto le destinazioni del collegamento più attentamente (cioè garantire che sempre vanno avanti/indietro la metà dello spostamento dell'elemento da cui puntano in la lunghezza della lista). Quindi trovo l'intervallo approssimativo che desidero con questi collegamenti e uso i collegamenti normali per trovare l'oggetto.

Questo è un buon esempio del perché odio i brevetti software. È roba eminentemente ovvia, avvolta in una prosa florida per confondere le persone.

Answer 2

Non posso esserne sicuro, ma suona un po 'come un skip list.

Anche se non è quello che è, è possibile trovare gli skip list a portata di mano. (Per quanto ne so io sono unidirezionale, comunque.)

Answer 3

La descrizione non è particolarmente buona, ma come meglio posso raccogliere, sembra meno efficiente skip list.

Answer 4

Non so se questo è esattamente una "lista quad-linked", ma suona come qualcosa di simile:

struct Person { 
    // Normal doubly-linked list. 
    Customer *nextCustomer; 
    Customer *prevCustomer; 

    std::string firstName; 

    Customer *nextByFirstName; 
    Customer *prevByFirstName; 

    std::string lastName; 

    Customer *nextByLastName; 
    Customer *prevByLastName; 
}; 

Cioè: si mantiene diversi ordinamenti attraverso la vostra collezione. Puoi navigare facilmente nell'ordine firstName o nell'ultimo nome. È costoso mantenere aggiornati i collegamenti, ma rende la navigazione abbastanza veloce.

Naturalmente, questo potrebbe essere qualcosa di completamente diverso.

Answer 5

La mia lettura di esso è che un quad collegata lista è quella che può essere attraversato (avanti o indietro) a O (n) in due modi diversi, cioè ordinata secondo FieldX o Fieldy:

(a) generare un primo e secondo gruppo di puntatori di collegamento, in cui il primo set di collegamento puntatori punti di elementi successivi di set di record correlati quando i record sono ordinato rispetto ID fissa campo, e il secondo set di collegamento punto indica i predecessori elementi del set di record correlati quando i record sono ordinati con rispetto al campo ID fisso;

(b) generare terzo e quarto set di puntatori di collegamento, in cui la terza set di collegamento puntatori punti di elementi successivi di set di record correlati quando i record sono ordinato rispetto alla variabile Campo ID e il quarto set di punti di collegamento del predecessore elementi del set di record correlati quando i record sono ordinati con rispetto al campo ID variabile;

Quindi, se si dispone di un elenco di dipendenti collegati in quad, è possibile archiviarli ordinati per nome E ordinati per età ed enumerarli in O (n).

Answer 6

Una fonte del brevetto è this.Ci sono, sembra, due rivendicazioni, la seconda delle quali è quasi più rilevanti:

Procedimento implementato calcolatore per organizzazione e ricerca una serie di record correlati, in cui ciascun record include:

i) campo ID fisso; e

ii) un campo ID variabile; il metodo comprendente le fasi di:

(a) generare un primo e un secondo gruppo di puntatori di collegamento, in cui la prima serie di puntatori di link punta agli elementi successivi dell'insieme dei record correlati quando i record sono ordinati rispetto al fisso Campo ID e la seconda serie di puntatori di link punta agli elementi predecessori dell'insieme di record correlati quando i record sono ordinati rispetto al campo ID fisso;

(b) generazione di terze e quarte serie di puntatori di collegamento, in cui la terza serie di puntatori di collegamento punta agli elementi successivi del set di record correlati quando i record sono ordinati rispetto al campo ID variabile e il quarto set dei puntatori di link punta agli elementi predecessori dell'insieme di record correlati quando i record sono ordinati rispetto al campo ID variabile;

(c) generare un primo e secondo gruppo di puntatori di campo, in cui il primo set di puntatori di campo comprende un insieme ordinato di puntatori che puntano a ogni campo ID fisso Nth quando i record sono ordinate rispetto al campo ID fissa, e il secondo set di puntatori include un insieme ordinato di puntatori che puntano a ogni campo dell'ID n variabile quando i record sono ordinati rispetto al campo ID variabile;

(d) durante la ricerca di un particolare record facendo riferimento al suo campo ID fisso, effettuando una ricerca binaria del primo insieme di puntatori di campo per determinare un puntatore iniziale e un puntatore finale che definiscono un intervallo all'interno del quale il particolare record è si trova;

(e) esaminando mediante scarch lineare, i campi ID fissi all'interno dell'intervallo determinato nel passaggio (d) per individuare il particolare record;

(f) durante la ricerca di un particolare record facendo riferimento al suo campo ID variabile, effettuando una ricerca binaria del secondo insieme di puntatori di campo per determinare un puntatore iniziale e un puntatore finale che definiscono un intervallo all'interno del quale il particolare record è si trova;

(g) esaminare, mediante ricerca lineare, i campi ID variabili all'interno dell'intervallo determinato nel passaggio (f) per individuare il particolare record.

Quando si lavora con il gobbledegook brevetto Credo significa approssimativamente uguale avente due saltare elenchi (uno per la ricerca in avanti, uno per all'indietro ricerca) su ciascuno dei due tasti (quindi 4 elenca in totale, e il nome "quad-list"). Non penso che sia un brevetto molto buono - sembra essere un'ovvia applicazione di skip list a un set di dati in cui si hanno due chiavi da cercare.