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

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

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

Я просмотрел литературу без везения.

Ответ 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.

Ответ 2

Точная структура данных, которая выполняет эту задачу, представляет собой Direct-mapped cache и обычно используется в ЦП.

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

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

Ответ 3

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

Ответ 4

Как насчет LRUCache?

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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

Ответ 9

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

EDIT Это утверждение верно только в том случае, если вы ищете эффективную структуру данных с памятью. Если память не ограничена, вы всегда можете получить структуру данных, чтобы получить 100% точные результаты, сохраняя каждый элемент элемента.