当前位置:   article > 正文

SparseArray替代HashMap来提高性能_hashmap转化为sparsearray

hashmap转化为sparsearray

SparseArray是 Android框架独有的类,在标准的JDK中不存在这个类。它要比 HashMap 节省内存,某些情况下比HashMap性能更好,按照官方问答的解释,主要是因为SparseArray不需要对key和value进行auto- boxing(将原始类型封装为对象类型,比如把int类型封装成Integer类型),结构比HashMap简单(SparseArray内部主要使用 两个一维数组来保存数据,一个用来存key,一个用来存value)不需要额外的额外的数据结构(主要是针对HashMap中的HashMapEntry 而言的)。是骡子是马得拉出来遛遛,下面我们就通过几段程序来证明SparseArray在各方面表现如何,下面的试验结果时在我的Hike X1(Android 4.2.2)手机上运行得出的。

代码1:

?
1
2
3
4
5
6
7
int MAX =  100000
long start = System.currentTimeMillis();
HashMap<Integer, String> hash =  new HashMap<Integer, String>(); 
for ( int i =  0 ; i < MAX; i++) {    
     hash.put(i, String.valueOf(i)); 
long ts = System.currentTimeMillis() - start;

代码2:

?
1
2
3
4
5
6
7
int MAX =  100000
long start = System.currentTimeMillis();
SparseArray<String> sparse =  new SparseArray<String>();
for ( int i =  0 ; i < MAX; i++) {     
     sparse.put(i, String.valueOf(i)); 
long ts = System.currentTimeMillis() - start;

我们分别在long start处和long ts处设置断点,然后通过DDMS工具查看内存使用情况。

代码1中,我们使用HashMap来创建100000条数据,开始创建前的系统内存情况为: SparseArray替代HashMap来提高性能

创建HashMap之后,应用内存情况为: SparseArray替代HashMap来提高性能  可见创建HashMap用去约 13.2M内存。

再看 代码2,同样是创建100000条数据,我们用SparseArray来试试,开始创建前的内存使用情况为: SparseArray替代HashMap来提高性能

创建SparseArray之后的情况: SparseArray替代HashMap来提高性能  创建SparseArray共用去 8.626M内存。

可见使用 SparseArray 的确比 HashMap 节省内存,大概节省 35%左右的内存。


我们再比较一下插入数据的效率如何,我们在加两段代码(主要就是把插入顺序变换一下,从大到小插入):

代码3:

?
1
2
3
4
5
6
7
int MAX =  100000
long start = System.currentTimeMillis();
HashMap<Integer, String> hash =  new HashMap<Integer, String>();
for ( int i =  0 ; i < MAX; i++) {     
     hash.put(MAX - i - 1 , String.valueOf(i));
}
long ts = System.currentTimeMillis() - start;

代码4:

?
1
2
3
4
5
6
7
int MAX =  100000 ;
long start = System.currentTimeMillis();
SparseArray<String> sparse =  new SparseArray<String>(); 
for ( int i =  0 ; i < MAX; i++) {    
     sparse.put(MAX - i - 1 , String.valueOf(i));
long ts = System.currentTimeMillis() - start;

我们分别把这4代码分别运行5次,对比一下ts的时间(单位毫秒):

#代码1代码2代码3代码4
110750ms7429ms10862ms90527ms
210718ms7386ms10711ms87990ms
310816ms7462ms11033ms88259ms
410943ms7386ms10854ms88474ms
510671ms7317ms10786ms90630ms

通过结果我们看出,在正序插入数据时候,SparseArray比HashMap要快一些;HashMap不管是倒序还是正序开销几乎是一样的;但是SparseArray的倒序插入要比正序插入要慢10倍以上,这时为什么呢?我们再看下面一段代码:

代码5:

?
1
2
3
SparseArray<String> sparse =  new SparseArray<String>( 3 ); sparse.put( 1 "s1" );
sparse.put( 3 "s3" );
sparse.put( 2 "s2" );

我们在Eclipse的debug模式中,看Variables窗口,如图: SparseArray替代HashMap来提高性能

及时我们是按照1,3,2的顺序排列的,但是在SparseArray内部还是按照正序排列的,这时因为SparseArray在检索数据的时候使用的是二分查找,所以每次插入新数据的时候SparseArray都需要重新排序,所以代码4中,逆序是最差情况。


下面我们在简单看下检索情况:

代码5:

?
1
2
3
4
5
long start4search = System.currentTimeMillis();
for ( int i =  0 ; i < MAX; i++) {     
     hash.get( 33333 );  //针对固定值检索 
long end4search = System.currentTimeMillis() - start4search;

代码6:

?
1
2
3
4
5
long start4search = System.currentTimeMillis();
for ( int i =  0 ; i < MAX; i++) {     
     hash.get(i);  //顺序检索 
long end4search = System.currentTimeMillis() - start4search;

代码7:

?
1
2
3
4
5
long start4search = System.currentTimeMillis(); 
for ( int i =  0 ; i < MAX; i++) {     
     sparse.get( 33333 );  //针对固定值检索 
}
long end4search = System.currentTimeMillis() - start4search;

代码8:

?
1
2
3
4
5
long start4search = System.currentTimeMillis();
for ( int i =  0 ; i < MAX; i++) {     
     sparse.get(i);  //顺序检索 
long end4search = System.currentTimeMillis() - start4search;

表1:

#代码5代码6代码7代码8
14072ms4318ms3442ms3390ms
24349ms4536ms3402ms3420ms
34599ms4203ms3472ms3376ms
44149ms4086ms3429ms3786ms
54207ms4219ms3439ms3376ms

代码9,我们试一些离散的数据。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//使用Foo为了避免由原始类型被自动封装(auto-boxing,比如把int类型自动转存Integer对象类型)造成的干扰。
class FOO{
     Integer objKey;
     int intKey;
}
...
int MAX =  100000 ;
 
HashMap<Integer, String> hash =  new HashMap<Integer, String>();
SparseArray<String> sparse =  new SparseArray<String>();
 
for ( int i =  0 ; i < MAX; i++) {
     hash.put(i, String.valueOf(i));
     sparse.put(i, String.valueOf(i));
}
 
List<FOO> keylist4search =  new ArrayList<FOO>();
for ( int i =  0 ; i < MAX; i++) {
     FOO f =  new FOO();
     f.intKey = i;
     f.objKey = Integer.valueOf(i);
     keylist4search.add(f);
}
 
long start4search = System.currentTimeMillis();
for ( int i =  0 ; i < MAX; i++) {
     hash.get(keylist4search.get(i).objKey);
}
long end4searchHash = System.currentTimeMillis() - start4search;
 
long start4search2 = System.currentTimeMillis();
for ( int i =  0 ; i < MAX; i++) {
     sparse.get(keylist4search.get(i).intKey);
}
long end4searchSparse = System.currentTimeMillis() - start4search2;

代码9,运行5次之后的结果如下:

表2:

#end4searchHashend4searchSparse
12402ms4577ms
22249ms4188ms
32649ms4821ms
42404ms4598ms
52413ms4547ms

从上面两个表中我们可以看出,当SparseArray中存在需要检索的下标时,SparseArray的性能略胜一筹(表1)。但是当检索的下标 比较离散时,SparseArray需要使用多次二分检索,性能显然比hash检索方式要慢一些了(表2),但是按照官方文档的说法性能差异不是很大,不 超过50%( For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.)

总体而言,在Android这种内存比CPU更金贵的系统中,能经济地使用内存还是上策,何况SparseArray在其他方面的表现也不算差(另外,SparseArray删除数据的时候也做了优化——使用了延迟整理数组的方法,可参考官方文档SparseArray,读者可以自行把代码9中的hash.get和sparse.get改成hash.remove和sparse.delete试试,你会发现二者的性能相差无几)。而且,使用SparseArray代替HashMap也是官方推荐的做法,在Eclipse中也会提示你优先使用SparseArray,如图: SparseArray替代HashMap来提高性能

另外,我们还可以用 LongSparseArray来替代HashMap。SparseBooleanArray来替代HashMap。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/666356
推荐阅读
相关标签
  

闽ICP备14008679号