好的，现在是测试不同方法的结果。以下是我测试过的各种方法（每个方法的名称也是我的源代码中的类名）：
NaiveRemoveManyPerformer - 使用迭代器和remove方法的ArrayList - 这是我在问题中提出的第一个简单实现。BetterNaiveRemoveManyPerformer - 使用反向迭代和从后往前删除的ArrayList。LinkedRemoveManyPerformer - 使用迭代器和remove方法但只适用于LinkedList。缺点：仅适用于LinkedList。CreateNewRemoveManyPerformer - 将ArrayList复制为新ArrayList（仅添加保留的元素），使用迭代器遍历输入的ArrayList。SmartCreateNewRemoveManyPerformer - 更好的CreateNewRemoveManyPerformer - 将结果ArrayList的初始大小（容量）设置为最终列表的大小。缺点：必须在开始时知道列表的最终大小。FasterSmartCreateNewRemoveManyPerformer - 更好的SmartCreateNewRemoveManyPerformer - 使用项目索引（items.get(idx)）而不是迭代器。MagicRemoveManyPerformer - 在ArrayList中原地工作（不进行列表复制），并将空洞（已删除的项）从列表开头压缩到列表末尾的项目中。缺点：此方法更改了列表中的项目顺序。ForwardInPlaceRemoveManyPerformer - 在ArrayList中原地工作 - 将保留的项目移动以填补空洞，最后返回子列表（没有最终的删除或清除）。GuavaArrayListRemoveManyPerformer - 使用Google Guava Iterables.removeIf处理ArrayList - 几乎与ForwardInPlaceRemoveManyPerformer相同，但在列表末尾执行最终的删除操作。
完整的源代码在本答案的结尾给出。
测试使用了不同的列表大小（从10,000个项目到10,000,000个项目）和不同的删除系数（指定必须从列表中删除多少个项目）。
正如我在其他答案的评论中所述 - 我认为将项目从ArrayList复制到第二个ArrayList比迭代LinkedList并仅删除项目要快。 Sun的Java文档表示，与LinkedList实现相比，ArrayList的常数因子较低，但令人惊讶的是，在我的问题中并非如此。
在实践中，大多数情况下使用简单迭代和删除的 LinkedList （这种方法在 LinkedRemoveManyPerformer 中实现）具有最佳性能。通常只有 MagicRemoveManyPerformer 的性能与 LinkedRemoveManyPerformer 相当，其他方法明显较慢。Google Guava 的 GuavaArrayListRemoveManyPerformer 比手写类似代码慢（因为我的代码不会删除列表末尾的不必要项目）。
从 1,000,000 个源项中删除 500,000 个项的示例结果：
- NaiveRemoveManyPerformer：未执行测试-我没有那么耐心，但它的表现比 BetterNaiveRemoveManyPerformer 差。
- BetterNaiveRemoveManyPerformer: 226080 毫秒
- LinkedRemoveManyPerformer: 69 毫秒
- CreateNewRemoveManyPerformer: 246 毫秒
- SmartCreateNewRemoveManyPerformer: 112 毫秒
- FasterSmartCreateNewRemoveManyPerformer: 202 毫秒
- MagicRemoveManyPerformer: 74 毫秒
- ForwardInPlaceRemoveManyPerformer: 69 毫秒
- GuavaArrayListRemoveManyPerformer: 118 毫秒
从 1,000,000 个源项中删除 1 个项的示例结果（第一项已被删除）：
- BetterNaiveRemoveManyPerformer: 34 毫秒
- LinkedRemoveManyPerformer: 41 毫秒
- CreateNewRemoveManyPerformer: 253 毫秒
- SmartCreateNewRemoveManyPerformer: 108 毫秒
- FasterSmartCreateNewRemoveManyPerformer: 71 毫秒
- MagicRemoveManyPerformer: 43 毫秒
- ForwardInPlaceRemoveManyPerformer: 73 毫秒
- GuavaArrayListRemoveManyPerformer: 78 毫秒
从 1,000,000 个源项中删除 333,334 个项的示例结果：
- BetterNaiveRemoveManyPerformer: 253206 毫秒
- LinkedRemoveManyPerformer: 69 毫秒
- CreateNewRemoveManyPerformer: 245 毫秒
- SmartCreateNewRemoveManyPerformer: 111 毫秒
- FasterSmartCreateNewRemoveManyPerformer: 203 毫秒
- MagicRemoveManyPerformer: 69 毫秒
- ForwardInPlaceRemoveManyPerformer: 72 毫秒
- GuavaArrayListRemoveManyPerformer: 102 毫秒
移除100万个元素的操作结果（全部元素都被移除，但是需要一个接一个地处理。如果您预先知道要删除所有元素，则应该简单清空列表）：
- BetterNaiveRemoveManyPerformer: 58毫秒
- LinkedRemoveManyPerformer: 88毫秒
- CreateNewRemoveManyPerformer: 95毫秒
- SmartCreateNewRemoveManyPerformer: 91毫秒
- FasterSmartCreateNewRemoveManyPerformer: 48毫秒
- MagicRemoveManyPerformer: 61毫秒
- ForwardInPlaceRemoveManyPerformer: 49毫秒
- GuavaArrayListRemoveManyPerformer: 133毫秒
我的最终结论：使用混合方法-如果处理LinkedList，则简单迭代和移除是最好的，如果处理ArrayList--它取决于项目顺序是否重要——然后使用ForwardInPlaceRemoveManyPerformer，如果项目顺序可以改变，则最佳选择是MagicRemoveManyPerformer。如果事先知道要删除的因素（您知道将删除多少项与保留多少项），则可以添加更多条件以选择在特定情况下表现更好的方法。但是已知删除因子不是常见情况... Google Guava Iterables.removeIf 是这样一种混合解决方案，但具有稍微不同的假设（原始列表必须更改，不能创建新列表，并且项目顺序始终很重要） - 这些是最常见的假设，因此removeIf 在大多数实际情况下都是最佳选择。
还要注意，所有良好的方法（naive不好！）都足够好-它们中的任何一个都应该在实际应用程序中表现出色，但必须避免naive方法。
最后-我的测试源代码。
package WildWezyrListRemovalTesting;
import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class RemoveManyFromList {
public static abstract class BaseRemoveManyPerformer {
protected String performerName() {
return getClass().getSimpleName();
}
protected void info(String msg) {
System.out.println(performerName() + ": " + msg);
}
protected void populateList(List<Integer> items, int itemCnt) {
for (int i = 0; i < itemCnt; i++) {
items.add(i);
}
}
protected boolean mustRemoveItem(Integer itemVal, int itemIdx, int removeFactor) {
if (removeFactor == 0) {
return false;
}
return itemIdx % removeFactor == 0;
}
protected abstract List<Integer> removeItems(List<Integer> items, int removeFactor);
protected abstract List<Integer> createInitialList();
public void testMe(int itemCnt, int removeFactor) {
List<Integer> items = createInitialList();
populateList(items, itemCnt);
long startMillis = System.currentTimeMillis();
items = removeItems(items, removeFactor);
long endMillis = System.currentTimeMillis();
int chksum = 0;
for (Integer item : items) {
chksum += item;
}
info("removing took " + (endMillis - startMillis)
+ " milli(s), itemCnt=" + itemCnt
+ ", removed items: " + (itemCnt - items.size())
+ ", remaining items: " + items.size()
+ ", checksum: " + chksum);
}
}
private List<BaseRemoveManyPerformer> rmps =
new ArrayList<BaseRemoveManyPerformer>();
public void addPerformer(BaseRemoveManyPerformer rmp) {
rmps.add(rmp);
}
private Runtime runtime = Runtime.getRuntime();
private void runGc() {
for (int i = 0; i < 5; i++) {
runtime.gc();
}
}
public void testAll(int itemCnt, int removeFactor) {
runGc();
for (BaseRemoveManyPerformer rmp : rmps) {
rmp.testMe(itemCnt, removeFactor);
}
runGc();
System.out.println("\n--------------------------\n");
}
public static class NaiveRemoveManyPerformer
extends BaseRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
if (items.size() > 300000 && items instanceof ArrayList) {
info("this removeItems is too slow, returning without processing");
return items;
}
int i = 0;
Iterator<Integer> iter = items.iterator();
while (iter.hasNext()) {
Integer item = iter.next();
if (mustRemoveItem(item, i, removeFactor)) {
iter.remove();
}
i++;
}
return items;
}
@Override
public List<Integer> createInitialList() {
return new ArrayList<Integer>();
}
}
public static class BetterNaiveRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
for (int i = items.size(); --i >= 0;) {
Integer item = items.get(i);
if (mustRemoveItem(item, i, removeFactor)) {
items.remove(i);
}
}
return items;
}
}
public static class LinkedRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> createInitialList() {
return new LinkedList<Integer>();
}
}
public static class CreateNewRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
List<Integer> res = createResultList(items, removeFactor);
int i = 0;
for (Integer item : items) {
if (mustRemoveItem(item, i, removeFactor)) {
} else {
res.add(item);
}
i++;
}
return res;
}
protected List<Integer> createResultList(List<Integer> items, int removeFactor) {
return new ArrayList<Integer>();
}
}
public static class SmartCreateNewRemoveManyPerformer
extends CreateNewRemoveManyPerformer {
@Override
protected List<Integer> createResultList(List<Integer> items, int removeFactor) {
int newCapacity = removeFactor == 0 ? items.size()
: (int) (items.size() * (removeFactor - 1L) / removeFactor + 1);
return new ArrayList<Integer>(newCapacity);
}
}
public static class FasterSmartCreateNewRemoveManyPerformer
extends SmartCreateNewRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
List<Integer> res = createResultList(items, removeFactor);
for (int i = 0; i < items.size(); i++) {
Integer item = items.get(i);
if (mustRemoveItem(item, i, removeFactor)) {
} else {
res.add(item);
}
}
return res;
}
}
public static class ForwardInPlaceRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
int j = 0;
for (int i = 0; i < items.size(); i++) {
Integer item = items.get(i);
if (mustRemoveItem(item, i, removeFactor)) {
} else {
if (j < i) {
items.set(j, item);
}
j++;
}
}
return items.subList(0, j);
}
}
public static class MagicRemoveManyPerformer
extends NaiveRemoveManyPerformer {
@Override
public List<Integer> removeItems(List<Integer> items, int removeFactor) {
for (int i = 0; i < items.size(); i++) {
if (mustRemoveItem(items.get(i), i, removeFactor)) {
Integer retainedItem = removeSomeFromEnd(items, removeFactor, i);
if (retainedItem == null) {
items.remove(i);
break;
}
items.set(i, retainedItem);
}
}
return items;
}
private Integer removeSomeFromEnd(List<Integer> items, int removeFactor, int lowerBound) {
for (int i = items.size(); --i > lowerBound;) {
Integer item = items.get(i);
items.remove(i);
if (!mustRemoveItem(item, i, removeFactor)) {
return item;
}
}
return null;
}
}
public static class GuavaArrayListRemoveManyPerformer
extends BaseRemoveManyPerformer {
@Override
protected List<Integer> removeItems(List<Integer> items, final int removeFactor) {
Iterables.removeIf(items, new Predicate<Integer>() {
public boolean apply(Integer input) {
return mustRemoveItem(input, input, removeFactor);
}
});
return items;
}
@Override
protected List<Integer> createInitialList() {
return new ArrayList<Integer>();
}
}
public void testForOneItemCnt(int itemCnt) {
testAll(itemCnt, 0);
testAll(itemCnt, itemCnt);
testAll(itemCnt, itemCnt - 1);
testAll(itemCnt, 3);
testAll(itemCnt, 2);
testAll(itemCnt, 1);
}
public static void main(String[] args) {
RemoveManyFromList t = new RemoveManyFromList();
t.addPerformer(new NaiveRemoveManyPerformer());
t.addPerformer(new BetterNaiveRemoveManyPerformer());
t.addPerformer(new LinkedRemoveManyPerformer());
t.addPerformer(new CreateNewRemoveManyPerformer());
t.addPerformer(new SmartCreateNewRemoveManyPerformer());
t.addPerformer(new FasterSmartCreateNewRemoveManyPerformer());
t.addPerformer(new MagicRemoveManyPerformer());
t.addPerformer(new ForwardInPlaceRemoveManyPerformer());
t.addPerformer(new GuavaArrayListRemoveManyPerformer());
t.testForOneItemCnt(1000);
t.testForOneItemCnt(10000);
t.testForOneItemCnt(100000);
t.testForOneItemCnt(200000);
t.testForOneItemCnt(300000);
t.testForOneItemCnt(500000);
t.testForOneItemCnt(1000000);
t.testForOneItemCnt(10000000);
}
}
