java - 从 ArrayList 中删除多个元素的快速算法

Question

假设一个 ArrayList 的大小为 n。

在我的例子中，我经常需要从 ArrayList 中删除 1 到 n 个具有不同索引的元素。

通过使用 visualvm 分析器，我发现 ArrayList.remove() 占用了大约 90% 的运行时间。

所以想提高去除的性能。我想知道是否可以加速。

这是一个最小的例子:

public void testArrayListRemove() {
        List list = new ArrayList();
        int[] indexes = new int[] { 1, 2, 4, 10, 100, 1000 };
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
        for (int i = indexes.length - 1; i >= 0; i--) {
            list.remove(indexes[i]);
        }
    }

我能想到的想法是把那些要移除的元素交换到最后，然后在那里移除，这样ArrayList.remove()就不需要make system.arraycopy了。我不确定这是否真的有效。

注意:ArrayList.remove(i) 当i 不是最后一个元素时，它会执行一个System.arraycopy 来移动元素。

如果您能提供解决我的问题的想法，我们将不胜感激。您可以对我将元素交换到最后的幼稚想法发表评论，也可以提供比我的想法更高级的算法。

谢谢。

Answer 1

你应该看看GapList – a lightning-fast List implementation

来自文章:

---

GapList 简介

为了解决所带来的问题，我们引入了 GapList 作为 java.util.List 接口(interface)的另一种实现。作为主要功能，GapList 提供

• 通过索引高效访问元素
• 在列表的头部和尾部进行恒定时间插入
• 利用应用程序中经常出现的引用位置

让我们看看如何实现 GapList 以提供这些功能。

如果我们比较一下 ArrayList 如何处理不同类型的插入，我们可以很快想出一个解决方案，以保证在列表的开头和结尾都能快速插入。

我们不是移动所有元素以在索引 0 处获得空间，而是将现有元素留在原处，如果有剩余空间，则将元素写入已分配数组的末尾。所以我们基本上将数组用作一种旋转缓冲区。

为了以正确的顺序访问元素，我们必须记住第一个元素的起始位置，并使用模运算从逻辑索引计算物理索引:

physIndex = (start + index) % capacity

为了利用引用的局部性，我们允许在列表元素的存储中包含一个间隙。支持阵列中未使用的槽形成的间隙可以在列表中的任何位置。最多有一个间隙，但也可以没有。

这个间隙可以帮助您利用列表引用的局部性，因此如果您将一个元素添加到列表的中间，后续添加到中间的操作将会很快。

如果 GapList 没有间隙，则在需要时创建一个。如果间隙在错误的位置，它会被移动。但是，如果这些操作发生在彼此附近，则只需复制很少的数据。

GapList 还允许在不移动元素的情况下删除开头和结尾的元素。

中间的删除处理类似于插入:如果不再需要，现有间隙可能会被移动或消失。

---

这是一个小示例代码:

package rpax.stackoverflow.q24077045;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import org.magicwerk.brownies.collections.GapList;

public class Q24077045 {

    static int LIST_SIZE = 500000;

    public static void main(String[] args) {
        long a1, b1, c1 = 0, a2, b2, c2 = 0;
        int[] indexes = generateRandomIndexes(10000);

        a2 = System.currentTimeMillis();
        List<Integer> l2 = testArrayListRemove2(indexes);
        if (l2.size() < 1)
            return;
        b2 = System.currentTimeMillis();
        c2 = b2 - a2;

        a1 = System.currentTimeMillis();
        List<Integer> l = testArrayListRemove(indexes);
        if (l.size() < 1)
            return;
        b1 = System.currentTimeMillis();
        c1 = b1 - a1;

        System.out.println("1 : " + c1);
        System.out.println("2 : " + c2);

        System.out.println("Speedup : "+ c1 * 1.00 / c2+"x");

    }

    static int[] generateRandomIndexes(int number) {
        int[] indexes = new int[number];
        for (int i = 0; i < indexes.length; i++)
        {
            indexes[i] = ThreadLocalRandom.current().nextInt(0, LIST_SIZE);
        }
        Arrays.sort(indexes);
        return indexes;
    }

    public static List<Integer> testArrayListRemove(int[] indexes) {
        List<Integer> list = new ArrayList<Integer>(LIST_SIZE);

        for (int i = 0; i < LIST_SIZE; i++)
            list.add(i);

        for (int i = indexes.length - 1; i >= 0; i--)
            list.remove(indexes[i]);
        return list;
    }

    public static List<Integer> testArrayListRemove2(int[] indexes) {

        List<Integer> list = GapList.create(LIST_SIZE);

        for (int i = 0; i < LIST_SIZE; i++)
            list.add(i);

        for (int i = indexes.length - 1; i >= 0; i--)
            list.remove(indexes[i]);
        return list;
    }

}

我的笔记本电脑大约快 10 倍。它似乎是 ArrayList 的一个很好的替代品。

^{免责声明:这不是性能分析。这只是一个说明性示例。}