diff options
author | Paul Phillips <paulp@improving.org> | 2012-10-29 17:17:43 -0700 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2013-01-30 03:50:42 -0800 |
commit | 98534b2cf67efc3930de427bfd1916fcf315fa59 (patch) | |
tree | ebf80284366e4d4055466c84aa6fa4adbeee93db /src/library | |
parent | d2316df920ffa4804fe51e8f8780240c46efa982 (diff) | |
download | scala-98534b2cf67efc3930de427bfd1916fcf315fa59.tar.gz scala-98534b2cf67efc3930de427bfd1916fcf315fa59.tar.bz2 scala-98534b2cf67efc3930de427bfd1916fcf315fa59.zip |
SI-6584, Stream#distinct uses too much memory.
[backport]
Nesting recursive calls in Stream is always a dicey business.
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 13 |
1 files changed, 10 insertions, 3 deletions
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 1c461973e4..5bb4ef5f21 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -841,9 +841,16 @@ self => * // produces: "1, 2, 3, 4, 5, 6" * }}} */ - override def distinct: Stream[A] = - if (isEmpty) this - else cons(head, tail.filter(head != _).distinct) + override def distinct: Stream[A] = { + // This should use max memory proportional to N, whereas + // recursively calling distinct on the tail is N^2. + def loop(seen: Set[A], rest: Stream[A]): Stream[A] = { + if (rest.isEmpty) rest + else if (seen(rest.head)) loop(seen, rest.tail) + else cons(rest.head, loop(seen + rest.head, rest.tail)) + } + loop(Set(), this) + } /** Returns a new sequence of given length containing the elements of this * sequence followed by zero or more occurrences of given elements. |