Напротив фильтра Блума?

Да, хеш-таблица с потерями или LRUCache - это структура данных с быстрым поиском O (1), которая даст только ложноотрицательные результаты - если вы спросите, выполнял ли я тест X, он ответит вам либо «Да, вы определенно есть »или« Я не могу вспомнить ».

Простите за крайне грубый псевдокод:

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.

Точная структура данных, которая выполняет эту задачу, представляет собой кеш с прямым отображением и является обычно используется в процессорах.

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

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

Можно ли сохранить тесты, которые вы не запускали? Это должно изменить поведение фильтра.

1. Используйте набор бит, как указано выше. Если вы знаете, что нет. тестов, которые вы собираетесь запустить заранее, вы всегда получите правильные результаты (присутствующие, отсутствующие) из структуры данных.
2. Вы знаете, какие ключи вы будете хешировать? Если это так, вам следует провести эксперимент, чтобы увидеть распределение ключей в BloomFilter, чтобы вы могли точно настроить его для воспроизведения ложных срабатываний или чего-то еще.
3. Вы также можете проверить HyperLogLog.

Нет, и если подумать, это было бы не очень полезно. В вашем случае вы не могли быть уверены, что ваш тестовый прогон когда-либо остановится, потому что, если всегда есть «ложноотрицательные», всегда будут тесты, которые нужно запустить ...

Я бы сказал, вам просто нужно использовать хеш.

Как насчет LRUCache?

Извините, я не очень помог - я не думаю, что это возможно. Если выполнение теста не может быть заказано, возможно, используйте упакованный формат (8 тестов на байт!) Или хорошую библиотеку разреженных массивов для хранения результатов в памяти.

Я думаю, вы упускаете часть решения; чтобы полностью избежать ложных срабатываний, вам все равно придется отслеживать, какие из них были выполнены, и, по сути, использовать фильтр цветения в качестве ярлыка для определения того, что тест определенно не запускался.

Тем не менее, поскольку вы заранее знаете количество тестов, вы можете настроить фильтр таким образом, чтобы обеспечить приемлемую частоту ошибок с использованием некоторых хорошо известных формул; для 1% вероятности возврата ложного срабатывания вам потребуется ~ 9,5 бит на запись, поэтому для одного миллиона записей достаточно 1,2 мегабайта. Если вы уменьшите допустимую частоту ошибок до 0,1%, она увеличится только до 1,8 МБ.

Статья в Википедии Bloom Filters дает отличный анализ и интересный обзор задействованной математики.

Ожидаемая структура данных не существует. Потому что такая структура данных должна быть отображением "многие-к-одному" или, скажем, ограниченным набором состояний. Должно быть как минимум два разных входа, отображаемых в одно и то же внутреннее состояние. Таким образом, вы не можете сказать, есть ли оба (или более) из них в наборе, только зная, что существует хотя бы один из таких входных данных.

РЕДАКТИРОВАТЬ Это утверждение верно только тогда, когда вы ищете структуру данных с эффективным использованием памяти. Если память не ограничена, вы всегда можете получить структуру данных, которая дает 100% точные результаты, сохраняя каждый элемент элемента.