在搜索的应用中, bitset 的应用相当广泛,而且是 java util 包下面标准的类,很多人也会首先使用,一般都用于记录对应的 document id 有没有选中,除了这一个解决方案,还有通过 new 数组[] 这样子的方式去记录,其实道理都大同小异,都是通过数组的下标确定对应的 document id 有没有选中。
BitSet性能其实不够好
功能差别上基本相似,但问题是性能方面如何?对于搜索应用,速度是搜索应用的生命,特别在大数据方面。我们不妨对此做一个测试,一个 bitset为1000W 的数组,遍历 10次
10次的总时间约 1.1秒,平均一次就是 0.11秒,这个速度能接受吗?显然不能接受,平均一个搜索应用也就 0.2 ~ 0.3 秒的时间,普通一个 bitset 就吃掉了 0.1 秒,这能接受吗?
让我们分析一下到底 bitset 的性能耗用在哪里?
通过分析 bitset 的源码可以清楚看到,所谓的 bitset 其实就是 long 数组,某一个值都需要除以 long 类型的64位,同时还要计算具体是 long 值的第几个 bit,通过位移来实现 ,这样子做好处就是可以节省存储的空间,简单来说,如果我有一个 64 个 document id 需要保存,则只需要 new long[0] , 就可以了,仅一个 long 值,各路大神估计也很明白其中的意思,我就不再啰嗦了。
理论上这是很快的,但得出的结论却不快,原因其实也很简单,由于在计算具体 每一个doc id 会落在数组中哪个 long 的第几个 bit ,需要2次 取余的运算,这一个就是问题的根本所有,不起眼的运算导致了速变慢了很多。具体大家可以写代码验证一下。
各数组类型的速度比较
为了不进行任何的除法或者取余的运算,我们可以使用最简单的方法,直接使用普通的数组
1. 使用 int 数组,一个int占用 4个字节
这样变成了纯通过数组下标操作了,速度快了不小,同样的条件,10次一共用了 0.5秒,平均一次 0.05 秒,约 50毫秒。从中可以看到,因为数组决定了这些在内存中是一排连续的地址,所以速度上提升非常明显!或者你现在也会想到,用 int 太浪费了,用其他更小的类型会怎么样?
2. 使用 char 类型的,占用两个字节
同样的道理,这次发现,同样的操作,换成 char 类型数组,则变成 0.31秒,平均每次 30毫秒,按这样子道理,如果换成 byte 类型,那应该是最快的
3. 使用 byte 类别,一个byte 就是一个字节
事实的确如此,这次同样条件,换成 byte 后,10次运算下来共 0.2 秒,每次约 20 毫秒,这样的速度比之前使用 bitset 的单次 0.1 秒,快了5倍了!
结论:
一个各种类型的对应表
可以看到,其实 bitset 反而最慢,主要是因为在 bitset 里面每一次都需要做大量的取余,除法等运算,如果一两次的运算倒无影响,但进行了1000W次的运算性能损失很可观。
Bitset 是 java 包中提供的工具类,很多人也会使用它,因为它提供了很多丰富的方法,比如取出已选中的值,统计有多少被选中等,对于普通的数组,还需要自己去实现,但我认为不是一个很大问题。
同样的 1000W数组中, bitset 大约只用了 1000w / 64 = 150w 左右的 long 数组,空间上的确比最小的 byte 数组还要小 8 倍,但需要注意的是,在遍历的速度上 byte 数组速度上明显快不小,而且,使用完数组后, GC 也会回收,内存上的使用,我认为问题不大。
最后,再有一点要说明的是,我们的10次测试中,每一次都会重新 new 了 1000W 的数组,假如我们 不把 new 1000W 的数组放到计时里面,就单纯看遍历数组,遍历速度将还会提升一倍!但考滤到, 使用旧的数组还有一个数组清零的过程,时间花费上也跟 new 一个 数组差不多,所以就图方便,直接每次 new 一个数组
by kernaling.wong @ 2014.01.22
- 大小: 65 KB
- 大小: 56.5 KB
- 大小: 56.4 KB
- 大小: 63.9 KB
- 大小: 18.8 KB
分享到:
相关推荐
对lucene的封装对lucene的封装 对lucene的封装 对lucene的封装
lucene、lucene.NET详细使用与优化详解lucene、lucene.NET详细使用与优化详解
一步一步跟我学习lucene是对近期做lucene索引的总结,
我的博客专栏http://blog.csdn.net/wuyinggui10000/article/category/3173543,希望大家关注
Lucene索引优化,是Lucene的wiki上生成的
NULL 博文链接:https://sunfish.iteye.com/blog/1415655
Lucene搜索优化,这是从wiki上保存的
较全面的介绍Lucene的使用与优化技巧,希望对您有所帮助
Lucene的API接口设计的比较通用,输入输出结构都很像数据库的表==>记录==>字段,所以很多传统的应用的文件、数据库等都可以比较方便的映射到Lucene的存储结构/接口中。总体上看:可以先把Lucene当成一个支持全文索引...
lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例lucene实例
本课程由浅入深的介绍了Lucene4的发展历史,开发环境搭建,分析lucene4的中文分词原理,深入讲了lucenne4的系统架构,分析lucene4索引实现原理及性能优化,了解关于lucene4的搜索算法优化及利用java结合lucene4实现...
lucene,lucene教程,lucene讲解。 为了对文档进行索引,Lucene 提供了五个基础的类 public class IndexWriter org.apache.lucene.index.IndexWriter public abstract class Directory org.apache.lucene.store....
本课程由浅入深的介绍了Lucene4的发展历史,开发环境搭建,分析lucene4的中文分词原理,深入讲了lucenne4的系统架构,分析lucene4索引实现原理及性能优化,了解关于lucene4的搜索算法优化及利用java结合lucene4实现...
Lucene之删除索引 Lucene之删除索引 Lucene之删除索引 http://blog.csdn.net/nupt123456789/article/details/10666105
lucene3.0 lucene3.0 lucene3.0 lucene3.0 lucene3.0
lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习lucene学习...
第一章 Lucene是个倒排索引 第二章 Lucene与数据库 第三章 Lucene的索引建立及文件结构 第四章 Lucene的检索机制及文档得分 第五章 Lucene的存储优化 第六章 Lucene的效率优化 第七章 用Lucene加快web开发!
Lucene学习总结之一:全文检索的基本原理 Lucene学习总结之二:Lucene的总体架构 Lucene学习总结之三:Lucene的索引文件格式(1) Lucene学习总结之三:Lucene的索引文件格式(2) Lucene学习总结之三:Lucene的...
包括认识Lucene、建立索引、为应用程序添加搜索功能、高级搜索技术、扩展搜索、使用Tika提取文本、Lucene的高级扩展、使用其他编程语言访问Lucene、Lucene管理和性能调优等内容,最后还提供了三大经典成功案例,为...
Lucene3.0特性Lucene3.0特性