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

假设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 = 0; i--) { list.remove(indexes[i]); } } 

我能想到的想法是将那些被删除的元素交换到最后并将其删除，以便ArrayList.remove（）不需要生成system.arraycopy。 我不确定这是否真的有效。

注意：ArrayList.remove（i）当我不是最后一个元素时，它将执行System.arraycopy来移动元素。

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

谢谢。

Answer 1

你应该看看GapList – 一个闪电般快速的List实现

来自文章：

---

GapList简介

为了解决问题，我们引入了GapList作为java.util.List接口的另一个实现。 作为主要function，GapList提供

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

让我们看看如何实现GapList来提供这些function。

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

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

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

 physIndex = (start + index) % capacity 

为了利用引用的局部性，我们允许在列表元素的存储中包含间隙。 由后备arrays中未使用的插槽形成的间隙可以是列表中的任何位置。 最多只有一个差距，但也可能没有。

这个差距可以帮助您利用列表的引用位置，因此如果您在列表的中间添加一个元素，则中间的后续添加将很快。

如果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 l2 = testArrayListRemove2(indexes); if (l2.size() < 1) return; b2 = System.currentTimeMillis(); c2 = b2 - a2; a1 = System.currentTimeMillis(); List 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 testArrayListRemove(int[] indexes) { List list = new ArrayList(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 testArrayListRemove2(int[] indexes) { List 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 

Answer 3

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

ArrayLists不是一个存储大量数据的好结构，因为内存使用很快就会出现，并且搜索/删除时间非常快。

Answer 4

ArrayList实际上不是一个很好的数据结构来执行此操作。

我建议您使用HashMap来实现此目的，您可以将密钥，值对与密钥保持为索引。