32

如果它们满足条件，我需要从中删除一些对象，ArrayList我想知道哪种方式更有效。

情况如下：我有一个包含一个ArrayList包含其他对象的类。我必须对此进行迭代ArrayList并删除所有满足特定条件的元素。据我所知，这些将是我删除的选项：

  1. 新建一个ArrayList并添加不满足条件的元素。迭代后，从旧的数组列表交换到没有元素的新数组列表。

  2. 创建一个新的ArrayList并添加满足条件的元素。迭代后，使用removeAll()传递的方法ArrayList与要删除的对象。

有没有更有效的方法从 中删除对象ArrayList？

4

13 回答 13

46

您可以在遍历 ArrayList 时向后迭代并删除。这具有后续元素不需要移动的优点，并且比向前移动更容易编程。

于 2009-08-21T07:52:10.760 回答
16

另一种方式：迭代器有一个可选的 remove() 方法，它是为 ArrayList 实现的。您可以在迭代时使用它。

我不知道，哪个变体性能最好，你应该测量它。

starblue 评论说，复杂性不好，这是真的（对于 removeAll() 也是如此），因为 ArrayList 必须复制所有元素，如果中间是添加或删除的元素。对于这种情况，LinkedList 应该更好地工作。但是，由于我们都不知道您的真实用例，因此最好测量所有变体，以选择最佳解决方案。

于 2009-08-21T07:43:47.190 回答
12

我猜，大多数性能会使用该listIterator方法并进行反向迭代：

for (ListIterator<E> iter = list.listIterator(list.size()); iter.hasPrevious();){
    if (weWantToDelete(iter.previous()))  iter.remove();
}

编辑：很久以后，人们可能还想添加Java 8使用 lambda 或方法引用从列表（或任何集合！）中删除元素的方法。如果您愿意，可以就地filter收集：

list.removeIf(e -> e.isBad() && e.shouldGoAway());

这可能是清理集合的最佳方式。由于它使用内部迭代，集合实现可以采取捷径使其尽可能快（对于ArrayLists，它可以最大限度地减少所需的复制量）。

于 2009-08-21T07:59:43.570 回答
5

显然，在您提到的两种方法中，数字 1 更有效，因为它只需要遍历列表一次，而使用方法 2，列表必须遍历两次（首先找到要删除的元素，然后将它们删除它们）。

实际上，从另一个列表中删除元素列表可能是一种比 O(n) 更糟糕的算法，因此方法 2 更糟糕。

迭代器方法：

List data = ...;

for (Iterator i = data.iterator(); i.hasNext(); ) {
    Object element = i.next();

    if (!(...)) {
        i.remove();
    }
}
于 2009-08-21T07:55:09.337 回答
4

首先，我会确保这确实是一个性能瓶颈，否则我会选择最干净、最具表现力的解决方案。

如果它是性能瓶颈，只需尝试不同的策略，看看什么是最快的。我的赌注是创建一个新的 ArrayList 并将所需的对象放入其中，丢弃旧的 ArrayList。

于 2009-08-21T07:53:54.440 回答
1

除非你确定你面临的问题确实是一个瓶颈，否则我会选择可读的

public ArrayList filterThings() {

    ArrayList pileOfThings;
    ArrayList filteredPileOfThings = new ArrayList();

    for (Thing thingy : pileOfThings) {
        if (thingy.property != 1) {
            filteredPileOfThings.add(thingy);
        }            
    }
    return filteredPileOfThings;
}
于 2009-08-21T08:22:03.900 回答
1

从 ArrayList 中删除元素有一个隐藏的成本。每次删除元素时，都需要移动元素以填充“洞”。平均而言，这将对N / 2具有 N 个元素的列表进行分配。

所以从 N 个元素的 ArrayList 中删除 M 个元素是O(M * N)平均的。O(N) 解决方案涉及创建一个新列表。例如。

List data = ...;
List newData = new ArrayList(data.size()); 

for (Iterator i = data.iterator(); i.hasNext(); ) {
    Object element = i.next();

    if ((...)) {
        newData.add(element);
    }
}

如果 N 很大，我的猜测是这种方法将比removeM 值小至 3 或 4 的方法更快。

但重要的是创建newList足够大以容纳所有元素，list以避免在扩展后备数组时复制它。

于 2009-08-21T10:16:06.663 回答
1 
int sizepuede= listaoptionVO.size();
for (int i = 0; i < sizepuede; i++) {
    if(listaoptionVO.get(i).getDescripcionRuc()==null){
        listaoptionVO.remove(listaoptionVO.get(i));
        i--;
        sizepuede--;
     }
}

编辑：添加缩进

于 2011-05-20T16:25:46.497 回答
0

也许Iterator的remove()方法？JDK 的默认集合类应该是所有支持此方法的创建者迭代器。

于 2009-08-21T07:48:56.570 回答
0

我找到了另一种更快的解决方案：

  int j = 0;
  for (Iterator i = list.listIterator(); i.hasNext(); ) {
    j++;

    if (campo.getNome().equals(key)) {
       i.remove();
       i = list.listIterator(j);
    }
  }
于 2009-09-22T16:07:57.183 回答
0

使用迭代器，您可以始终处理要订购的元素，而不是指定的索引。所以，你不应该为上面的事情而烦恼。

Iterator itr = list.iterator();
String strElement = "";
while(itr.hasNext()){

  strElement = (String)itr.next();
  if(strElement.equals("2"))
  {
    itr.remove();
  }
于 2012-07-11T09:30:24.853 回答
0

虽然这是反直觉的，但这是我大幅加快此操作的方式。

正是我在做什么：

ArrayList < HashMap < String , String >> results; // This has been filled with a whole bunch of results

ArrayList < HashMap < String , String >> 丢弃 = findResultsToDiscard(results);

结果.removeall（丢弃）；

但是，删除所有方法需要 6 秒以上（不包括获取丢弃结果的方法）才能从 2000 个数组（ish）中删除大约 800 个结果。

我尝试了 gustafc 和其他人在这篇文章中建议的迭代器方法。

这确实稍微加快了操作（降低到大约 4 秒），但这仍然不够好。所以我尝试了一些冒险的事情......

 ArrayList < HashMap < String, String>> results;

  List < Integer > noIndex = getTheDiscardedIndexs(results);

for (int j = noIndex.size()-1; j >= 0; j-- ){
    results.remove(noIndex.get(j).intValue());
}

而 getTheDiscardedIndexs 保存索引数组而不是 HashMaps 数组。事实证明，这加快了删除对象的速度（现在大约 0.1 秒），并且内存效率更高，因为我们不需要创建大量结果来删除。

希望这可以帮助某人。

于 2012-08-03T16:17:05.850 回答
-2

我很喜欢 Mnementh 的建议。
不过只有一个警告，

 ConcurrentModificationException

请注意，您运行的线程不超过一个。如果执行多个线程并且线程没有很好地同步，则可能会出现此异常。

于 2009-08-21T09:13:27.290 回答