我需要一个节省空间的概率数据结构来存储我已经计算的值。对我来说，计算很便宜，但空间却不是——所以如果这个数据结构返回误报，我可以每隔一段时间重做一些工作，但误报是不可接受的。所以我正在寻找的是相反的布隆过滤器.
对于漏报，您可以使用有损哈希表或 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.
类似地，用于误报的布隆过滤器
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
