Seq for fast random access and fast growth in Scala

5
votes

What would be the best Scala collection (in 2.8+), mutable or immutable, for the following scenario:

  • Sequentially ordered, so I can access items by position (a Seq)
  • Need to insert items frequently, so the collection must be able to grow without too much penalty
  • Random access, frequently need to remove and insert items at arbitrary indexes in the collection

Currently I seem to be getting good performance with the mutable ArrayBuffer, but is there anything better? Is there an immutable alternative that would do as well? Thanks in advance.

3
scalascala-collections
You might want to go thru this excellent collection API documentation by Martin Odersky and Lex Spoon: lampwww.epfl.ch/~odersky/whatsnew/collections-api/… – missingfaktor
Thanks - I had missed that one somehow. – Johan Nystrom

3 Answers

4
votes

Mutable: ArrayBuffer
Immutable: Vector

4
votes

If you insert items at random positions more than log(N)/N of the time that you access them, then you should probably use immutable.TreeSet as all operations are O(log(N)). If you mostly do accesses or add to the (far) end, ArrayBuffer and Vector work well.

2
votes

Vector. IndSeq from scalaz should be even better.