Gegenteil von Bloom filter?

Question

Ich versuche, eine Software zu optimieren, die im Grunde genommen Millionen von Tests ausführt. Diese Tests werden so generiert, dass es einige Wiederholungen geben kann. Natürlich möchte ich keine Zeit damit verbringen Tests zu machen, die ich bereits ausgeführt habe, wenn ich es effizient vermeiden kann.

Also, ich denke über die Verwendung eines Bloom-Filters, um die Tests zu speichern, die bereits ausgeführt wurden. Allerdings irrt der Bloom-Filter auf der unsicheren Seite für mich. Es gibt falsche Positive. Das heißt, es kann berichten, dass ich einen Test durchgeführt habe, den ich nicht gemacht habe. Obwohl dies in dem Szenario, an dem ich gerade arbeite, akzeptabel sein könnte, habe ich mich gefragt, ob es einen äquivalenten Bloom-Filter gibt, aber auf der anderen Seite irrte, das heißt, nur falsche Negative zu geben.

Ich habe die Literatur ohne Glück überflogen.

Answer 1

Nein und wenn Sie darüber nachdenken, wäre es nicht sehr nützlich. In Ihrem Fall konnten Sie nicht sicher sein, dass Ihr Testlauf jemals aufhören würde, denn wenn es immer "falsche Negative" gibt, wird es immer Tests geben, die ausgeführt werden müssen ...

Ich würde sagen, Sie müssen nur Verwende einen Hash.

Answer 2

Ist es möglich, die Tests zu speichern, die Sie nicht ausgeführt haben? Dies sollte das Verhalten des Filters umkehren.

Answer 3

Wie wäre es mit einem LRUCache?

Answer 4

Es tut mir leid, ich bin nicht viel Hilfe - ich glaube nicht, dass es möglich ist. Wenn die Testausführung nicht bestellt werden kann, verwenden Sie möglicherweise ein gepacktes Format (8 Tests pro Byte!) Oder eine gute Sparse-Array-Bibliothek zum Speichern der Ergebnisse im Speicher.

Answer 5

Ich denke, Sie lassen einen Teil der Lösung aus; Um Fehlalarme vollständig zu vermeiden, müssen Sie immer noch nachverfolgen, welche Prozesse ausgeführt wurden, und im Wesentlichen den Bloom-Filter als Abkürzung verwenden, um zu bestimmen, ob ein Test definitiv ausgeführt wurde.

Da Sie die Anzahl der Tests im Voraus kennen, können Sie den Filter so dimensionieren, dass er eine akzeptable Fehlerrate mit einigen bekannten Formeln liefert; bei einer Wahrscheinlichkeit von 1%, dass ein falsches positives Ergebnis zurückgegeben wird, benötigen Sie ~ 9,5 Bit/Eintrag, so dass für eine Million Einträge 1,2 Megabyte ausreichen. Wenn Sie die akzeptable Fehlerrate auf 0,1% reduzieren, erhöht sich diese nur auf 1,8 MB.

Der Wikipedia-Artikel Bloom Filters gibt eine gute Analyse und einen interessanten Überblick über die beteiligten Mathe.

Answer 6

Ja, eine verlustbehaftete Hash-Tabelle oder ein LRUCache ist eine Datenstruktur mit schneller O (1) -Lookup, die nur falsche Negative geben wird - wenn Sie fragen, ob ich Test X ausgeführt habe, wird es Ihnen entweder sagen Ja, du hast definitiv ", oder" ich kann mich nicht erinnern ".

Vergib den extrem groben Pseudo-Code:

setup_test_table(): 
    create test_table(some large number of entries) 
    clear each entry(test_table, NEVER) 
    return test_table 

has_test_been_run_before(new_test_details, test_table): 
    index = hash(test_details , test_table.length) 
    old_details = test_table[index].detail 
    // unconditionally overwrite old details with new details, LRU fashion. 
    // perhaps some other collision resolution technique might be better. 
    test_table[index].details = new_test_details 
    if (old_details === test_details) return YES 
    else if (old_details === NEVER) return NEVER 
    else return PERHAPS  

main() 
    test_table = setup_test_table(); 
    loop 
     test_details = generate_random_test() 
     status = has_test_been_run_before(test_details, test_table) 
     case status of 
      YES: do nothing; 
      NEVER: run test (test_details); 
      PERHAPS: if(rand()&1) run test (test_details); 
    next loop 
end. 

Answer 7

Die Struktur genaue Daten, die diese Aufgabe erfüllt ist ein Direct-mapped cache und in CPUs häufig verwendet wird.

function set_member(set, item) 
    set[hash(item) % set.length] = item 

function is_member(set, item) 
    return set[hash(item) % set.length] == item 

Answer 8

Die von Ihnen erwartete Datenstruktur existiert nicht. Weil eine solche Datenstruktur eine Viele-zu-Eins-Abbildung oder, sagen wir, eine begrenzte Zustandsmenge sein muss. Es müssen mindestens zwei verschiedene Eingänge vorhanden sein, die auf denselben internen Zustand abgebildet werden. Sie können also nicht sagen, ob beide (oder mehr) von ihnen in der Menge sind, nur dass mindestens eine solche Eingabe existiert.

EDIT Diese Aussage trifft nur zu, wenn Sie nach einer speichereffizienten Datenstruktur suchen. Wenn der Speicher unbegrenzt ist, können Sie immer eine Datenstruktur erhalten, um 100% genaue Ergebnisse zu erhalten, indem Sie jedes Element speichern.

Answer 9

1. Verwenden Sie ein Bit, wie oben erwähnt. Wenn Sie die Nr. Kennen von Tests, die Sie im Voraus ausführen, erhalten Sie immer korrekte Ergebnisse (vorhanden, nicht vorhanden) aus der Datenstruktur.
2. Wissen Sie, welche Schlüssel Sie hashen werden? Wenn dies der Fall ist, sollten Sie ein Experiment durchführen, um die Verteilung der Schlüssel im BloomFilter zu sehen, damit Sie Feinabstimmung vornehmen können, um falsche Positive zu reproduzieren, oder was Sie haben.
3. Sie können auch HyperLogLog überprüfen.