技巧:ArrayList删除元素时, 从尾部开始遍历,可大大提升执行效率

一.描述:

    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()

 

public E remove(int index) {
        RangeCheck(index);

        modCount++;
        E oldValue = (E) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
    }

            里面的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是最快的,因为不涉及内存移动. 

 

import java.util.ArrayList;
import java.util.List;

public class $ {

    private static int MAX = 100000;

    public static void main(String[] args) {
        System.out.println("容量:" + MAX);
        removeFromF();
        removeFromL();
    }

    private static void removeFromF() {

        List data = initData();

        long l0 = System.currentTimeMillis();
        for (int i = 0; i < data.size() - 1; i++) {
            data.remove(i--);
        }
        long l1 = System.currentTimeMillis();

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

    private static void removeFromL() {

        List data = initData();

        long l0 = System.currentTimeMillis();
        for (int i = data.size() - 2; i >= 0; i--) {
            data.remove(i);
        }
        long l1 = System.currentTimeMillis();

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

    private static List initData() {
        List data = new ArrayList();
        for (int i = 0; i < MAX; i++) {
            data.add(i);
        }
        return data;
    }
}

 

    结果:

 

容量:100000
从前往后remove(留下最后一个):3596MS
从后往前remove(留下最后一个):6MS

 

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

 

六.番外:

 

    随便记一下:

 

    public E remove(int index) {
        RangeCheck(index);

        modCount++;
        E oldValue = (E) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
    }

 

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

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

 

七:扩展:

 

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

 

    举例:

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

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

    有兴趣可试试....

 

不错，学到了

具体源码没看，但是删除应该是从后面来删除~！

高性能JavaScript里面也提到过，逆序比正序要快。
而且，可以把每次循环里执行的调用做多点，性能会更好。
当然，是对JavaScript而言。
没想到Java也有类似的问题，学习了！

很棒，学到了，楼主加油。

平凡删除，无须插入 建议使用LinkedList.   学java的时候 没学过吗？

这个和语言无关，是数据结构上的东东了

唉，看来还是当初在学校没学好！

表示楼主，从头到尾删除的时候只删了一半，
for(int i=0;i<data.size();i--){}
每次data。size();少一，有i--,每次i减掉2，所以、、、、

多谢提醒,应该是
for (int i = 0; i < data.size() - 1; i++) {
    data.remove(i--);
}

上面代码已经变更