Naprzeciwko filtra Blooma?

Question

Próbuję zoptymalizować oprogramowanie, które generuje miliony testów. Testy te są generowane w taki sposób, że mogą występować pewne powtórzenia. Oczywiście nie chcę tracić czasu na przeprowadzanie testów, które już uruchomiłem, jeśli mogę skutecznie tego uniknąć.

Zastanawiam się, czy użyć filtru Bloom do przechowywania testów, które już zostały uruchomione. Jednak filtr Bloom'a błądzi mnie po niebezpiecznej stronie. Daje fałszywe alarmy. Oznacza to, że może on zgłosić, że przeprowadziłem test, którego nie zrobiłem. Chociaż może to być dopuszczalne w scenariuszu, nad którym pracuję, zastanawiałem się, czy istnieje odpowiednik filtru Blooma, ale błądzę po przeciwnej stronie, to znaczy podaję tylko fałszywe negatywy.

Przeszukałem literaturę bez powodzenia.

Answer 1

Nie, a jeśli się nad tym zastanowić, nie byłoby to zbyt przydatne. W twoim przypadku nie możesz być pewien, że twój test kiedykolwiek się zatrzyma, ponieważ jeśli zawsze będą "fałszywe negatywy" zawsze będą testy, które trzeba uruchomić ...

Powiedziałbym, że musisz po prostu użyj skrótu.

Answer 2

Czy można przechować testy, które wykonałeś , a nie uruchomić? Powinno to odwrócić zachowanie filtra.

Answer 3

Co powiesz na LRUCache?

Answer 4

Przykro mi, nie jestem zbyt pomocny - nie sądzę, że to możliwe. Jeśli nie można zamówić wykonania testu, może użyć formatu spakowanego (8 testów na bajt!) Lub dobrej biblioteki z rzadką biblioteką do przechowywania wyników w pamięci.

Answer 5

Myślę, że pomijasz część rozwiązania; Aby całkowicie uniknąć fałszywych alarmów, nadal będziesz musiał śledzić, które zostały uruchomione, i zasadniczo używaj filtru Blooma jako skrótu, aby stwierdzić, że test nie został wykonany.

To powiedziawszy, ponieważ znasz liczbę testów z wyprzedzeniem, możesz ustawić filtr w taki sposób, aby zapewnić akceptowalny poziom błędu za pomocą dobrze znanych formuł; dla 1% prawdopodobieństwa zwrotu fałszywego wyniku pozytywnego potrzebujesz ~ 9,5 bitów/wpis, więc dla miliona pozycji wystarczające jest 1,2 megabajta. Jeśli zmniejszysz dopuszczalny poziom błędu do 0,1%, to tylko zwiększy się do 1,8 MB.

Artykuł Wikipedii Bloom Filters zawiera świetną analizę i interesujący przegląd matematyki.

Answer 6

Tak, stratna tablica skrótów lub LRUCache to struktura danych z szybkim wyszukiwaniem O (1), która daje tylko fałszywe negatywy - jeśli zapytasz "Czy uruchomiłem test X", powie Ci to albo " Tak, zdecydowanie masz "lub" Nie pamiętam ".

Wybacz bardzo surowy Pseudokod:

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

Dokładna struktura danych, który realizuje to zadanie jest Direct-mapped cache i jest powszechnie stosowane w procesorach.

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

Struktura danych, której oczekujesz, nie istnieje. Ponieważ taka struktura danych musi być mapowaniem wielu do jednego, lub, powiedzmy, zestawem stanów ograniczonych. Musi istnieć co najmniej dwa różne wejścia mapujące do tego samego stanu wewnętrznego. Nie można więc stwierdzić, czy oba (lub więcej) z nich są w zestawie, tylko wiedząc, że przynajmniej jedno z takich danych wejściowych istnieje.

EDYCJA To stwierdzenie jest prawdziwe tylko wtedy, gdy szukasz pamięci wydajnej struktury danych. Jeśli pamięć jest nieograniczona, zawsze możesz uzyskać strukturę danych, aby uzyskać 100% dokładne wyniki, przechowując każdy element członkowski.

Answer 9

1. Użyj zestawu bitów, jak wspomniano powyżej. Jeśli znasz nie. testów, które zamierzasz uruchomić wcześniej, zawsze uzyskasz poprawne wyniki (obecne, nieobecne) ze struktury danych.
2. Czy wiesz, jakie klucze będziesz mieszać? Jeśli tak, powinieneś uruchomić eksperyment, aby zobaczyć rozmieszczenie kluczy w BloomFilter, abyś mógł go dostroić, aby odtworzyć fałszywe alarmy lub co ty.
3. Możesz również chcieć sprawdzić HyperLogLog.