Attraversamento efficiente di un elenco di modifiche

Question

Ho un elenco di modifiche a un elenco: aggiunge ed elimina. L'elenco potrebbe essere enorme - diciamo 10'000 articoli.

Voglio conoscere lo stato dell'elenco dopo la modifica 9'000.

Potrei percorrere l'elenco dall'inizio fino a cambiare 9'000. Mi sembra un po 'prolisso.

Potrei tenere un elenco di elementi e registrare quando vengono aggiunti e quando vengono eliminati, quindi scorrere questo elenco per vedere cosa c'è nell'elenco in una particolare modifica. Se le aggiunte e le eliminazioni fossero ugualmente probabili, dimezzerei il numero di elementi dell'elenco che dovrei esaminare ...

Ma la notazione Big O afferma che dimezzare le dimensioni del problema non rende le cose più efficienti (se l'ho capito correttamente).

Potrei memorizzare nella cache lo stato dell'elenco ad ogni 100 o 1000 modifica ... ma ancora una volta, la grande O dice che dividere il numero di elementi per 'n' non rende le cose più efficienti.

Allora, qual è il modo efficace per farlo? Esiste un modo efficace per farlo?

Ulteriori dettagli: In particolare, sto monitorando allocazioni / deallocazioni di memoria in un allocatore personalizzato. Ogni allocazione / deallocazione è un evento nell'elenco. Ogni allocazione ha un ID univoco. Mi piacerebbe sapere cosa è attualmente assegnato dopo (ad esempio) 9'000 eventi.

La mia prima idea è stata quella di memorizzare, per ogni ID, l'evento che è stato allocato e l'evento che è stato deallocato. Quindi per portare questo elenco fino alla prima allocazione il cui evento alloc è maggiore di 9000. Ma come ho detto, questo dimezzerebbe solo il numero di elementi che dovrei percorrere.

Mi piace il punto sollevato da Mike F: camminare dal 100esimo oggetto più vicino è tempo costante ...

Answer 1

Se si memorizza nella cache lo stato dell'elenco ogni X modifica, quindi è possibile eseguire un taglio binario per scendere a due stati memorizzati nella cache limitando la modifica che si sta cercando, quindi si cammina verso la maggior parte degli elementi X per arrivare all'elemento si. Quello è O (log N), più o meno.

Ma più in generale, ridurre la grande complessità O è il mezzo, non il fine. Se il tuo elenco è generalmente di 10.000 articoli, dovresti preoccuparti di renderlo veloce per N = 10.000, sia riducendo la complessità, sia semplicemente rendendolo più veloce.

Modifica: Oops, ho appena letto più attentamente la tua domanda. Se si memorizza nella cache lo stato ogni (ad es.) 100 elementi, non si esegue la ricerca, quindi non è nemmeno necessario eseguire un taglio binario: si passa direttamente allo stato memorizzato nella cache più vicino e si camminano al massimo 100 elementi per raggiungere l'elemento si. Quindi questo è un algoritmo a tempo costante no?

Answer 2

Con che tipo di struttura stai lavorando? Non esiste un modo efficiente per utilizzare una struttura di dati generica, ma esistono migliaia di metodi di ottimizzazione e metodi efficienti per strutture specifiche.

E sì, se hai un algoritmo che è O (n) complessità temporale, dimezzare il numero di elementi non lo cambierà da O (n) complessità ... ma significherà che ogni nuovo oggetto ha solo la metà l'effetto che aveva originariamente. La notazione O grande è un buon modo di classificare gli algoritmi, ma in realtà non si mette in efficienza a parte i numeri enormi (un buon esempio è l'ordinamento. Quicksort è una complessità peggiore di Fusione nel peggiore dei casi ... ma è possibile implementare QuickSort in modo più efficiente di mergesort per quasi tutte le applicazioni diverse da quelle che si occupano dell'ordinamento di milioni di articoli)

Answer 3

'Timestamp' o segna ogni inserimento ed eliminazione, quindi ci vorrebbe un semplice attraversamento per trovare le modifiche (O (n)).