data structures - ¿Hay alguna estructura de datos probabilísticos que proporcione falsos negativos pero no falsos positivos?

data-structures hash

Question

Necesito una estructura de datos probabilísticos eficiente en el espacio para almacenar valores que ya he calculado. Para mí, el cálculo es barato, pero el espacio no lo es, así que si esta estructura de datos arroja un falso negativo, estoy de acuerdo con rehacer algún trabajo de vez en cuando, pero los falsos positivos son inaceptables. Entonces, lo que estoy buscando es una especie de opuesto a un filtro Bloom .

Answer 1

Para los negativos falsos, puede usar la tabla hash con pérdidas o un LRUCache. Es una estructura de datos con búsqueda rápida O (1) que solo arrojará falsos negativos. si pregunta si "He realizado la prueba X", le dirá "Sí, definitivamente tiene" o "No puedo recordar".

Pseudocódigo:

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.

Del mismo modo Bloom filtro para falso positivo