diff options
author | Paul Phillips <paulp@improving.org> | 2010-04-23 21:20:14 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2010-04-23 21:20:14 +0000 |
commit | eb1ee924dd922db2e967c8a38ec13410eeb7110f (patch) | |
tree | c47f0b34931797ebf271d41b0e13ec9d42e6032c /src/library/scala/collection/mutable/GrowingBuilder.scala | |
parent | db8bd90da4c78e543bad65dea5600febc6fbbd20 (diff) | |
download | scala-eb1ee924dd922db2e967c8a38ec13410eeb7110f.tar.gz scala-eb1ee924dd922db2e967c8a38ec13410eeb7110f.tar.bz2 scala-eb1ee924dd922db2e967c8a38ec13410eeb7110f.zip |
Created Mutable and Immutable SetFactories to d...
Created Mutable and Immutable SetFactories to deal with the spectacular
performance regression which accompanies the use of AddingBuilder on
mutable Sets. Because '+' now creates a new collection even on mutable
sets, AddingBuilder on a 100K element collection will create garbage
sets of size 1,2,3...,99,999 before finishing. Thankfully there is
already GrowingBuilder.
See test/files/run/adding-growing-set.scala for a demonstration.
This patch is not complete: in particular, SortedSet and SetBuilder need
attention. Unfortunately there is a combinatorial jump in the number of
Addable/Growable divisions which arises once one tries to accomodate
both Sorted signatures (taking an Ordering) and unsorted signatures, so
will come back to it after receiving counsel.
Review by odersky.
Diffstat (limited to 'src/library/scala/collection/mutable/GrowingBuilder.scala')
-rw-r--r-- | src/library/scala/collection/mutable/GrowingBuilder.scala | 5 |
1 files changed, 5 insertions, 0 deletions
diff --git a/src/library/scala/collection/mutable/GrowingBuilder.scala b/src/library/scala/collection/mutable/GrowingBuilder.scala index cd1c8bec8c..781753c24d 100644 --- a/src/library/scala/collection/mutable/GrowingBuilder.scala +++ b/src/library/scala/collection/mutable/GrowingBuilder.scala @@ -18,6 +18,11 @@ import generic._ * interacting surprisingly with any2stringadd thus driving '+' out of the `Seq` * hierarchy. The tendrils of original sin should never be underestimated. * + * Addendum: of even greater significance is that '+' on mutable collections now + * creates a new collection. This means using AddingBuilder on them will create + * a new intermediate collection for every element given to the builder, taking + * '+' from an O(1) to O(n) operation. + * * @author Paul Phillips * @version 2.8 * @since 2.8 |