Ho letto su strutture di dati come filtri di fioritura e elenchi di salti.Quali sono le strutture dati probabilistiche?
Quali sono le caratteristiche comuni delle strutture di dati probabilistiche e per cosa sono utilizzate?
Probabilmente ci sono molte (e buone) risposte diverse, ma a mio modesto parere, le caratteristiche comuni delle strutture dati probabilistiche sono che forniscono una risposta approssimativa, non precisa.
Quanti oggetti ci sono qui? Circa 1.523.425 con probabilità del 99%
Aggiornamento: rapida ricerca prodotto link all'articolo decente sul tema:
https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/
strutture di dati probabilistici non si può dare una risposta definitiva, invece Forniscono con una ragionevole approssimazione della risposta e un modo per approssimare questa stima. Sono estremamente utili per i big data e le applicazioni di streaming perché consentono di ridurre drasticamente la quantità di memoria necessaria (rispetto alle strutture di dati che forniscono risposte esatte).
Nella maggior parte dei casi queste strutture dati utilizzano le funzioni hash per randomizzare gli elementi. Perché ignorano le collisioni mantengono le dimensioni costanti, ma questo è anche un motivo per cui non possono darti valori esatti. I vantaggi portano:
utilizzati frequentemente strutture di dati probabilistici sono:
C'è una lista di strutture di dati probabilistici in Wikipedia per il vostro riferimento: https://en.wikipedia.org/wiki/Category:Probabilistic_data_structures
Ci sono definizioni diverse su ciò che "struttura dati probabilistica" è. IMHO, la struttura dei dati probabilistica significa che la struttura dei dati utilizza un algoritmo randomizzato o sfrutta internamente alcune caratteristiche probabilistiche, ma non devono comportarsi in modo probabilistico o non deterministico dal punto di vista dell'utente della struttura dei dati.
ci sono molti "strutture di dati probabilistici" con probabilisticamente comportamento come il bloom filter e HyperLogLog menzionato dalle altre risposte.
Allo stesso tempo, ci sono altre "strutture dati probabilistiche" con comportamento determinato (dal punto di vista dell'utente) come skip list.Per l'elenco dei salti, gli utenti possono usarlo allo stesso modo di un albero di ricerca binario bilanciato, ma è implementato internamente con alcune idee legate alla probabilità. E secondo per saltare di lista autore William Pugh:
Skip liste sono una struttura di dati probabilistica che sembrano propensi a soppiantare alberi bilanciati come il metodo di attuazione di scelta per molte applicazioni. Gli algoritmi Skip list hanno lo stesso limite di tempo previsto asintotico come alberi bilanciati e sono più semplici, veloci e utilizzano spazio in meno.
non è una tabella hash senza LinkedList in ogni slot (memorizzazione quindi solo un "sì oggetto esiste" o "nessuna voce non esistono" in ogni slot) anche una struttura dati probabilistica? – Pacerier
@Pacerier, quello che stai dicendo è in realtà un filtro di fioritura con k = 1 funzione di hash. Ma come può certamente dire che se un oggetto è "non esiste", non può certamente dire che se l'oggetto "esiste". Ecco perché, sì, sarà una struttura dati probabilistica. –