1

From the javadoc of List.scala:

 Time: List has O(1) prepend and head/tail access. Most other operations are `O(n)` on the number of elements in the list.
 *  **This includes the index-based lookup of elements**, `length`, `append` and `reverse`.

This compares (unfavorably) with ArrayList in java. (Yes I realize it is mutable and List is not .. but giving up that performance is a non-starter).

So then what is a likely /preferred "go-to" immutable List implementation in Scala with O(1) for index based lookup (and preferably for length as well). It is understandable/accepted that append and reverse are O(n)

Update Om-nom-nom nominated Vector and I concur (awaiting his making a real answer on this).

From the javadoc on Vector:

Vector is a general-purpose, immutable data structure. It provides random access and updates in effectively constant time, as well as very fast append and prepend. Because vectors strike a good balance between fast random selections and fast random functional updates, they are currently the default implementation of immutable indexed sequences.

WestCoastProjects
  • 58,982
  • 91
  • 316
  • 560

2 Answers2

5

For immutable structures, you probably want a Vector; it is pretty slow with direct access compared to an array, but it is close to O(1) for lookup and repeated appends or prepends. (Mixed appends/prepends confound it, however.)

ArrayBuffer is mutable and is basically the same data structure as java.util.ArrayList except with all the Scala collections goodies on top. (Map, etc..)

If you like the stack-like properties of lists, ArrayStack has push/pop and indexing where the top element on the stack is 0 (ArrayStack is also mutable).

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407
  • Hi, I upvoted this. om-nom-nom had already pointed this to be the right direction - but in a comment only. So he kind of got there first: but he has not posted a real answer yet. I'm not sure who should get the award for the answer. – WestCoastProjects Apr 09 '14 at 23:01
  • @javadba - Certainly fair to mark his answer as the correct one if he posts. I just wanted to add information about some alternatives (and give a little more info about `Vector` itself). – Rex Kerr Apr 09 '14 at 23:12
  • I am going to go ahead and award this. i will upvote his answer whenever (if) it arrives. – WestCoastProjects Apr 09 '14 at 23:20
  • @javadba - You can always switch which answer is best at a later date. – Rex Kerr Apr 09 '14 at 23:24
3

Just use an Array. That is O(1) for lookup.

What's an ArrayList in Java? It's just an array that adheres to the List contract. If Java Collections were being designed today, they'd probably make Array a class rather than a language feature, like Scala does.

So in Scala we can use an Array like we use any other type of Seq, eg List or Vector.

sksamuel
  • 16,154
  • 8
  • 60
  • 108
  • Thx. In which cases do you recommend to use List as opposed to Array? One of my concerns on using e.g. ListBuffer is that mutability is discouraged rather strongly in Scala. So using an Array as a go-to solution would seem to be frowned upon idiom-wise .. ? – WestCoastProjects Apr 09 '14 at 22:33
  • 2
    JFYI: http://stackoverflow.com/q/6928327/298389 (for Vectors lookups are not O(1), but practically are close to this value and they inherit good traits from both sides -- fast appends and fast lookups) – om-nom-nom Apr 09 '14 at 22:36
  • @om-nom-nom Vector is just what i was looking for. Please make a separate answer and I will award it. – WestCoastProjects Apr 09 '14 at 22:54
  • @om-nom-nom I went ahead and upvoted your comment, but awarded a similar - but somewhat expanded - answer by Rex kerr – WestCoastProjects Apr 09 '14 at 23:23
  • @javadba nevermind :-) happy that I got you into the right direction – om-nom-nom Apr 10 '14 at 11:01
  • I'm actually the only person who answered the question :) Vector is not O(1) even though its close enough for practical purposes. – sksamuel Apr 10 '14 at 11:51
  • @monkjack - What order is `ArrayBuffer` and `ArrayStack`? – Rex Kerr Apr 10 '14 at 12:29
  • Mutable. I was only joking anyway, shesh. – sksamuel Apr 10 '14 at 12:34