Java:高效的ArrayList筛选? [英] Java: Efficient ArrayList filtering?

问题描述

我需要过滤ArrayList并删除找到的元素.作为Java的新手，我想知道实现这一目标的最有效方法是什么(这是因为它可以在移动设备上运行).目前，我正在这样做:

I need to filter an ArrayList and remove found elements. Being relatively new to Java, I'm wondering what the most efficent method is to achieve this (matters because it runs on mobile devices). Currently I do this:

// 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);

可以在没有临时对象的情况下完成此操作吗?也许直接操作(删除)要迭代的列表中的元素?

Can it be done without temporary objects? Maybe by directly manipulating (removing) elements of the list being iterated?

推荐答案

要有效地从ArrayList中删除许多元素，需要一些思考.天真的方法是这样的:

Efficiently removing a number of elements from an ArrayList requires some thought. The naive approach is something like this:

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

问题在于，每次删除元素时，您平均都会复制一半的剩余元素.这是因为从ArrayList中删除一个元素需要在元素删除到左侧一个位置之后复制所有元素.

The problem is that each time you remove an element you copy (on average) half of the remaining elements. This is because removing an element from an ArrayList entails copying all elements after element removed one position to the left.

您最初涉及要删除的元素列表的解决方案实际上执行相同的操作.不幸的是，ArrayList的属性不允许removeAll做得比上述更好.

Your original solution involving the list of elements to be removed essentially does the same thing. Unfortunately, the properties of an ArrayList don't allow removeAll to do better than the above.

如果您希望删除许多元素，则以下方法会更有效:

If you expect to remove a number of elements, the following is more efficient:

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个元素，这应该(平均)达到收支平衡.

We are copying (almost) the entire list twice, so this should break even (on average) if you remove as few as 4 elements.

有趣的是，功能性编程语言/库通常支持一种过滤方法，并且可以一遍遍地完成此任务.即更有效率.我认为，如果/当Java支持lambda并增强了collection API以便使用它们时，我们可以期待会有显着的改进.

It is interesting to note that functional programming languages / libraries typical support a filter method, and that can do this task in one pass through the list; i.e. a lot more efficiently. I think we can expect significant improvements if / when Java supports lambdas, and the collection APIs are enhanced to use them.

更新，并通过Java 8 lambda和流，在此用例中获得了它们.

UPDATE and with Java 8 lambdas and streams, we get them ... for this use-case.

这篇关于Java:高效的ArrayList筛选?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！