如何在scala中查找流中的第一個副本

如何在scala中查找Stream中的第一個副本？如何在scala中查找流中的第一個副本

我目前的想法是將每個元素與以前所有元素的Set配對。之後，在產生的Stream上調用find。

因此，對於每個元素，我們有

插入在Set：O（1）
測試contains在Set：O（1）

因此，這個算法的整體複雜性似乎是O（n）。

def firstDuplicate[A](s: Stream[A]) = { 
    def recurse(s: Stream[A], set: Set[A]) : Stream[(A, Set[A])]= 
     (s.head, set) #:: recurse(s.tail, set + s.head) 
    val pairedWithElements = recurse(s, Set.empty) 
    pairedWithElements.find{ case (e, elems) => elems.contains(e)}.get._1 
    }

有沒有更好的方法？

來源

2016-12-31 Yann Moisan

你認爲這條河流有多大？更好的是，可以出現的元素有多種？ – Chobeat

這似乎是相當優化的方法，儘管對於大型或無限流，它將使用大量內存。您可以嘗試使用布盧姆過濾器而不是集合，但您需要多次瀏覽前n個元素，因爲它可能會返回誤報。 – adamwy

你應該讓你的函數尾遞歸。你擁有它的方式，你在堆棧上完成了整個流的另一個副本。另外，我不明白你爲什麼要製作整個流的副本（以及一個whoooole buuunch集），然後再次掃描它以找到dup。您可以立即將它添加到集合中，並立即停止。

像這樣的東西可能：以上

def firstDup[T](s: Stream[T], seen: Set[T] = Set.empty[T]): Option[T] = s match { 
     case head #:: tail if seen(head) => Some(head) 
     case head #:: tail => firstDup(tail, seen + head) 
     case _ => None 
    }

布隆過濾器中的建議從註釋是真正巨大輸入流是一個好主意。在這種情況下，「外殼」將保持不變，您只需更改底層的seen實現。

來源

2016-12-31 15:24:59 Dima

感謝您提供更簡單的解決方案。只有2個錯別字：s /＃：/＃::和s /空/空[T] –

第一個是一個錯字（現在修復）。另一個不是 - 那裏的類型參數是不必要的，可以推斷出來。 – Dima

沒有類型參數，當我調用方法時，我遇到了這個編譯錯誤：[error]注意：Nothing <：Pos，但是特徵Set在類型A中不變。 [錯誤]您可能希望調查通配符類型，例如'_ <：Pos'。（SLS 3.2.10） –

如何在scala中查找流中的第一個副本

回答

相關問題