文档章节

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

假装是大神
 假装是大神
发布于 2015/06/07 18:34
字数 851
阅读 16
收藏 0
点赞 0
评论 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列, 看看哪个快?

    有兴趣可试试....


© 著作权归作者所有

共有 人打赏支持
假装是大神
粉丝 16
博文 33
码字总数 7065
作品 0
广州
技术主管
Java集合框架总结(4)——List接口的使用

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

dong.li ⋅ 2012/04/24 ⋅ 1

jdk1.6的集合源码阅读之ArrayList

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

双月通天 ⋅ 2016/08/23 ⋅ 0

Java 持有对象简要笔记

Set 不保存重复的数,如果这个 数已经重复那么会自动被抛弃。 HAshSet提供最快的查询速度 TreeSet除了上述的功能外还会帮助用户自动排序 Queue 队列是先进先出通常用offer(E e)来插入数据,p...

罗布V ⋅ 2012/03/19 ⋅ 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

JAVA容器-自问自答学ArrayList

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

liangzzz ⋅ 2017/08/15 ⋅ 0

ArrayList超详细源码解析

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

她的梦z ⋅ 05/15 ⋅ 0

ArrayList的使用

问题的提出 给出了两个时间点(例如,20060321,20080402),要求计算出中间的所有日期,并显示出来。在调用的时候需要拿一个容器将这些日期存放起来。但是,由于时间点是随机给出,不能确定数...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

Java 基础(八)手撸 ArrayList、HashMap、TreeMap

学了这么久的集合终于要结束了,在最后,我们手撸几个集合聊表对自己刻苦学习的尊敬吧~ 本次一共选择了三个具有代表性的集合作为模仿对象,分别是 ArrayList、HashMap、TreeMap。至于为什么选...

diamond_lin ⋅ 2017/10/20 ⋅ 0

Java中List的集合

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

西红柿的眼泪 ⋅ 2016/07/14 ⋅ 0

正确使用ArrayList和LinkedList

原文链接地址 最近在看数据结构,发现这个东西不错,记录下来,以便分享! ArrayList内部是使用可増长数组实现的,所以是用get和set方法是花费常数时间的,但是如果插入元素和删除元素,除非...

zongjh ⋅ 2014/05/06 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring Boot整合模板引擎thymeleaf

项目结构 引入依赖pom.xml <!-- 引入 thymeleaf 模板依赖 --><dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-thymeleaf</artifactId......

yysue ⋅ 19分钟前 ⋅ 0

ConstraintLayout使用解析

AndroidStudio3.0创建Project默认的布局就是ConstraintLayout。 AndroidStudio3.0前的可以自己修改,使用ConstraintLayout。 为了要使用ConstraintLayout,我们需要在app/build.gradle文件中...

_OUTMAN_ ⋅ 31分钟前 ⋅ 0

OSChina 周三乱弹 —— 这样的女人私生活太混乱了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 胖达panda :你经历过体验到人生的大起大落吗?我一朋友在10秒内体验了,哈哈。@小小编辑 请点一首《almost lover》送给他。 《almost love...

小小编辑 ⋅ 今天 ⋅ 9

自己动手写一个单链表

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号:好好学java,获取优质学习资源。 一、概述 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对...

公众号_好好学java ⋅ 今天 ⋅ 0

Centos7重置Mysql 8.0.1 root 密码

问题产生背景: 安装完 最新版的 mysql8.0.1后忘记了密码,向重置root密码;找了网上好多资料都不尽相同,根据自己的问题总结如下: 第一步:修改配置文件免密码登录mysql vim /etc/my.cnf 1...

豆花饭烧土豆 ⋅ 今天 ⋅ 0

熊掌号收录比例对于网站原创数据排名的影响[图]

从去年下半年开始,我在写博客了,因为我觉得业余写写博客也还是很不错的,但是从2017年下半年开始,百度已经推出了原创保护功能和熊掌号平台,为此,我也提交了不少以前的老数据,而这些历史...

原创小博客 ⋅ 今天 ⋅ 0

LVM讲解、磁盘故障小案例

LVM LVM就是动态卷管理,可以将多个硬盘和硬盘分区做成一个逻辑卷,并把这个逻辑卷作为一个整体来统一管理,动态对分区进行扩缩空间大小,安全快捷方便管理。 1.新建分区,更改类型为8e 即L...

蛋黄Yolks ⋅ 今天 ⋅ 0

Hadoop Yarn调度器的选择和使用

一、引言 Yarn在Hadoop的生态系统中担任了资源管理和任务调度的角色。在讨论其构造器之前先简单了解一下Yarn的架构。 上图是Yarn的基本架构,其中ResourceManager是整个架构的核心组件,它负...

p柯西 ⋅ 今天 ⋅ 0

uWSGI + Django @ Ubuntu

创建 Django App Project 创建后, 可以看到路径下有一个wsgi.py的问题 uWSGI运行 直接命令行运行 利用如下命令, 可直接访问 uwsgi --http :8080 --wsgi-file dj/wsgi.py 配置文件 & 运行 [u...

袁祾 ⋅ 今天 ⋅ 0

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部