Struttura dati: ordina e ricerca in modo efficace

1. Se aggiungi e rimuovi raramente dati

Che ne pensi di utilizzare la stessa tecnica utilizzata in RDBMS con gli indici?

In altre parole, avrai il set non ordinato contenente i dati e quattro set ordinati contenenti le chiavi e i puntatori agli elementi nel set di dati.

Naturalmente, questo potrebbe causare problemi di prestazioni se devi aggiungere e rimuovere frequentemente molti dati.

2. Se i dati vengono aggiunti o rimossi di frequente

È possibile modificare leggermente l'algoritmo per ridurre l'impatto sulle prestazioni dell'ordinamento dei quattro set di indici ogni volta che si aggiunge o si rimuove un elemento. Ad esempio, puoi avere quattro set di indici non ordinati, creare da essi i set ordinati quando necessario e invalidare quei set ordinati quando un elemento viene aggiunto o rimosso.

3. Profilo

Si noti che la profilazione è importante, dal momento che non è possibile indovinare dove sarà il collo di bottiglia. Ricorda di:

• Quando rimuovi un elemento dal set di dati, la rimozione di quattro chiavi da quattro set di indici è rapida, poiché questi set sono già ordinati;

• Quando aggiungi un elemento, l'aggiunta di quattro chiavi ai set di indici non è estremamente lenta: devi solo passare attraverso i set e inserire i tasti nella posizione appropriata:

  Let the list be:

   3, 7, 8, 12, 16, 22, 23, 24, 27
  

  If you need to add the value 25, position yourself at the middle of the list:

   3, 7, 8, 12, 16, 22, 23, 24, 27
                ↑
  

  Since 25 is greater then 16, go to the right:

   -, -, -, --, --, 22, 23, 24, 27
                           ↑
  

  And again to the right:

   -, -, -, --, --, --, --, 24, 27
                               ↑
  

  Found the position.

Mantenere quattro chiavi ordinate non è molto diverso dal mantenere un tasto ordinato.

Dal momento che dici che il tempo di ordinamento dovrebbe essere molto piccolo, sei praticamente limitato a usare una sorta di struttura ad albero (albero, skip-list, trie, ecc.). Quale è il migliore per la tua applicazione dipende dalla natura delle chiavi; se puoi usare un trie bit a bit, è molto probabile che sia il migliore. Altrimenti, è possibile selezionare tra le numerose varianti di albero a seconda di come si desidera scambiare tempo di inserimento e tempo di ricerca / utilizzo della memoria. Ad esempio, gli alberi AVL sono più densi degli alberi rosso-neri, il che significa che l'inserimento / eliminazione negli alberi AVL è più lento (più lavoro per mantenere la struttura densa), ma la ricerca è più veloce e l'utilizzo della memoria è inferiore. Se tendi ad accedere ripetutamente agli stessi pochi elementi, è preferibile uno splay tree.

Una volta che hai selezionato una struttura dati appropriata per una singola chiave, la duplica tutte le volte che vuoi per tutte le chiavi che vuoi ordinare. Se ogni elemento deve essere in grado, ad esempio, di sapere come arrivare a "next" e "previous", puoi avere ogni elemento memorizzare un singolo puntatore a una struttura contenente tutti i tuoi alberi.

Mantieni i tuoi dati in una tabella hash codificata da un UUID. Quindi mantieni quattro indici, ognuno con due campi: la chiave di ricerca e l'UUID dei dati. Cerchi gli indici per trovare la chiave, quindi usa la chiave per ottenere i dati dalla tabella hash. Il recupero dei dati dalla tabella hash è O (1), la ricerca dell'indice dipende dall'implementazione (O (log N) per un albero rosso-nero, O (M) per un trie, O (1) per una tabella hash) .