時間流過濾器

的複雜性我有這樣的代碼：時間流過濾器

List<Listing> Listings = new ArrayList<>(); 
Listings.add(listing1); 
Listings.add(listing2); 
... 
... 
... 

Listing listing= listings.stream() 
       .filter(l -> l.getVin() == 456) 
       .findFirst();

我的問題是什麼是過濾過程的時間複雜度？如果是O（n），我的直覺就是將它轉換爲HashSet，就像數據結構一樣，這樣時間複雜度可能變成O（1），是否有一種優雅的方式可以通過流與流？

來源

2017-08-14 zonyang

它可能是一個並行流，但複雜性仍然是O（n）。將它轉換爲一個過濾器操作的集合仍然是O（n），因此您需要首先使用集合。您可能想要使用LinkedHashset來保留插入順序，或使用TreeSet進行其他排序（列表意味着一些排序和/或允許重複）。 – Thomas

'Stream＃filter'總是遍歷完整的'Stream'並將過濾標準應用於**每個元素**。一個優點是流可以很容易地被並行化，但是它只是通過一個常數因子（物理內核的數量）來減少時間複雜度。 – Zabuza

它是O(n)。流過濾在內部使用迭代。

如下您可以將其轉換爲一個地圖：

Map<Integer, Listing > mapOfVinToListing = listings.stream().collect(Collectors.toMap(Listing::getVin, Functions.identity()); // Assuming vin is unique per listing 
mapOfVinToListing.get(456);// O(1)

但是，該轉換過程也爲O（n）。所以，如果你只需要做一次，使用過濾器。如果您需要多次查詢同一個列表，那麼將其轉換爲地圖可能有意義。

您也可以嘗試使用並行流。在某些情況下，它們可能更高效，但這取決於具體情況。

來源

2017-08-14 23:33:52 Adam

或者，如果可能，從頭開始直接使用索引'HashMap'來首先存儲元素。如果你需要經常做這樣的查詢，那麼索引列表是一個更好的解決方案，就像@Adam所說的那樣。 – Zabuza

@Zabuza好點。如果可以將集合創建爲HashMap，那肯定比轉換它好。 – Adam

最壞的情況是O(n)但由於Stream是懶惰的，如果之前找到該值，它將停止迭代。如果你需要不斷查找，那麼轉換爲Map是一個好主意，但需要額外的空間;如果名單如果巨大，你應該考慮這方面。實際上，如果列表很小，那麼Map和List之間的差異幾乎不會引起注意，除非您在時間關鍵型系統中工作。

來源

2017-08-15 01:33:50

filter本身沒有終端操作將具有零開銷 - 因爲它什麼也沒有;流僅由終端操作驅動 - 無終端操作，不會執行任何操作。

然後是該filter具有迭代在所有元件（可能所有）的源（懶惰）的的情況。因此，過濾器的時間複雜度將取決於您從中流出的來源;在你的情況List，所以它會是O(n)。

但是，這將是最壞情況。根據我所能看到的filter一般，你不能預測平均情況，因爲它取決於基礎源。

來源

2017-08-15 11:34:36 Eugene

時間流過濾器

回答

相關問題