- About Scala
- In the Enterprise
- Scala Community
- Language Research
- In the Press
- The Scala Team
- Scala's Prehistory
- Contact Us
- Learning Scala
- Tour of Scala
- Scala API
- Setup & Getting Started
- Programming Guides
- Other Guides
- Code Examples
- Scala Developers
Set invariance and performance
Mon, 2011-11-28, 22:56
I read in a previous discussion that Set[T] is invariant so that it
can implement Function1[T,Boolean], and that this is likely to stay
this way due to compatibility issues.
I currently have a situation where I could really use covariant sets.
Currently, when I have a set of some trait B extends A, and want to
convert it into a set of trait A, I do Set.empty[A] ++ setOfB. But
that is very inefficient and ugly.
Would it be safe to say setOfB.asInstanceOf[Set[A]] instead, and could
I somehow define an implicit method to do this automatically so that I
don't have to sprinkle my code with asInstanceOf?
besides, there are quite a few things that I think could be improved
about the current set implementation without too much work:
val large=(1 to 1000).toSet
val small=(1 to 10).toSet
large.intersect(small) is significantly slower than
small.intersect(large). Is there a reason intersect doesn't check the
size of both arguments and does the intersection in the right order?
large.union(small) is significantly faster than small.union(large). In
the extreme case large.union(empty) returns the first argument, while
empty.union(large) rebuilds the complete set from scratch!
I understand that you can not order by size in the generic case,
because the type of the returned collection depends on the type of the
first argument. But in case of union and intersection you know that
both sides are of the same type, so you could do the size check.