布卢姆filter的对面?

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

所以,我正在考虑使用Bloomfilter来存储已经运行的testing。 但是布卢姆filter对我来说是不安全的一方。 它给出了误报。 也就是说,它可能会报告我已经跑了一个我没有的testing。 虽然在我正在处理的情况下这可能是可以接受的,但是我想知道是否有相当于布卢姆filter,但却犯了相反的错误,也就是只给出了错误的否定。

我没有任何运气,通过文学浏览。

是的,有损散列表或LRUCache是​​一种快速O(1)查找的数据结构,只会给出错误的否定结果 – 如果您询问“是否运行testingX”,它会告诉您“是的,您肯定有“或”我不记得“。

原谅极其粗糙的伪代码:

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. 

完成此任务的确切数据结构是直接映射caching ,通常在CPU中使用。

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

是否有可能存储你没有运行的testing? 这应该反filter的行为。

LRUCache怎么样?

对不起,我没有太多的帮助 – 我不认为这是可能的。 如果testing执行不能sorting,可以使用打包的格式(每个字节8个testing!)或一个好的稀疏数组库来将结果存储在内存中。

我认为你会离开解决scheme的一部分。 为了避免误报,你仍然需要跟踪哪些已经运行,并基本上使用布隆filter作为确定一个testing肯定没有运行的捷径。

也就是说,由于您事先知道testing的次数,您可以使用一些众所周知的公式来确定filter的大小,以提供可接受的错误率; 对于1%的返回假阳性的可能性,您需要〜9.5位/条目,因此对于一百万条logging,1.2兆字节就足够了。 如果您将可接受的错误率降低到0.1%,则这只会增加到1.8 MB。

维基百科的文章布卢姆filter给出了一个很好的分析,并涉及math有趣的概述。

  1. 如上所述,使用一些设置。 如果你知道没有。 您将事先运行testing,您将始终从数据结构中获得正确的结果(呈现,不存在)。
  2. 你知道什么键你会哈希? 如果是这样,您应该运行一个实验来查看BloomFilter中密钥的分布情况,以便您可以对其进行微调以重现误报或您有什么。
  3. 您也可能想要检出HyperLogLog。

不,如果你仔细想想,那也不会很有用。 在你的情况下,你不能确定你的testing运行永远不会停止,因为如果总是有“假阴性”,总会有testing需要运行。

我会说你只需要使用散列。

您所期望的数据结构不存在。 因为这样的数据结构必须是多对一的映射,或者说是一个有限的状态集合。 必须有至less两个不同的input映射到相同的内部状态。 所以你不能分辨两个(或更多)是否在集合中,只知道至less有一个这样的input存在。

编辑只有当你正在寻找一个高效的内存数据结构时,这个语句才是真实的。 如果内存是无限的,您可以通过存储每个成员项目,始终获得一个数据结构,以提供100%准确的结果。