Java：高效的ArrayList过滤？

Question

我需要过滤一个ArrayList并移除找到的元素。作为一个相对新手的Java程序员，我想知道最有效的方法是什么（因为它要在移动设备上运行）。目前我是这样做的：

// We display only top-level dealers (parentId=-10)
ArrayList<DealerProductCount> subDealers = new ArrayList<DealerProductCount>();
for (DealerProductCount dealer : wsResponse.Dealers) {
    if (dealer.ParentId != -10) subDealers.add(dealer);
}
wsResponse.Dealers.removeAll(subDealers);

能否在不使用临时对象的情况下完成？也许可以通过直接操作（删除）正在迭代的列表元素来实现吗？

- Bachi

---

还有其他数据结构，其中项目删除更有效率。从LinkedList中删除将具有O(n)性能。从HashMap中删除将具有恒定时间性能。 - Programmer Bruce

Answer 1

从一个ArrayList高效地移除多个元素需要一些思考。 像下面这样的朴素方法：

Iterator<DealerProductCount> it = wsResponse.Dealers.iterator();
while (it.hasNext()) {
    if (it.next().ParentId != -10) { 
        it.remove(); 
    }
}

问题在于每次删除一个元素时，你平均要拷贝剩余元素的一半。这是因为从ArrayList中删除一个元素需要将该元素后面的所有元素向左移动一个位置。

你原来的解决方案涉及到要删除的元素列表，实际上也是做同样的事情。不幸的是，ArrayList的属性并不允许removeAll比上述方法更好。

如果你希望删除多个元素，则以下方案更加高效：

ArrayList<DealerProductCount> retain =
        new ArrayList<DealerProductCount>(wsResponse.Dealers.size());
for (DealerProductCount dealer : wsResponse.Dealers) {
    if (dealer.ParentId == -10) {
        retain.add(dealer);
    }
}
// either assign 'retain' to 'wsResponse.Dealers' or ...
wsResponse.Dealers.clear();
wsResponse.Dealers.addAll(retain);

我们几乎完全复制了整个列表两次，因此如果您删除少于4个元素，则应该能够达到平衡（平均而言）。

---

有趣的是，函数式编程语言/库通常支持筛选方法，并且可以通过一次遍历列表来执行此任务；即更有效率。我认为如果/当Java支持lambda并且集合API被改进以使用它们，我们可以期望显着的改进。 更新：有了Java 8 lambda和streams，我们可以实现这个用例。

- Stephen C

---

感谢Stephen提供的深入解释！所以我们可以得出结论，通常最好填充一个新的ArrayList而不是从现有的ArrayList中删除元素。很好知道这一点！ - Bachi

Answer 2

如果您使用迭代器，您可以在迭代时安全地删除元素。

- Petar Minchev

---

（如果迭代器提供了remove的实现-它可能会抛出UnsupportedOperationException-所以这仅在您非常了解迭代器的情况下才有效） - Andreas Dolk

Answer 3

一种方法是使用迭代器而不是 for each 循环：

Iterator<DealerProductCount> iter = wsResponse.Dealers.iterator()
while(iter.hasNext()) {
    if (iter.next().ParentId != -10) iter.remove();
}

- Joshua