在沒有外部庫的情況下過濾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列表

回答

相關問題