问题描述
假设一个ArrayList是大小为n的。
Say an ArrayList is of size n.
在我的情况，我经常需要从1转移到n个元素具有不同的索引，从一个ArrayList
In my case, I often need to remove from 1 to n elements with different indexes from an ArrayList.
使用了VisualVM探查器，我发现ArrayList.remove（）花了大约90％的运行时间。
By using visualvm profiler, I found the ArrayList.remove() took around 90% of the running time.
所以我想提高除去性能。我不知道是否会加速进行。
So I want to improve the performance of the removal. I wonder if it could be accelerated.
下面是一个小例子：
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。我不知道这是否会真正发挥作用。
The idea I can think of is to exchange those to be removed elements to the end and remove them there so that ArrayList.remove() do not need to make system.arraycopy. I am not sure whether this will really work.
注：ArrayList.remove（我）当我不是最后一个元素，它会执行System.arraycopy移动元素。
Note: ArrayList.remove(i) when i is not the last element, it will perform a System.arraycopy to move elements.
这将是非常美联社preciated如果你能提供思路来处理我的问题。您可以在交换的元素到最后甚至可能更好地提供更先进的算法比我的想法其他的我天真的想法发表意见。
It would be very appreciated if you can provide ideas to deal with my problem. You can either comment on my naive idea of exchanging elements to the end or maybe even better provide more advanced algorithms other than my idea.
感谢。
推荐答案
您应该看一看的
从文章：
介绍GapList
要解决带出了问题，我们引入GapList作为另一个实施的java.util.List 接口。作为主要特点，GapList提供
To solve the issues brought out, we introduce GapList as another implementation of the java.util.List interface. As main features, GapList provides
- 通过索引高效的访问元素
- 在头部和列表的尾部固定时间插入
- 漏洞引用的位置常见于应用程序
让我们来看看GapList是如何实现的，以提供这些功能。
Let's see how GapList is implemented to offer these features.
如果我们比较如何在不同种类的刀片由ArrayList的处理，我们可以迅速拿出一个溶液，以保证快速插入两者在开始和在列表的末尾。
If we compare how the different kind of inserts are handled by ArrayList, we can quickly come up with a solution to guarantee fast insertion both at the beginning and at the end of the list.
而不是移动的所有元素，以获得空间索引0，我们留在原地已经存在的元素，写元素在分配的数组结束时，如果有剩余空间。因此，我们基本上用数组作为一种旋转的缓冲区。
Instead of moving all elements to gain space at index 0, we leave the existing elements in place and write the elements at the end of the allocated array if there is space left.So we basically use the array as a kind of rotating buffer.
有关访问以正确的顺序的要素，我们必须记住的第一个元素的开始位置，并使用模运算从逻辑1来计算物理索引
For accessing the elements in the right order, we have to remember the start position of the first element and use a modulo operation to calculate the physical index from the logical one:
physIndex = (start + index) % capacity
要利用引用的位置，我们允许的间隙被包括在列表中的元素存储。由背衬阵列中的未使用的插槽形成的间隙可以是在列表中的任何地方。有至多一个间隙，但也可以是无
To exploit the locality of reference, we allow a gap to be included in the storage of the list elements. The gap formed by the unused slots in the backing array can be anywhere in the list. There is at most one gap, but there can also be none.
这差距可帮助您采取的参考名单所在地的优势，所以，如果你的元素添加到列表的中间，随后除了中间会很快。
This gap helps you to take advantage of the locality of reference to the list, so if you add an element to the middle of the list, a subsequent addition to the middle will be fast.
如果一个GapList没有间隙，一个是如果需要创建。如果间隙是在错误的地点，很是感动。但是，如果操作发生邻近彼此，只有很少的数据将不得不被复制。
If a GapList has no gap, one is created if needed. If the gap is at a wrong place, it is moved. But if the operations happen near to each other, only few data will have to be copied.
GapList还允许去除在开始和结束时的元素没有元件的任何移动。
GapList also allows removal of elements at the beginning and at the end without any moving of elements.
在中减除的处理方式类似于插入：现有的差距可能会被移动或不再需要消失
Removals in the middle are handled similar to insertions: an existing gap may be moved or vanish if no longer needed.
下面是一个小样本code：
Here's a small sample code:
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 。
这篇关于快速算法从一个ArrayList删除一些元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！