主要是测试了改进后的Bloomfilter的性能
1.改进前,采用的是BitSet
测试结果: 测试总量:10,000,000 HASH函数个数:8个 冲突数:4
内存占用:450,000,000 花费时间:51,294
2.改进后,采用数组方式 均采用2个hash函数
测试结果:
测试总量:10,000,000 浮动大小:0.85 冲突数:0
内存占用:47,058,824 花费时间:8,563 统计数:10,000,000
测试总量:10,000,000 浮动大小:0.75 冲突数:0
内存占用:53,333,332 花费时间:8,019 统计数:10,000,000
测试总量:10,000,000 浮动大小:0.85 冲突数:0
内存占用:47,058,824 花费时间:8,003 统计数:10,000,000
测试总量:10,000,000 浮动大小:0.95 冲突数:0
内存占用:42,105,264 花费时间:8,253 统计数:10,000,000
测试总量:20,000,000 浮动大小:0.85 冲突数:0
内存占用:94,117,648 花费时间:13,331 统计数:20,000,000
测试总量:20,000,000 浮动大小:0.75 冲突数:0
内存占用:106,666,664 花费时间:14,097 统计数:20,000,000
测试总量:20,000,000 浮动大小:0.95 冲突数:0
内存占用:84,210,528 花费时间:14,132 统计数:20,000,000
测试总量:100,000,000 浮动大小:0.95 冲突数:1
内存占用:421,052,640 花费时间:79,357 统计数:99,999,999
测试总量:100,000,000 浮动大小:0.85 冲突数:0
内存占用:470,588,224 花费时间:72,870 统计数:100,000,000
测试总量:200,000,000 浮动大小:0.85 冲突数:0
内存占用:941,176,448 花费时间:153,760 统计数:200,000,000
可见,采用ARRAY改进后的BloomFilter性能大大提升,并且支持删除操作,即能替代CBF的功能
由结果比较可知,当浮点因子为0.85时耗时最低,冲突率大大降低
分享到:
相关推荐
布隆过滤器的性能概述 :定义布隆过滤器参数... [0s 3.81267ms] :索引文件 dewiki-20140114-article-categories.ttl.ntriples...[3s 88.882374ms] :Lookup...数组的总大小为 575 [0s 27.010578ms] 下一步/测试 a)...
布隆过滤器对于插入和查找具有恒定的时间O(1)性能(其中K为常数)。 K是密码散列的次数。 Bloom筛选器可以使用非常有限的资源轻松处理数十亿个禁用的密码哈希。 当成员资格测试返回404(未找到)时,可以安全地...
Bloomfilters是概率数据结构,支持基本对象成员资格测试。 使用add方法add对象添加到Bloomfilters中,并使用in运算符测试对象的成员资格。 向in查询查询报告False的Bloomfilter保证没有对象。 bloomfilter报告为True...
(实践三)MapReduce 布隆过滤器 过滤器训练、过滤器应用、结果验证及分析 (实践四)MapReduce Top 10模式示例 在ctrip数据集上进行Top 10排序。 (实践五)去重的用户—针对ctrip数据集去重 对ctrip数据集中的...
布谷鸟过滤器被认为是布隆过滤器的更好替代方案,具有较低的空间开销并支持删除插入的元素。 当负载系数高时,将元素插入布谷鸟过滤器会变慢,并且当容量接近满时可能会失败。执行在此实现中,过滤器数据存储在...
这是一个简单的测试项目,比较了在 JavaScript 中完全搜索数据的三种通用方法的性能: 通用的基于 Angular 的搜索过滤器 通过模糊搜索 布隆过滤器搜索 这三种方法中的每一种都适用于不同的场景: Angular 过滤器:...
布隆过滤器是一种概率数据结构,用于在恒定时间内搜索大量元素中的一个元素,即O(K),其中K是布隆过滤器中使用的哈希函数的数量。 在以下情况下很有用: 要搜索的数据很大 系统上可用的内存有限/不足 与具有...
Tree理论以及Merge-Dump存储引擎进行改进,并参考Google的单机持久化存储系统LevelDB,实现一个分布式的Key-Value持久化缓存系统SSDB,结合传统缓存系统的优点并利用一致性哈希、布隆过滤器等思想对SSDB进行一系列...
布卢姆该软件包实现了通用用法的布隆过滤器。 它使用FNV和一个简单的技巧来计算所需的k个散列。特征初始化Bloom Filter仅需要过滤器的大小和哈希函数的数量。 使用Uint8Array TypedArray来确保最小的内存占用。 使用...
13.3.2 布隆过滤器 224 13.4 Apache Cassandra 225 13.4.1 点对点模型 225 13.4.2 基于Gossip和Antientropy 225 13.4.3 快速写 226 13.4.4 提示移交 226 13.5 Berkeley DB 226 13.6 小结 228 第四部分 掌握...
为了很好地实现布隆过滤器,开发人员需要一种高性能的方式来操作大量布尔值,所以这个库是对这个要求的一个答案。 虽然它在这个功能上表现出色,但它适合作为一个布尔数组,其中 vanilla javascript 是所需的平台。...