スカラのストリームで最初の複製を見つける方法

Question

スカラのストリームで最初の複製を見つける方法はありますか？

私の現在のアイデアは、各要素をすべて前の要素のSetとペアにすることです。その後、Streamにfindが呼び出されます。

したがって、各要素について、我々はSetに

• 挿入を有する：O（1）Setで
• 試験contains：

したがって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 
    } 

もっと良い方法がありますか？

Answer 1

あなたの関数の末尾を再帰的にする必要があります。あなたが持っている方法では、ストリーム全体のもう一つのコピーをスタック上に作っています。また、私はストリーム全体のコピーを作成しているのか（なぜなら、セットの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の実装を変更するだけで済みます。