如何有效（性能）从Java中的列表中删除许多项？
我有一个很大的List命名项（> =
1,000,000个项），并且用
我的目标是有效删除
这是我的测试代码：
System.out.println("preparing items");
List<Integer> items = new ArrayList<Integer>(); // Integer is for demo
for (int i = 0; i < 1000000; i++) {
items.add(i * 3); // just for demo
}
System.out.println("deleting items");
long startMillis = System.currentTimeMillis();
items = removeMany(items);
long endMillis = System.currentTimeMillis();
System.out.println("after remove: items.size=" + items.size() +
" and it took " + (endMillis - startMillis) + " milli(s)");
和天真的实现：
public static <T> List<T> removeMany(List<T> items) {
int i = 0;
Iterator<T> iter = items.iterator();
while (iter.hasNext()) {
T item = iter.next();
// <cond> goes here
if (/*<cond>: */i % 2 == 0) {
iter.remove();
}
i++;
}
return items;
}
如您所见，我使用项索引模2 == 0作为删除条件（
removeMany可以提供哪个更好的版本，为什么这个更好的版本实际上更好呢？
问题答案：
好的，现在该是提出的方法的测试结果了。这里是我测试过的方法（每种方法的名称在我的资源中也是类名）：
NaiveRemoveManyPerformer-ArrayList使用迭代器和删除-我的问题中给出的第一个天真的实现。BetterNaiveRemoveManyPerformer-ArrayList向后迭代并从头到尾删除。LinkedRemoveManyPerformer-天真的迭代器，并删除但仍在进行LinkedList。障碍：仅适用于LinkedList。CreateNewRemoveManyPerformer-ArrayList作为副本制作（仅添加保留的元素），迭代器用于遍历inputArrayList。SmartCreateNewRemoveManyPerformer-更好CreateNewRemoveManyPerformer-结果的初始大小（容量）ArrayList设置为最终列表大小。缺点：启动时必须知道列表的最终大小。FasterSmartCreateNewRemoveManyPerformer-更好（？）SmartCreateNewRemoveManyPerformer-使用项目索引（items.get(idx)）代替迭代器。MagicRemoveManyPerformer-ArrayList从列表末尾的项目开始就位（无列表副本）并压缩孔（已删除的项目）。缺点：此方法更改列表中项目的顺序。ForwardInPlaceRemoveManyPerformer-适用于ArrayList-移动保留项以填充孔，最后返回subList（没有最终移除或清除）。GuavaArrayListRemoveManyPerformer-Google GuavaIterables.removeIf用于ArrayList-几乎与ForwardInPlaceRemoveManyPerformer列表末尾相同，但最终将其删除。
完整的源代码在此答案的末尾给出。
使用不同的列表大小（从10,000项到10,000,000项）和不同的删除因子（指定必须从列表中删除多少个项目）执行测试。
正如我在此处的评论中发布的其他答案一样，我认为将项目从复制ArrayList到秒ArrayList将比迭代LinkedList和删除项目要快。Sun的Java文档说，ArrayList与LinkedList实现相比，常数因子低，但是令人惊讶的是，我的问题并非如此。
实际上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毫
从1,000,000个源项目中删除1,000,000个（所有）项目的示例结果（所有项目都被删除，但经过一个接一个的处理，如果您先验地知道要删除所有项目，则应该简单地清除列表）：
- 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最好大多数现实生活中的选择。
还要注意，所有好的方法（天真的不好！）都足够好-在实际应用中，其中任何一个都做得很好，但是必须避免使用天真的方法。
最后-我的测试源代码。
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) {
// if (items.size() > 300000 && items instanceof ArrayList) {
// info("this removeItems is too slow, returning without processing");
// return items;
// }
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)) {
// no-op
} 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);
//System.out.println("newCapacity=" + newCapacity);
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)) {
// no-op
} 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; // destination idx
for (int i = 0; i < items.size(); i++) {
Integer item = items.get(i);
if (mustRemoveItem(item, i, removeFactor)) {
// no-op
} 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);
}
}
-
问题内容： 我想从列表中删除重复项，但我无法正常工作： 问题答案： 如果该代码不起作用，则可能是你未在该类上正确实现。 大概有一些钥匙（我们称之为）可以唯一地标识一个客户。例如 的适当定义equals(Object)如下所示： 为了完整起见，你还应该实现hashCode两个Customer相等的对象将返回相同的哈希值。hashCode上述定义的匹配项为equals： 还值得注意的是，如果列表很大，
-
问题内容： 我将如何使用python检查列表并删除所有重复项？我不需要指定重复项是什么- 我希望代码找出是否存在重复项，如果有则将其删除，每个重复项仅保留一个实例。如果列表中有多个重复项，它也必须起作用。 例如，在下面的代码中，列表lseparatedOrbList有12个项目-一项被重复六次，一项被重复五次，并且只有一个实例。我希望它更改列表，因此只有三项-每一项，并且它们之前出现的顺序相同。我
-
问题内容： 我试图一次从几个表中删除。我做了一些研究，并提出了 但是，我收到此错误 未捕获的Database_Exception [1064]：您的SQL语法有错误；检查与您的MySQL服务器版本相对应的手册以获取正确的语法，以在’p，pa … 附近使用… 我以前从未做过跨表删除操作，所以我现在还没有经验，并且一直坚持下去！ 我究竟做错了什么？ 问题答案： 在语句中使用a 。 另外，您可以使用…
-
问题内容： 我有一个清单，里面有空清单： 如何删除空列表，以便获得： 我尝试了list.remove（’‘），但这不起作用。 问题答案： 尝试 如果您想摆脱所有“虚假”的东西，例如空字符串，空元组，零，您也可以使用
-
我最近开始发现Databricks，并面临需要删除增量表的某个列的情况。当我使用后格雷SQL时，它就像 我正在浏览有关删除的数据砖文档，但它仅涵盖。 我还找到了关于DROP数据库、DROP函数和DROP表的文档，但对于如何从delta表中删除列却一无所知。我在这里错过了什么？是否有标准的方法从delta表中删除列？
-
问题内容： 我有创建元素的代码。我需要单击一次删除一个元素。对于每个元素，我都有。我了解我需要一些功能来通过删除项目。如何使用此功能删除ReactJS中的元素？我的代码： 问题答案： 您正在父级组件中管理数据并在子级组件中呈现UI，因此要从子级组件中删除项目，您需要将一个函数与数据一起传递，从子级中调用该函数并在父级组件内部传递列表项的任何唯一标识符使用该唯一标识符删除项目。 步骤1： 将父组件的