为什么Java的ArrayList的删除功能似乎花费这么少？

Question

我有一个操作非常大的列表的功能,超过大约250,000个项目.对于大多数这些项目,它只是替换位置x处的项目.但是,对于它们中的大约5%,它必须从列表中删除它们.

使用LinkedList似乎是避免昂贵删除的最明显的解决方案.然而,自然地,随着时间的推移,通过索引访问LinkedList变得越来越慢.这里的成本是几分钟(其中很多).

在LinkedList上使用Iterator也很昂贵,因为我似乎需要一个单独的副本来避免在编辑该列表时出现Iterator并发问题.这里的费用是几分钟.

然而,这是我的思绪被吹嘘的地方.如果我更改为ArrayList,它几乎立即运行.

对于包含297515个元素的列表,删除11958个元素并修改其他所有元素需要909ms.我确认结果列表的大小确实是285557,如预期的那样,并包含我需要的更新信息.

为什么这么快？我查看了JDK6中ArrayList的源代码,它似乎正在按预期使用arraycopy函数.我很想理解为什么ArrayList在这里工作得很好,当常识似乎表明这个任务的数组是一个可怕的想法,需要移动几十万个项目.

Answer 1

我运行了一个基准测试,尝试以下每个策略来过滤列表元素:

• 将所需元素复制到新列表中
• 用于Iterator.remove()从中删除不需要的元素ArrayList
• 用于Iterator.remove()从a中删除不需要的元素LinkedList
• 将列表压缩到原位(将所需元素移动到较低位置)
• 通过索引(List.remove(int))删除ArrayList
• 通过索引(List.remove(int))删除LinkedList

每次我用10万个随机实例填充列表Point并使用过滤条件(基于哈希码)接受95%的元素并拒绝剩下的5%(问题中陈述的比例相同,但列表较小因为我没有时间为250000元素运行测试.)

平均时间(在我的旧MacBook Pro:Core 2 Duo,2.2GHz,3Gb RAM上)是:

CopyIntoNewListWithIterator   :      4.24ms
CopyIntoNewListWithoutIterator:      3.57ms
FilterLinkedListInPlace       :      4.21ms
RandomRemoveByIndex           :    312.50ms
SequentialRemoveByIndex       :  33632.28ms
ShiftDown                     :      3.75ms

因此,通过索引从a中删除元素LinkedList比从其中删除它们的成本高出300多倍ArrayList,并且可能比其他方法(避免线性搜索arraycopy)的价格高出6000-10000倍.

这四种更快的方法之间似乎没有太大区别,但我再次使用500000元素列表运行这四种方法,结果如下:

CopyIntoNewListWithIterator   :     92.49ms
CopyIntoNewListWithoutIterator:     71.77ms
FilterLinkedListInPlace       :     15.73ms
ShiftDown                     :     11.86ms

我猜测,随着更大的缓存内存成为限制因素,因此创建列表的第二个副本的成本变得非常重要.

这是代码:

import java.awt.Point;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;

public class ListBenchmark {

    public static void main(String[] args) {
        Random rnd = new SecureRandom();
        Map<String, Long> timings = new TreeMap<String, Long>();
        for (int outerPass = 0; outerPass < 10; ++ outerPass) {
            List<FilterStrategy> strategies =
                Arrays.asList(new CopyIntoNewListWithIterator(),
                              new CopyIntoNewListWithoutIterator(),
                              new FilterLinkedListInPlace(),
                              new RandomRemoveByIndex(),
                              new SequentialRemoveByIndex(),
                              new ShiftDown());
            for (FilterStrategy strategy: strategies) {
                String strategyName = strategy.getClass().getSimpleName();
                for (int innerPass = 0; innerPass < 10; ++ innerPass) {
                    strategy.populate(rnd);
                    if (outerPass >= 5 && innerPass >= 5) {
                        Long totalTime = timings.get(strategyName);
                        if (totalTime == null) totalTime = 0L;
                        timings.put(strategyName, totalTime - System.currentTimeMillis());
                    }
                    Collection<Point> filtered = strategy.filter();
                    if (outerPass >= 5 && innerPass >= 5) {
                        Long totalTime = timings.get(strategyName);
                        timings.put(strategy.getClass().getSimpleName(), totalTime + System.currentTimeMillis());
                    }
                    CHECKSUM += filtered.hashCode();
                    System.err.printf("%-30s %d %d %d%n", strategy.getClass().getSimpleName(), outerPass, innerPass, filtered.size());
                    strategy.clear();
                }
            }
        }
        for (Map.Entry<String, Long> e: timings.entrySet()) {
            System.err.printf("%-30s: %9.2fms%n", e.getKey(), e.getValue() * (1.0/25.0));
        }
    }

    public static volatile int CHECKSUM = 0;

    static void populate(Collection<Point> dst, Random rnd) {
        for (int i = 0; i < INITIAL_SIZE; ++ i) {
            dst.add(new Point(rnd.nextInt(), rnd.nextInt()));
        }
    }

    static boolean wanted(Point p) {
        return p.hashCode() % 20 != 0;
    }

    static abstract class FilterStrategy {
        abstract void clear();
        abstract Collection<Point> filter();
        abstract void populate(Random rnd);
    }

    static final int INITIAL_SIZE = 100000;

    private static class CopyIntoNewListWithIterator extends FilterStrategy {
        public CopyIntoNewListWithIterator() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            ArrayList<Point> dst = new ArrayList<Point>(list.size());
            for (Point p: list) {
                if (wanted(p)) dst.add(p);
            }
            return dst;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class CopyIntoNewListWithoutIterator extends FilterStrategy {
        public CopyIntoNewListWithoutIterator() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            int inputSize = list.size();
            ArrayList<Point> dst = new ArrayList<Point>(inputSize);
            for (int i = 0; i < inputSize; ++ i) {
                Point p = list.get(i);
                if (wanted(p)) dst.add(p);
            }
            return dst;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class FilterLinkedListInPlace extends FilterStrategy {
        public String toString() {
            return getClass().getSimpleName();
        }
        FilterLinkedListInPlace() {
            list = new LinkedList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (Iterator<Point> it = list.iterator();
                 it.hasNext();
                 ) {
                Point p = it.next();
                if (! wanted(p)) it.remove();
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final LinkedList<Point> list;
    }

    private static class RandomRemoveByIndex extends FilterStrategy {
        public RandomRemoveByIndex() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (int i = 0; i < list.size();) {
                if (wanted(list.get(i))) {
                    ++ i;
                } else {
                    list.remove(i);
                }
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class SequentialRemoveByIndex extends FilterStrategy {
        public SequentialRemoveByIndex() {
            list = new LinkedList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (int i = 0; i < list.size();) {
                if (wanted(list.get(i))) {
                    ++ i;
                } else {
                    list.remove(i);
                }
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final LinkedList<Point> list;
    }

    private static class ShiftDown extends FilterStrategy {
        public ShiftDown() {
            list = new ArrayList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            int inputSize = list.size();
            int outputSize = 0;
            for (int i = 0; i < inputSize; ++ i) {
                Point p = list.get(i);
                if (wanted(p)) {
                    list.set(outputSize++, p);
                }
            }
            list.subList(outputSize, inputSize).clear();
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

}

Answer 2

数组副本是一种相当昂贵的操作.它是在一个非常基础的层次上完成的(它是一个java本机静态方法),你还没有在性能变得非常重要的范围内.

在您的示例中,您复制大约12000次大小为150000(平均)的数组.这不需要太多时间.我在笔记本电脑上测试了它,花了不到500毫秒.

更新我在笔记本电脑上使用以下代码进行测量(英特尔P8400)

import java.util.Random;

public class PerformanceArrayCopy {

    public static void main(String[] args) {

        int[] lengths = new int[] { 10000, 50000, 125000, 250000 };
        int[] loops = new int[] { 1000, 5000, 10000, 20000 };

        for (int length : lengths) {
            for (int loop : loops) {

                Object[] list1 = new Object[length];
                Object[] list2 = new Object[length];

                for (int k = 0; k < 100; k++) {
                    System.arraycopy(list1, 0, list2, 0, list1.length);
                }

                int[] len = new int[loop];
                int[] ofs = new int[loop];

                Random rnd = new Random();
                for (int k = 0; k < loop; k++) {
                    len[k] = rnd.nextInt(length);
                    ofs[k] = rnd.nextInt(length - len[k]);
                }

                long n = System.nanoTime();
                for (int k = 0; k < loop; k++) {
                    System.arraycopy(list1, ofs[k], list2, ofs[k], len[k]);
                }
                n = System.nanoTime() - n;
                System.out.print("length: " + length);
                System.out.print("\tloop: " + loop);
                System.out.print("\truntime [ms]: " + n / 1000000);
                System.out.println();
            }
        }
    }
}

一些结果:

length: 10000   loop: 10000 runtime [ms]: 47
length: 50000   loop: 10000 runtime [ms]: 228
length: 125000  loop: 10000 runtime [ms]: 575
length: 250000  loop: 10000 runtime [ms]: 1198

Answer 3

我认为性能的差异可能归结为ArrayList支持随机访问的区别,其中LinkedList没有.

如果我想得到(1000)一个ArrayList我指定一个特定的索引来访问它,但是LinkedList不支持这个,因为它是通过Node引用组织的.

如果我调用LinkedList的get(1000),它将迭代整个列表,直到找到索引1000,如果LinkedList中有大量项目,这可能过于昂贵.

Answer 4

有趣和意想不到的结果.这只是一个假设,但......

平均来说,你的一个数组元素删除需要移动一半的列表(后面的所有内容)返回一个元素.如果每个项目是一个指向对象的64位指针(8个字节),则表示复制125000个项目x每个指针8个字节= 1 MB.

现代CPU可以非常快速地将1 MB RAM的连续块复制到RAM.

与每次访问的链接列表循环相比,这需要比较和分支以及其他CPU不友好的活动,RAM副本很快.

您应该真正尝试独立地对各种操作进行基准测试,并了解它们对各种列表实现的效率.如果你这样做,在这里分享你的结果

Answer 5

我在这里故意跳过一些实现细节,只是为了解释根本区别.

要删除M个元素列表的第N个元素,LinkedList实现将向上导航到此元素,然后只需删除它并相应地更新N-1和N + 1个元素的指针.第二个操作非常简单,但是这个元素需要花费你的时间.

但是对于ArrayList,访问时间是瞬时的,因为它由数组支持,这意味着连续的内存空间.您可以直接跳转到正确的内存地址,从广义上讲,执行以下操作:

• 重新分配一个新的M - 1元素数组
• 在新的arraylist数组中,将0到N - 1的所有内容放在索引0处
• 把所有N + 1都放在arraylist数组中索引N的M处.

考虑到它,您会注意到您甚至可以重用相同的数组,因为Java可以使用具有预先分配大小的ArrayList,因此如果删除元素,您也可以跳过步骤1和2并直接执行步骤3并更新您的大小.

内存访问速度很快,在现代硬件上复制大块内存的速度可能足够快,因此移动到N位置太费时间了.

但是,如果您使用LinkedList,它允许您删除多个彼此跟随的元素并跟踪您的位置,您会看到增益.

但显然,在很长的清单上,做一个简单的删除(i)将是昂贵的.

为此添加一些盐和香料:

• 请参阅有关阵列数据结构效率的说明以及动态阵列 维基百科条目上的性能说明,它们描述了您的问题.
• 请记住,使用需要连续内存的内存结构需要连续的内存.这意味着您的虚拟内存需要能够分配连续的块.或者甚至使用Java,你会发现你的JVM很快就会遇到一个模糊的OutOfMemoryException,它会导致低级崩溃.