È una buona idea usare i filtri bloom per questo scenario?

Question

È una buona idea usare i filtri bloom per questo scenario?

#1 da (2 voti)

1

Ho un social network teorico in cui due persone, A & C, può diventare amico se e solo se, hanno tra loro un amico comune B.

La soluzione più semplice è quella di scorrere le due liste e vedere se hanno amici in comune. La mia domanda è, posso usare invece i filtri di fioritura? Avrò un filtro di fioritura per ogni utente con la loro lista di amici aggiunta. Quando ho bisogno di verificare se esiste un amico comune, controllo prima la lista di amici con il filtro di fioritura di C e se ottengo un risultato positivo, eseguo effettivamente l'iterazione per confermare.

Dato che la dimensione media dell'elenco di amici se 100 amici, questa implementazione sarà migliore della semplice iterazione?

data-structures

posta Gaurav 04.11.2014 - 06:17

fonte

1 risposta

Leggi altre domande sui tag data-structures

salvataggio delle informazioni sulla connettività in una rete di nodi / spigoli Qual è un buon modo per spiegare che la configurazione del sistema in fase di esecuzione non dovrebbe essere modificata dal codice al momento della compilazione? [chiuso]

score 2 · Answer 1

No, i filtri di fioritura non sono adatti al tuo caso.

I filtri di utilizzo del caso di utilizzo sono i seguenti:

hai molto dataset di grandi dimensioni che in genere non si adattano alla memoria
si desidera verificare se contiene elementi forniti, essendo possibili falsi positivi

In altre parole, è un trucco per inserire qualcosa in memoria che è in realtà più grande, ma sul lato negativo accettiamo i falsi positivi. Questo è sia eccessivo che inadeguato per il tuo caso in cui si desidera confrontare due liste di amici.

Cosa dovresti fare:

Basta mettere una lista in un hash impostato per O (1) "contenere" operazioni, e iterare con l'altro elenco.

EDIT:

Un revisore ha cambiato questo aspetto con non contiene , questo non è né sbagliato né vero, è solo l'altra faccia della medaglia. Per renderlo più chiaro:

se il filtro di fioritura dà un colpo: l'elemento è probabilmente all'interno
se il filtro di fioritura dà un errore: l'elemento non è certamente all'interno

... in altre parole:

se un elemento è all'interno: ottieni sempre un successo
se un elemento non è all'interno: probabilmente ottieni un errore

... sì, questo è il problema delle strutture dati probabilistiche. Puoi anche vederlo in questo modo: ci sono più chiavi che colpiscono di oggetti all'interno.