diff options
author | Paul Phillips <paulp@improving.org> | 2012-10-29 17:17:43 -0700 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2012-11-01 05:04:53 -0700 |
commit | 8a537b7d7da03833946a6a2f4461da2080363c88 (patch) | |
tree | 50d2a05eb55cd8b7f8f56f09260ddebf55f16f8f | |
parent | e660b58f795a9ad7825398b5831e4011b652cffb (diff) | |
download | scala-8a537b7d7da03833946a6a2f4461da2080363c88.tar.gz scala-8a537b7d7da03833946a6a2f4461da2080363c88.tar.bz2 scala-8a537b7d7da03833946a6a2f4461da2080363c88.zip |
Fix SI-6584, Stream#distinct uses too much memory.
Nesting recursive calls in Stream is always a dicey business.
-rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 13 | ||||
-rw-r--r-- | test/files/run/t6584.check | 8 | ||||
-rw-r--r-- | test/files/run/t6584.scala | 16 |
3 files changed, 34 insertions, 3 deletions
diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 461a375317..78c4d76eda 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. diff --git a/test/files/run/t6584.check b/test/files/run/t6584.check new file mode 100644 index 0000000000..35c8688751 --- /dev/null +++ b/test/files/run/t6584.check @@ -0,0 +1,8 @@ +Array: 102400 +Vector: 102400 +List: 102400 +Stream: 102400 +Array: 102400 +Vector: 102400 +List: 102400 +Stream: 102400 diff --git a/test/files/run/t6584.scala b/test/files/run/t6584.scala new file mode 100644 index 0000000000..24c236ef35 --- /dev/null +++ b/test/files/run/t6584.scala @@ -0,0 +1,16 @@ +object Test { + def main(args: Array[String]): Unit = { + val size = 100 * 1024 + val doubled = (1 to size) ++ (1 to size) + + println("Array: " + Array.tabulate(size)(x => x).distinct.size) + println("Vector: " + Vector.tabulate(size)(x => x).distinct.size) + println("List: " + List.tabulate(size)(x => x).distinct.size) + println("Stream: " + Stream.tabulate(size)(x => x).distinct.size) + + println("Array: " + doubled.toArray.distinct.size) + println("Vector: " + doubled.toVector.distinct.size) + println("List: " + doubled.toList.distinct.size) + println("Stream: " + doubled.toStream.distinct.size) + } +} |