假设 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 来移动元素。
如果您能提供解决我的问题的想法，我将不胜感激。您可以评论我将元素交换到最后的天真想法，或者甚至更好地提供除我的想法之外的更高级的算法。
Thanks.
你应该看看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.
Disclaimer: This is not a performance analisis. It is only an illustrative example.