文档章节

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

假装是大神
 假装是大神
发布于 2015/06/07 18:34
字数 851
阅读 18
收藏 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容器-自问自答学ArrayList

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

liangzzz
2017/08/15
0
0
ArrayList超详细源码解析

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

她的梦z
05/15
0
0
Java集合框架总结(4)——List接口的使用

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

dong.li
2012/04/24
0
1
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

没有更多内容

加载失败,请刷新页面

加载更多

Mac OS X下Maven的安装与配置

Mac OS X 安装Maven: 下载 Maven, 并解压到某个目录。例如/Users/robbie/apache-maven-3.3.3 打开Terminal,输入以下命令,设置Maven classpath $ vi ~/.bash_profile 添加下列两行代码,之后...

TonyStarkSir
今天
3
0
关于编程,你的练习是不是有效的?

最近由于工作及Solution项目的影响,我在重新学习DDD和领域建模的一些知识。然后,我突然就想到了这个问题,以及我是怎么做的? 对于我来说,提升技能的项目会有四种: 纯兴趣驱动的项目。即...

问题终结者
今天
4
0
打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部