Performance and usage comparison of different collection types

Question

I have been programming in Scala for a few months now. I'm still confused by the many different collections there are.

Is there a page/article somewhere that shows what each type is best suitable for?

The problem with Scala is that it has too many different types, then you have something like Array which maps directly to a Java array, then you have something like "Set" which is actually a "trait" but you can use it like a normal class even though my understanding is that a trait is like an interface. The documentation says "to implement a concrete set, you need to define the following methods: ..." but actually I can use it just fine.

The whole thing is really confusing to me. Coming from C#/.NET, things there were quite clear and I didn't have the odd types like "LinkedHashMap" and "LinkedHashSet".

Answer 1

Use the trait (interface) Seq (ordered list), Map (key value), Set, IndexedSeq, Array (for Java primitives) types and let the compiler choose the implementation. If you look at the source you will see a companion object for each. This uses a factory to find an implementation for you.

This page helped me. http://docs.scala-lang.org/overviews/collections/overview.html

The section on Concrete collections goes into the implementations.

Seq companion object:

object Seq extends SeqFactory[Seq] {
  /** $genericCanBuildFromInfo */
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A]
}

https://github.com/scala/scala/blob/v2.10.3/src/library/scala/collection/Seq.scala#L1

Look at the factory source to see how apply initializes the collection.

abstract class GenericCompanion[+CC[X] <: GenTraversable[X]] {
  /** The underlying collection type with unknown element type */
  type Coll = CC[_]

  /** The default builder for `$Coll` objects.
   *  @tparam A      the type of the ${coll}'s elements
   */
  def newBuilder[A]: Builder[A, CC[A]]

  /** An empty collection of type `$Coll[A]`
   *  @tparam A      the type of the ${coll}'s elements
   */
  def empty[A]: CC[A] = newBuilder[A].result

  /** Creates a $coll with the specified elements.
   *  @tparam A      the type of the ${coll}'s elements
   *  @param elems  the elements of the created $coll
   *  @return a new $coll with elements `elems`
   */
  def apply[A](elems: A*): CC[A] = {
    if (elems.isEmpty) empty[A]
    else {
      val b = newBuilder[A]
      b ++= elems
      b.result
    }
  }
}

https://github.com/scala/scala/blob/v2.10.3/src/library/scala/collection/generic/GenericCompanion.scala#L1

Update: I usually use Array for a mutable indexed collections type since it is easier to type, but Vector for immutable. The Scala style encourages using the immutable collections since making a new "copy" of an immutable data structure is performant because of the underlying implementation being done with Hash array mapped trie structures. http://en.wikipedia.org/wiki/Hash_array_mapped_trie

Answer 2

I have been programming in Scala for a few months now. I'm still confused by the many different collections there are.

You probably only need only some time to get used to things. Scala wouldn't be Scala, if it would look exactly like another language, right? :) Every programming language has its strengths and weaknesses.

Is there a page/article somewhere that shows what each type is best suitable for?

You actually need a general article about data structures. E.g. if you need to store data in a collection, and need to access them quickly, without the need to modify the collection, than an array is suitable. Arrays, lists, sets, maps etc. are data structures which basically behave the same way in every language. Differences are in terms of syntax.

The problem with Scala is that it has too many different types, then you have something like Array which maps directly to a Java array, then you have something like "Set" which is actually a "trait" but you can use it like a normal class even though my understanding is that a trait is like an interface. The documentation says "to implement a concrete set, you need to define the following methods: ..." but actually I can use it just fine.

You should look at the link @sam already posted: http://docs.scala-lang.org/overviews/collections/overview.html Here's another: http://twitter.github.io/scala_school/collections.html