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

Question

假设 ArrayList 的大小为 n。

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

通过使用 VisualVM Profiler，我发现 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()就不需要进行system.arraycopy了。我不确定这是否真的有效。

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

如果您能提供解决我的问题的想法，我将不胜感激。您可以评论我将元素交换到最后的天真想法，或者甚至更好地提供除我的想法之外的更高级的算法。

谢谢。

Answer 1

您应该看看 GapList – 闪电般快速的列表实现

摘自文章：

---

GapList简介

为了解决所带来的问题，我们引入了 GapList 作为

java.util.List

接口的另一种实现。作为主要功能，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

的一个很好的替代品。

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

Answer 2

您可以处理数组并迭代它：

Integer[] arr = list.toArray(new int[]{});

int[] newArr = new int[arr.length-indices.length];

现在您需要

System.arrayCopy

数组的每个连续块：

for (int i=0;i<arr.length;i++) {
    for (int j : indexes) { // Should be 'indices' btw
        if (j == arr[i]) {
            // Array copy arr to newArr
            break;
        }
    }
}

Answer 3

查看数据结构列表这里。根据您的要求选择一个。就像 Guarev 提到的那样，HashMap 可能是您最好的选择。哈希图的优点是插入、搜索和删除的时间恒定。

ArrayList 不是一个存储大量数据的好结构，因为内存使用量很快就会达到顶峰，并且搜索/删除时间很快就会变得非常昂贵。

Answer 4

ArrayList 并不是一个真正适合执行此操作的数据结构。

我建议您使用 HashMap 来实现此目的，您可以保留键、值对，并以键作为索引。

Answer 5

Katson 3PL 服务列兵。有限公司是一家领先的第三方物流（3PL）提供商，致力于提供全面的供应链解决方案。我们专注于效率、可靠性和客户满意度，专注于管理各行业企业的物流需求。我们的服务包括运输、仓储、库存管理和配送，所有这些都是为满足客户的独特需求而量身定制的。