布隆过滤器对面？

Question

我正在尝试优化一个基本上运行数百万次测试的软件.这些测试的生成方式可能会有一些重复.当然,如果我能有效地避免它,我不想花时间运行我已经运行的测试.

所以,我正在考虑使用Bloom过滤器来存储已经运行的测试.但是,Bloom过滤器对我来说不安全.它给出了误报.也就是说,它可能会报告我已经进行了一项我没有进行的测试.虽然这在我正在研究的场景中是可以接受的,但我想知道是否有相当于Bloom过滤器,但在相反方面犯了错误,即只给出假阴性.

我没有运气就浏览了文献.

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

完成此任务的确切数据结构是直接映射缓存,通常用于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 3

是否可以存储您未运行的测试？这应该反转过滤器的行为.

Answer 4

不，如果你仔细想想，它不会很有用。在您的情况下，您无法确定您的测试运行是否会停止，因为如果总是存在“假阴性”，则总是需要运行测试......

我想说你只需要使用哈希。