¿Frente al filtro Bloom?

Question

Estoy tratando de optimizar un software que básicamente ejecuta millones de pruebas. Estas pruebas se generan de tal manera que puede haber algunas repeticiones. Por supuesto, no quiero perder tiempo ejecutando pruebas que ya realicé si puedo evitarlo de manera eficiente.

Por lo tanto, estoy pensando en utilizar un filtro Bloom para almacenar las pruebas que ya se han ejecutado. Sin embargo, el filtro Bloom se equivoca en el lado inseguro para mí. Da falsos positivos. Es decir, puede informar que realicé una prueba que no hice. Aunque esto podría ser aceptable en el escenario en el que estoy trabajando, me preguntaba si existe un equivalente a un filtro Bloom, pero se equivoca en el lado opuesto, es decir, solo se dan falsos negativos.

He hojeado la literatura sin ningún tipo de suerte.

Answer 1

No, y si lo piensas bien, no sería muy útil. En su caso, no puede estar seguro de que su prueba se detenga alguna vez, porque si siempre hay "falsos negativos" siempre habrá pruebas que deben ejecutarse ...

Yo diría que solo tiene que usa un hash

Answer 2

¿Es posible almacenar las pruebas que hizo no ejecutar? Esto debería invertir el comportamiento del filtro.

Answer 3

¿Qué tal un LRUCache?

Answer 4

Lo siento, no soy de mucha ayuda, no creo que sea posible. Si no se puede ordenar la ejecución de la prueba, quizás use un formato empaquetado (¡8 pruebas por byte!) O una buena biblioteca de matriz dispersa para almacenar los resultados en la memoria.

Answer 5

Creo que está dejando de lado parte de la solución; para evitar falsos positivos por completo, aún tendrá que rastrear los que se han ejecutado, y esencialmente utilizar el filtro de floración como un atajo para determinar que la prueba definitivamente no se ha ejecutado.

Dicho esto, ya que conoce el número de pruebas por adelantado, puede ajustar el tamaño del filtro de forma que proporcione una tasa de error aceptable utilizando algunas fórmulas bien conocidas; para una probabilidad del 1% de devolver un falso positivo necesitas ~ 9.5 bits/entrada, por lo que para un millón de entradas son suficientes 1.2 megabytes. Si reduce la tasa de error aceptable al 0.1%, esto solo aumenta a 1.8 MB.

El artículo de Wikipedia Bloom Filters ofrece un excelente análisis y una visión general interesante de las matemáticas involucradas.

Answer 6

Sí, una tabla hash con pérdida o una LRUCache es una estructura de datos con una búsqueda O (1) rápida que solo arrojará resultados negativos falsos. Si pregunta "¿He ejecutado la prueba X?", Le dirá " Sí, definitivamente tienes ", o" No puedo recordar ".

perdonar al pseudocódigo muy crudo:

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

La estructura de datos exacta que lleva a cabo esta tarea es un Direct-mapped cache, y se utiliza comúnmente en las CPU.

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

La estructura de datos que espera no existe. Debido a que dicha estructura de datos debe ser un mapeo de varios a uno, o por ejemplo, un conjunto de estados limitados. Debe haber al menos dos entradas diferentes asignadas al mismo estado interno. Por lo tanto, no puede decir si ambos (o más) de ellos están en el conjunto, solo sabiendo que al menos uno de dichos datos existe.

EDITAR Esta afirmación es verdadera solo cuando se busca una estructura de datos con memoria eficiente. Si la memoria es ilimitada, siempre puede obtener una estructura de datos para obtener resultados 100% precisos, almacenando cada elemento miembro.

Answer 9

1. Utilice un conjunto de bits, como se mencionó anteriormente. Si sabes el no. de las pruebas que va a ejecutar de antemano, siempre obtendrá los resultados correctos (presente, no presente) de la estructura de datos.
2. ¿Sabes qué teclas vas a utilizar hashing? Si es así, debe ejecutar un experimento para ver la distribución de las claves en BloomFilter para que pueda ajustarlo y reproducir falsos positivos, o lo que sea.
3. Es posible que desee comprobar HyperLogLog también.