1

For whatever reason there was no notion on that in Performance Characteristics Doc, so I dug into the sources and found out that List and Queue seem to have O(n), since they iterate thru all members. The Vector seems to have O(1), since it simply subtracts one Int from another.

Now, it doesn't matter whether the collection is append- or prepend-oriented, but either one of them must be O(1), and there's no need for performant apply.

Is Vector the correct choice? Which would you suggest?

om-nom-nom
  • 62,329
  • 13
  • 183
  • 228
Nikita Volkov
  • 42,792
  • 11
  • 94
  • 169
  • There are very few situations where a `List` is better than a `Vector`. Default to `Vector` unless you have a good reason not to. – Luigi Plinge Jul 25 '12 at 17:38
  • @LuigiPlinge Are you suggesting to use `Vector` as a default `Seq` implementation? This opinion seems at least unusual to me, because linked lists are all over the functional programming world and are the default collection type. Also `Vector`, being a more complex structure, must inevitably perform worse when used for `head`, `tail` and `prepend` operations. It must occupy more memory aswell. Could you please refer to any research / discussion / reading material on this? – Nikita Volkov Jul 25 '12 at 20:44
  • 1
    See also [this question](http://stackoverflow.com/questions/6928327/when-should-i-choose-vector-in-scala) – 0__ Jul 25 '12 at 23:30
  • Also interesting: [this question](http://stackoverflow.com/questions/6243232/scala-collection-memory-footprint-characteristics) showing that `Vector` has better memory footprint than `List`. There _was_ a discussion on one of the mailing lists about `Vector` as default type for `scala.Seq`, but I couldn't find it any more. – 0__ Jul 25 '12 at 23:39
  • @LuigiPlinge Thanks. The answers on the first link kinda prove that `List` is better when you know what you're doing (i.e. head, tail and prepend), the `Vector` while being just slightly slower on those operations is well optimized for most of the others and thus makes a better candidate for general type of collection. – Nikita Volkov Jul 26 '12 at 01:11
  • I'm glad @0__ found those links because they're what I was thinking of. I seem to have written an answer there lauding the virtues of `List`, but Daniel Spiewak knows a lot more about these things and I've come round to his view of favouring `Vector`. There's a good talk by him here: http://www.infoq.com/presentations/Functional-Data-Structures-in-Scala About the 26m mark he starts talking about hash tries, which is what Vector is, and why they're so efficient. – Luigi Plinge Jul 26 '12 at 02:01

1 Answers1

5

Is Vector the correct choice?

Yes. An alternative would be to create your own immutable wrapper around List, adding its size as constant, but it would be a lot of work if you want to allow all standard collection operations. Stick to Vector.

0__
  • 66,707
  • 21
  • 171
  • 266