在没有外部库的情况下过滤Java列表

此问题类似于What is the best way to filter a Java Collection?“基于谓词过滤a java.util.Collection”。与在没有外部库的情况下过滤Java列表

滤波器代替进行（O(1)存储器不包括输入），因为该列表是大的额外要求
不需要外部库（即番石榴，Apache的共享空间，等等）可被用于
Java 7的兼容（没有Java 8流）

我们可以假设java.util.Collection类型是java.util.List实现.remove(int)

级

可能的解决方案：

使用的List的Iterator的.remove()方法。这可能会引发UnsupportedOperationException因为.remove()方法任选负载在Iterator
是遍历列表使用索引，.size()写我们自己的迭代器，并.remove(int)

是否有任何简单的解决方案？

是Iterator.remove()对所有执行.remove(int)的标准Java List和/或Collection执行吗？

来源

2016-03-14 arcyqwerty

@AndyTurner，谢谢。我已经更新了我的问题的最后一点，然后：“Iterator.remove（）是否实现了所有标准Java List和/或实现'.remove（int）'？”的集合类。 – arcyqwerty

使用for循环，但从列表的末尾开始并递减到开始。这种方式删除元素不会影响指数计数器。 –

@BoristheSpider它适用于一般性的非Android特定问题。我确实在问题中指定了Java 7。 – arcyqwerty

有适合所有List没什么最佳的解决方案，这就是你永远无法达到的Java 8中的效率，如，作为一个interface方法，爪哇8的default方法可以由任何List实施提供了量身定制的实现覆盖那个特定的类。

如果要在Java 8之前执行类似功能的合理实现，则必须重点关注常见的个案。几乎没有JRE提供的列表remove(int)工作，但Iterator.remove不。但考虑到ArrayList是最常用的可变List实现，对于该实现，基于迭代器的解决方案对于大型列表和大量已移除项目的性能会很差。这是因为无论您是使用remove(int)还是Iterator.remove，每次删除操作都会将所有后续项目移动一个位置，然后才能继续，并且可能会再次移除项目。在最坏的情况下，有一个谓词匹配所有项目，这会强加二次复杂性。因此，它提供了这种情况下，一个更复杂的解决方案是非常重要的：

interface Predicate<T> { 
    boolean test(T object); 
} 
public static <T> boolean removeIf(List<T> list, Predicate<? super T> p) { 
    if(list instanceof RandomAccess) { 
     int num=list.size(); 
     BitSet bs=new BitSet(num); 
     for(int index=0; index<num; index++) { 
      if(p.test(list.get(index))) bs.set(index); 
     } 
     if(bs.isEmpty()) { 
      return false; 
     } 
     for(int dst=bs.nextSetBit(0), src=dst;; dst++, src++) { 
      src=bs.nextClearBit(src); 
      if(src==num) { 
       list.subList(dst, src).clear(); 
       break; 
      } 
      list.set(dst, list.get(src)); 
     } 
     return true; 
    } 
    else { 
     boolean changed=false; 
     for(Iterator<T> it=list.iterator(); it.hasNext();) { 
      if(p.test(it.next())) { 
       it.remove(); 
       changed=true; 
      } 
     } 
     return changed; 
    } 
}

在列表中的情况下实现RandomAccess，其中包括所有ArrayList的风格的实现，该解决方案将模仿类似于Java 8的ArrayList.removeIf实现的东西，虽然我们不”我可以直接访问内部阵列，并省去了所有失败 - 快速并发修改检测的东西。现在，对于ArrayList类型的列表，它将具有线性复杂性，因此它将具有LinkedList，因为它不实现RandomAccess，因此将使用其Iterator进行处理。

该方法还履行Java 8的removeIf合同返回列表是否已被操作更改的方法。

CopyOnWriteArrayList是个例外，但对于一个写入时复制清单的想法就地removeIf是没有实际意义，除非列表本身提供的，如，通过执行它时，它的remove(int)（或任何其他public）操作，我们正在有效地复制每个更改的整个列表。因此，在这种情况下，将整个列表复制到普通列表中，在该列表上执行removeIf并将其复制回来将在大多数情况下更有效。

来源

2016-03-15 21:16:51 Holger

注意，'CopyOnWriteArrayList'允许'remove（int）'，但不允许从迭代器中移除remove（）。起初有点令人吃惊，但是当你考虑COWAL的迭代器语义是超过*快照*时是明智的，所以任何突变都会在陈旧的副本上进行。 –

@Stuart Marks：很好的提示。如果'CopyOnWriteArrayList'操作失败，可能会更好*但是由于它实现了'RandomAccess'，它可以工作，性能低于最优并且没有并发更新保护...... – Holger

Filters和Predicate s是Java8类型，所以如果你不想使用Java8，你需要类似的东西。

你可以伪造与过滤的包裹Iterator并使其与对象（类似于Prediates可以如何实现）的工作;然而，还有其他问题：

您声明该列表非常大，解决方案的内存影响应该是O(1)，但如果不知道该列表正在被操作，则无法保证这种事情。在实现中，remove(int)运算符可以分配新的列表索引并将其复制到其中。

假设名单确实没有这样的东西，你能做的最好的是实现自己的迭代器，需要一个谓语像测试，或者写一个特定的循环来处理列表。

在任何情况下，这听起来像一个面试问题。这里有一个例子

public interface MyPredicate<T> { 
    public boolean isTrue(T value); 
} 

public void removeOnTrue(List<T> list, MyPredicate<T> predicate) { 
    Iterator<T> iterator = list.iterator(); 
    while (iterator.hasNext()) { 
     T next = iterator.next(); 
     if (predicate.isTrue(next)) { 
     iterator.remove(); 
     } 
    } 
}

用做横跨指数环是差不多的，除非你将不得不跟踪的指数（和使用索引中删除）。

要使用上面的例子：

... 
List<String> names = ...; 
removeOnTrue(names, new MyPredicate<String>() { 
    public boolean isTrue(String value) { 
    return value.startsWith("A"); 
    } 
}); 
...

将产生一个与names所有字符串开始以 “A” 中删除。

来源

2016-03-14 20:52:14

如何遍历List并不重要，重要的部分是将测试包装在Object中。遵循'Comparator'建立的模式，但不是返回一个'int'来显示顺序，而是返回一个'boolean'来显示包含在集合中。 –

在没有外部库的情况下过滤Java列表

回答

相关问题