Противоположность фильтра Цветка?

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

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

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

How about an LRUCache?

I'm sorry I'm not much help - I don't think its possible. If test execution can't be ordered maybe use a packed format (8 tests per byte!) or a good sparse array library for storing the outcomes in memory.

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

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

В статье Википедии Фильтры Блума дается большой анализ и интересный обзор математики.

Да, хэш-таблица с потерями или 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.