文档章节

最快删除 ArrayList 里面元素的方法实践

假装是大神
 假装是大神
发布于 2015/06/07 18:34
字数 851
阅读 27
收藏 0

一.描述:

    1. 工作中,常常遇到这样的要求: 将列表里符合(或不符合)某条件的元素删除, 如:

        有列表list = [ "a", "b", "c", "d" ], 删除其中的"a", "b", "c"

    2. 关键在于遍历: 建议从尾部开始, 取代常规的从头部开始

    3. 有人会说 使用 LinkedList 更合适 -- 此处只考虑 ArrayList;

 

二.推断:

    当 list 删除元素 "a" 之后, 变为 [ "b", "c", "d" ], 猜想, list 内部数组发生变化(内存的变化):

        list(1) --> list(0),

        list(2) --> list(1),

        list(3) --> list(2),

        list(4)删除

 

    list(n):表示list内部数组的元素;

    -->    :表示复制到,或移动到

 

三.证明:

            查看源码java.util.ArrayList.remove()

 

Java代码  收藏代码

  1. public E remove(int index) {  

  2.         RangeCheck(index);  

  3.   

  4.         modCount++;  

  5.         E oldValue = (E) elementData[index];  

  6.   

  7.         int numMoved = size - index - 1;  

  8.         if (numMoved > 0)  

  9.             System.arraycopy(elementData, index + 1, elementData, index, numMoved);  

  10.         elementData[--size] = null// Let gc do its work  

  11.   

  12.         return oldValue;  

  13.     }  

            里面的System.arraycopy(),正是将 欲删除的元素 后面的 元素, 依次向前移动一个位置(内存), 最后再将

   最后一个元素删除(值空, 删除由GC处理).

            与预想的吻合.

 

四.分析:

    1.从list头部开始遍历:

       列表元素                            删除元素        操作后列表元素           内存移动次数

     ----------------------------------------------------------------------------------------------------

       [ "a", "b", "c", "d" ]             "a"            [ "b", "c", "d" ]         3

              [ "b", "c", "d" ]             "b"            [ "c", "d" ]                2

                     [ "c", "d" ]             "c"             [  "d" ]                     1

     ----------------------------------------------------------------------------------------------------

                               合计                                                              6

 

    2.从list尾部开始遍历:

       列表元素                            删除元素        操作后列表元素           内存移动次数

     ----------------------------------------------------------------------------------------------------

       [ "a", "b", "c", "d" ]             "c"            [ "a", "b", "d" ]         1

             [ "a", "b", "d" ]             "b"            [ "a", "d" ]                1

                    [ "a", "d" ]             "a"            [  "d" ]                      1

     ----------------------------------------------------------------------------------------------------

                               合计                                                              3

 

    3.综上两点, 从list尾部开始遍历 可以减少底层的操作次数, 提高程序执行得效率.

 

五.实践:

 

    此例, 删除了99999个元素(共100000), 免得有人投机取巧用clear,当然用clear是最快的,因为不涉及内存移动. 

 

Java代码  收藏代码

  1. import java.util.ArrayList;  

  2. import java.util.List;  

  3.   

  4. public class $ {  

  5.   

  6.     private static int MAX = 100000;  

  7.   

  8.     public static void main(String[] args) {  

  9.         System.out.println("容量:" + MAX);  

  10.         removeFromF();  

  11.         removeFromL();  

  12.     }  

  13.   

  14.     private static void removeFromF() {  

  15.   

  16.         List data = initData();  

  17.   

  18.         long l0 = System.currentTimeMillis();  

  19.         for (int i = 0; i < data.size() - 1; i++) {  

  20.             data.remove(i--);  

  21.         }  

  22.         long l1 = System.currentTimeMillis();  

  23.   

  24.         System.out.println("从前往后remove(留下最后一个):" + (l1 - l0) + "MS");  

  25.     }  

  26.   

  27.     private static void removeFromL() {  

  28.   

  29.         List data = initData();  

  30.   

  31.         long l0 = System.currentTimeMillis();  

  32.         for (int i = data.size() - 2; i >= 0; i--) {  

  33.             data.remove(i);  

  34.         }  

  35.         long l1 = System.currentTimeMillis();  

  36.   

  37.         System.out.println("从后往前remove(留下最后一个):" + (l1 - l0) + "MS");  

  38.     }  

  39.   

  40.     private static List initData() {  

  41.         List data = new ArrayList();  

  42.         for (int i = 0; i < MAX; i++) {  

  43.             data.add(i);  

  44.         }  

  45.         return data;  

  46.     }  

  47. }  

 

    结果:

 

Java代码  收藏代码

  1. 容量:100000  

  2. 从前往后remove(留下最后一个):3596MS  

  3. 从后往前remove(留下最后一个):6MS  

 

   这耗时, 不是一个数量级的,随着数据增大, 差距越明显.

 

六.番外:

 

    随便记一下:

 

Java代码  收藏代码

  1. public E remove(int index) {  

  2.     RangeCheck(index);  

  3.   

  4.     modCount++;  

  5.     E oldValue = (E) elementData[index];  

  6.   

  7.     int numMoved = size - index - 1;  

  8.     if (numMoved > 0)  

  9.         System.arraycopy(elementData, index + 1, elementData, index, numMoved);  

  10.     elementData[--size] = null// Let gc do its work  

  11.   

  12.     return oldValue;  

  13. }  

 

   当做其删除操作时, list 内部数组的大小是没有变化的(假如此时GC尚未工作), 变化的只是size, 而在外部我们能得到的

是size, 最多也只能得到 0 ~ size-1 的元素.

 

七:扩展:

 

    手动删除excel列时,也建议 从后面开始删. 源码没有看过,是根据现象猜测的.

 

    举例:

    excel2007 (2003没试过,猜想应该是一样的)

    从A ~ BB列, 20000行数据, 删除其中的A列 和 BB列, 看看哪个快?

    有兴趣可试试....


本文转载自:http://www.iteye.com/topic/1128264

共有 人打赏支持
假装是大神
粉丝 16
博文 33
码字总数 7065
作品 0
广州
技术主管
私信 提问
jdk1.6的集合源码阅读之ArrayList

简述 ArrayList其实就是动态数组,是Array的复杂版本,动态扩容和缩容,灵活的设置数组的大小,等等。 其定义如下 而AbstractCollection实现了Collection的部分方法和AbstractList继承了该A...

双月通天
2016/08/23
18
0
Java集合框架总结(4)——List接口的使用

List集合代表一个有序集合,集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素,可以通过索引来访问指定位置的集合元素。 1、List接口和ListIterator接口 List作为Collection接...

dong.li
2012/04/24
0
1
ArrayList超详细源码解析

查询某节点数据、更改某节点数据,快 增加、删除可能会慢,存在扩容和移动元素。 底层实现是Object数组 默认大小为10 ArrayList类的继承关系: 比对着源码看一下 可以看到继承了AbstractLis...

她的梦z
05/15
0
0
JAVA容器-自问自答学ArrayList

前言 在之前的几篇文章里面,我主要都是推荐了一些工具类,为的就是让大家可以提高开发效率,但是我们在提高开发效率,也应该提高代码的执行效率,注重代码的质量。如何提高,其中的一个好办...

liangzzz
2017/08/15
0
0
Java中判断字符串是否为数字的五种方法

//方法一:用JAVA自带的函数 public static boolean isNumeric(String str){ for (int i = str.length();--i>=0;){ if (!Character.isDigit(str.charAt(i))){ return false; } } return true......

冰shang蚊
05/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

jquery通过id显示隐藏

var $div3 = $('#div3'); 显示 $div3.show(); 隐藏 $div3.hide();

yan_liu
今天
3
0
《乱世佳人》读书笔记及相关感悟3900字

《乱世佳人》读书笔记及相关感悟3900字: 之前一直听「荔枝」,后来不知怎的转向了「喜马拉雅」,一听就是三年。上班的时候听房产,买房了以后听装修,兴之所至时听旅行,分手后听亲密关系,...

原创小博客
今天
3
0
大数据教程(9.6)map端join实现

上一篇文章讲了mapreduce配合实现join,本节博主将讲述在map端的join实现; 一、需求 实现两个“表”的join操作,其中一个表数据量小,一个表很大,这种场景在实际中非常常见,比如“订单日志...

em_aaron
今天
3
0
cookie与session详解

session与cookie是什么? session与cookie属于一种会话控制技术.常用在身份识别,登录验证,数据传输等.举个例子,就像我们去超市买东西结账的时候,我们要拿出我们的会员卡才会获取优惠.这时...

士兵7
今天
3
0
十万个为什么之为什么大家都说dubbo

Dubbo是什么? 使用背景 dubbo为什么这么流行, 为什么大家都这么喜欢用dubbo; 通过了解分布式开发了解到, 为适应访问量暴增,业务拆分后, 子应用部署在多台服务器上,而多台服务器通过可以通过d...

尾生
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部