当前位置： 移动技术网 > IT编程>移动开发>Android > Android中SparseArray性能优化的使用方法

Android中SparseArray性能优化的使用方法

2019年07月24日  | 移动技术网IT编程  | 我要评论

雷小二倒酒,中国包装印刷网,馆陶信息港

之前一篇文章研究完横向二级菜单，发现其中使用了sparsearray去替换hashmap的使用.于是乎自己查了一些相关资料,自己同时对性能进行了一些测试。首先先说一下sparsearray的原理.

  sparsearray(稀疏数组).他是android内部特有的api,标准的jdk是没有这个类的.在android内部用来替代hashmap<integer,e>这种形式,使用sparsearray更加节省内存空间的使用,sparsearray也是以key和value对数据进行保存的.使用的时候只需要指定value的类型即可.并且key不需要封装成对象类型.

  楼主根据亲测,sparsearray存储数据占用的内存空间确实比hashmap要小一些.一会放出测试的数据在进行分析。我们首先看一下二者的结构特性.

  hashmap是数组和链表的结合体,被称为链表散列.

  sparsearray是单纯数组的结合.被称为稀疏数组,对数据保存的时候,不会有额外的开销.结构如下：

  这就是二者的结构,我们需要看一下二者到底有什么差异...

  首先是插入：

  hashmap的正序插入：

 hashmap<integer, string>map = new hashmap<integer, string>();
 long start_map = system.currenttimemillis();
 for(int i=0;i<max;i++){
   map.put(i, string.valueof(i));
 }
 long map_memory = runtime.getruntime().totalmemory();
 long end_map = system.currenttimemillis()-start_map;
 system.out.println("<---map的插入时间--->"+end_map+"<---map占用的内存--->"+map_memory);

 执行后的结果:

 <---map的插入时间--->914
 <---map占用的内存--->28598272

sparsearray的正序插入：

 sparsearray<string>sparse = new sparsearray<string>();
 long start_sparse = system.currenttimemillis();
 for(int i=0;i<max;i++){
    sparse.put(i, string.valueof(i));
 }
 long sparse_memory = runtime.getruntime().totalmemory();
 long end_sparse = system.currenttimemillis()-start_sparse;
 system.out.println("<---sparse的插入时间--->"+end_sparse+"<---sparse占用的内存--->"+sparse_memory);

//执行后的结果：
<---sparse的插入时间--->611
<---sparse占用的内存--->23281664

   我们可以看到100000条数据量正序插入时sparsearray的效率要比hashmap的效率要高.并且占用的内存也比hashmap要小一些..这里的正序插入表示的是i的值是从小到大进行的一个递增..序列取决于i的值，而不是for循环内部如何执行...

  通过运行后的结果我们可以发现，sparsearray在正序插入的时候，效率要比hashmap要快得多，并且还节省了一部分内存。网上有很多的说法关于二者的效率问题，很多人都会误认为sparsearray要比hashmap的插入和查找的效率要快，还有人则是认为hash查找当然要比sparsearray中的二分查找要快得多.

  其实我认为android中在保存<integer,value>的时候推荐使用sparsearray的本质目的不是由于效率的原因，而是内存的原因.我们确实看到了插入的时候sparsearray要比hashmap要快.但是这仅仅是正序插入.我们来看看倒序插入的情况.

  hashmap倒序插入：

 system.out.println("<------------- 数据量100000 散列程度小 map 倒序插入--------------->");
 hashmap<integer, string>map_2 = new hashmap<integer, string>();
 long start_map_2 = system.currenttimemillis();
 for(int i=max-1;i>=0;i--){
   map_2.put(max-i-1, string.valueof(max-i-1));
 }
 long map_memory_2 = runtime.getruntime().totalmemory();
 long end_map_2 = system.currenttimemillis()-start_map_2;
 system.out.println("<---map的插入时间--->"+end_map_2+"<---map占用的内存--->"+map_memory_2);
 
 //执行后的结果：
 <------------- 数据量100000 map 倒序插入--------------->
 <---map的插入时间--->836<---map占用的内存--->28598272

  sparsearray倒序插入：

system.out.println("<------------- 数据量100000 散列程度小 sparsearray 倒序插入--------------->");
sparsearray<string>sparse_2 = new sparsearray<string>();
long start_sparse_2 = system.currenttimemillis();
for(int i=max-1;i>=0;i--){
  sparse_2.put(i, string.valueof(max-i-1));
}
long sparse_memory_2 = runtime.getruntime().totalmemory();
long end_sparse_2 = system.currenttimemillis()-start_sparse_2;
system.out.println("<---sparse的插入时间--->"+end_sparse_2+"<---sparse占用的内存--->"+sparse_memory_2);
//执行后的结果
<------------- 数据量100000 sparsearray 倒序插入--------------->
<---sparse的插入时间--->20222<---sparse占用的内存--->23281664

 通过上面的运行结果,我们仍然可以看到,sparsearray与hashmap无论是怎样进行插入,数据量相同时,前者都要比后者要省下一部分内存,但是效率呢？我们可以看到,在倒序插入的时候,sparsearray的插入时间和hashmap的插入时间远远不是一个数量级.由于sparsearray每次在插入的时候都要使用二分查找判断是否有相同的值被插入.因此这种倒序的情况是sparsearray效率最差的时候.

 sparsearray的插入源码我们简单的看一下..

 public void put(int key, e value) {
    int i = containerhelpers.binarysearch(mkeys, msize, key); //二分查找.

    if (i >= 0) { //如果当前这个i在数组中存在,那么表示插入了相同的key值,只需要将value的值进行覆盖..
      mvalues[i] = value;
    } else { //如果数组内部不存在的话,那么返回的数值必然是负数.
      i = ~i; //因此需要取i的相反数.
      //i值小于msize表示在这之前. mkey和mvalue数组已经被申请了空间.只是键值被删除了.那么当再次保存新的值的时候.不需要额外的开辟新的内存空间.直接对数组进行赋值即可.
      if (i < msize && mvalues[i] == deleted) {
        mkeys[i] = key;
        mvalues[i] = value;
        return;
      }
      //当需要的空间要超出,但是mkey中存在无用的数值,那么需要调用gc()函数.
      if (mgarbage && msize >= mkeys.length) {
        gc();
        
        // search again because indices may have changed.
        i = ~containerhelpers.binarysearch(mkeys, msize, key);
      }
      //如果需要的空间大于了原来申请的控件,那么需要为key和value数组开辟新的空间.
      if (msize >= mkeys.length) {
        int n = arrayutils.idealintarraysize(msize + 1);
        //定义了一个新的key和value数组.需要大于msize
        int[] nkeys = new int[n];
        object[] nvalues = new object[n];

        // log.e("sparsearray", "grow " + mkeys.length + " to " + n);
        //对数组进行赋值也就是copy操作.将原来的mkey数组和mvalue数组的值赋给新开辟的空间的数组.目的是为了添加新的键值对.
        system.arraycopy(mkeys, 0, nkeys, 0, mkeys.length);
        system.arraycopy(mvalues, 0, nvalues, 0, mvalues.length);
        //将数组赋值..这里只是将数组的大小进行扩大..放入键值对的操作不在这里完成.
        mkeys = nkeys;
        mvalues = nvalues;
      }
      //如果i的值没有超过msize的值.只需要扩大mkey的长度即可.
      if (msize - i != 0) {
        // log.e("sparsearray", "move " + (msize - i));
        system.arraycopy(mkeys, i, mkeys, i + 1, msize - i);
        system.arraycopy(mvalues, i, mvalues, i + 1, msize - i);
      }
      //这里是用来完成放入操作的过程.
      mkeys[i] = key;
      mvalues[i] = value;
      msize++;
    }
  }

  这就是sparsearray插入函数的源码.每次的插入方式都需要调用二分查找.因此这样在倒序插入的时候会导致情况非常的糟糕,效率上绝对输给了hashmap学过数据结构的大家都知道.map在插入的时候会对冲突因子做出相应的决策.有非常好的处理冲突的方式.不需要遍历每一个值.因此无论是倒序还是正序插入的效率取决于处理冲突的方式,因此插入时牺牲的时间基本是相同的.

  通过插入.我们还是可以看出二者的差异的.

  我们再来看一下查找首先是hashmap的查找.

 system.out.println("<------------- 数据量100000 map查找--------------->");
 hashmap<integer, string>map = new hashmap<integer, string>();
    
 for(int i=0;i<max;i++){
    map.put(i, string.valueof(i));
 }
 long start_time =system.currenttimemillis();
 for(int i=0;i<max;i+=100){
      map.get(i);
 }
 long end_time =system.currenttimemillis()-start_time;
 system.out.println(end_time);
 
 //执行后的结果
 <!---------查找的时间:175------------>

 sparsearray的查找:

 system.out.println("<------------- 数据量100000 sparsearray 查找--------------->");
 sparsearray<string>sparse = new sparsearray<string>();
 for(int i=0;i<10000;i++){
    sparse.put(i, string.valueof(i));
 }
 long start_time =system.currenttimemillis();
    
 for(int i=0;i<max;i+=10){
    sparse.get(i);
 }
 long end_time =system.currenttimemillis()-start_time;
 system.out.println(end_time);
 //执行后的结果
 <!-----------查找的时间:239---------------->

  我这里也简单的对查找的效率进行了测试.对一个数据或者是几个数据的查询.二者的差异还是非常小的.当数据量是100000条.查100000条的效率还是map要快一点.数据量为10000的时候.这就差异性就更小.但是map的查找的效率确实还是赢了一筹.

  其实在我看来.在保存<integer,e>时使用sparsearray去替换hashmap的主要原因还是因为内存的关系.我们可以看到.保存的数据量无论是大还是小,map所占用的内存始终是大于sparsearray的.数据量100000条时sparsearray要比hashmap要节约27%的内存.也就是以牺牲效率的代价去节约内存空间.我们知道android对内存的使用是极为苛刻的.堆区允许使用的最大内存仅仅16m.很容易出现oom现象的发生.因此在android中内存的使用是非常的重要的.因此官方才推荐去使用sparsearray<e>去替换hashmap<integer,e>.官方也确实声明这种差异性不会超过50%.所以牺牲了部分效率换来内存其实在android中也算是一种很好的选择吧.

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网