Ulteriori ipotesi
Questa risposta è basata sulle seguenti ipotesi aggiuntive:
- puoi facilmente determinare il timestamp per l'inizio del log e
- è possibile memorizzare le posizioni del singhiozzo (opzionale)
Algoritmo di ricerca
La ricerca è suddivisa in due diversi algoritmi. Se cerchi un log con un timestamp che è dopo l'inizio del log, sai che non sarà trovato nel singhiozzo e userà ricerca non hiccup sotto. Se cerchi un timestamp prima dell'inizio del log, usi invece hiccup search . Se non esegui una ricerca in base al timestamp, ma alcuni altri criteri, per prima cosa prova la ricerca non hiccup a causa della copertura del 95% e poi prova la ricerca hiccup se non è riuscito a trovare nulla.
Facoltativamente, puoi accelerare la ricerca di non-hiccup con un passaggio di pre-elaborazione.
Pre-elaborazione (facoltativo)
Se possibile, pre-analizzare i dati con una ricerca lineare per scoprire le posizioni dei dati di singhiozzo. Ciò dipende interamente dalla fattibilità di poter archiviare questi intervalli, il che potrebbe essere possibile dato che ammontano solo al 5% dei log (oppure potrebbe non esserlo, nel qual caso la performance degrada).
Si noti che la datastruttura corrispondente deve essere aggiornata ogni volta che si scrivono nuovi log, o almeno dovrebbe essere in grado di indicare fino a che punto dei log è stata eseguita la pre-elaborazione.
Ricerca non hiccup
La ricerca dei dati non-hiccup è possibile tramite una combinazione di ricerca binaria e lineare. Esegui una normale ricerca binaria, tuttavia, quando il tuo elemento pivot viene timestampato prima dell'inizio del log, ovvero l'elemento pivot è un blocco, devi determinare la prima voce del registro prima dell'elemento pivot e usarlo come elemento di pivot reale della tua ricerca binaria.
Questa prima voce di log con una timestamp dopo l'inizio del log si trova tramite una ricerca lineare a partire dall'elemento hiccup pivot. Se si conoscono gli aggiornamenti preelaborati o incrementali del singhiozzo memorizzato nella cache in cui è posizionato l'elemento di pivot pertinente, è possibile saltare lì in un tempo costante. Se dovessi eseguire la ricerca lineare completa, aggiorni una infrastruttura dati per memorizzare che queste posizioni sono coperte da dati di intoppo, in modo che la prossima volta sia possibile determinare rapidamente l'elemento di pivot giusto.
Hiccup-ricerca
Questo dipende dal fatto che sia stato effettuato il pre-processo. In caso contrario, si tratta di una ricerca lineare di tutti i dati (e al momento è possibile eseguire anche le parti di preelaborazione). Altrimenti, la tua infrastruttura preelaborata è in grado di dirti le posizioni dei dati di intasamento e puoi cercare direttamente attraverso questi, cioè eseguire una ricerca lineare solo attraverso il 5% dei dati di singhiozzo.
Prestazioni
Per la ricerca non hiccup con dati completamente preelaborati è possibile ottenere quasi le prestazioni di una ricerca binaria predefinita. Invece di un semplice confronto in ogni fase, è necessario un confronto aggiuntivo per determinare se si colpisce un elemento di intoppo e in tal caso è necessario un accesso alla struttura dei dati per trovare l'elemento di pivot reale. Questo lavoro aggiuntivo, tuttavia, è leggermente alleviato dal fatto che non si esclude solo metà del set di dati, ma si esclude anche la parte dei dati di intoppo.
Ovviamente, se devi ricorrere alla ricerca lineare, questo si degrada di conseguenza.
La ricerca di intoppi è un caso negativo se non si dispone di informazioni sui problemi esistenti esistenti e occorre effettuare una ricerca lineare attraverso tutti i dati.
Infine, se non si cerca un timestamp, ma alcuni altri criteri e nessuna voce del registro esiste, questo è il tuo caso peggiore. Infatti, se non si dispone di una struttura dati per il singhiozzo, finisce per essere più lento della ricerca lineare, poiché entrambe le esecuzioni di ricerca possono eseguire linearmente la scansione delle stesse posizioni di singhiozzo (sebbene sia ancora O (n)).
Se si dispone della struttura di dati disponibile e completamente preelaborata, il runtime del caso peggiore si riduce a O (max (log (M) * log (N), M)) dove M è la quantità di dati hiccup, che è cercato linearmente, e assumendo che si possa cercare la fine dei dati di hiccup dati qualsiasi posizione di hiccup dal tuo datastructure in O (log (M)).