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

Question

Я пытаюсь оптимизировать часть программного обеспечения, которая в основном выполняет миллионы тестов. Эти тесты генерируются таким образом, что могут быть некоторые повторения. Конечно, я не хочу тратить время на тесты, которые я уже выполнил, если я могу эффективно их избежать.

Итак, я думаю об использовании фильтра Блума для хранения уже выполненных тестов. Тем не менее, фильтр Блума делает ошибку на небезопасной для меня стороне. Это дает ложные срабатывания. То есть он может сообщить, что я провел тест, которого у меня нет. Хотя это может быть приемлемым в сценарии, над которым я работаю, мне было интересно, есть ли эквивалент фильтра Блума, но с ошибкой на противоположной стороне, то есть только с ложными отрицаниями.

Я пролистал литературу без удачи.

Answer 1

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

Как насчет LRUCache?

Answer 9

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

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