Conversion between different implementations of Seq in Scala

Question

From what I have read, one should prefer to use generic Seq when defining sequences instead of specific implementations such as List or Vector.

Though I have parts of my code when a sequence will be used mostly for full traversal (mapping, filtering, etc) and some parts of my code where the same sequence will be used for indexing operations (indexOf, lastIndexWhere).

In the first case, I think it is better to use LinearSeq (implem is List) whereas in the second case it is better to use IndexedSeq (implem is Vector).

My question is: do I need to explicitly call the conversion method toList and toIndexedSeqin my code or is the conversion done under the hood in an intelligent manner ? If I use these conversions, is it a penalty for performance when going back and forth between IndexedSeq and LinearSeq ?

Thanks in advance

score 1 · Accepted Answer · edited May 23 '17 at 12:29

Vector will almost always out-perform List. Unless your algorithm uses only ::, head and tail, Vector will be faster than List. Using List is more of a conceptual question on your algorithm (data is stack-structured, only accessing head/tail, only adding elements by prepending, use of pattern matching (which can be used with Vector, just feels more natural to me to use it with List)).

You might want to look at Why should I use vector in scala

Now for some nice number to compare (obviously not a 'real' benchmark, but eh) :

val l = List.range(1,1000000)
val a = Vector.range(1,1000000)

import System.{currentTimeMillis=> milli}

val startList = milli
l.map(_*2).map(_+2).filter(_%2 == 0)
println(s"time for list map/filter operations : ${milli - startList}")

val startVector = milli
a.map(_*2).map(_+2).filter(_%2 == 0)
println(s"time for vector map/filter operations : ${milli - startVector}")

Output :

time for list map/filter operations : 1214  
time for vector map/filter operations : 364

Edit : Just realized this doesn't actually answer your question. As far as I know, you will have to call toList/toVector yourself. As for performances, it depends on your sequence, but unless you're going back and forth all the time, it shouldn't be a problem.

Once again, not a serious benchmark, but :

val startConvToList = milli
a.toList
println(s"time for conversion to List: ${milli - startConvToList}")

val startConvToVector = milli
l.toVector
println(s"time for conversion to Vector: ${milli - startConvToVector}")

Output :

time for conversion to List: 48
time for conversion to Vector: 18

These benchmarks are not really robust enough to go by. It's not hard to find cases where `List` outperforms `Vector`. For example, if they're objects already (no boxing) and the collection is only e.g. 22 long, `List` wins on a map by about 20%. `List` creates more garbage; depending on how impacted the GC is, it can either be almost free or pretty expensive. — Rex Kerr, Aug 28 '13 at 15:27

score 0 · Answer 2 · edited May 23 '17 at 12:05

I have done the same for indexOf and Vector is also more performant

val l = List.range(1,1000000)
val a = Vector.range(1,1000000)

import System.{currentTimeMillis=> milli}

val startList = milli
l.indexOf(500000)
println("time for list index operation : " + (milli - startList))

val startVector = milli
a.indexOf(500000)
println("time for vector index operation : " + (milli - startVector))

Output :

time for list index operation : 36
time for vector index operation : 33

So I guess I should use Vector all the times in internal implementations but I must use Seq when I build interface as specified here : Difference between a Seq and a List in Scala

Conversion between different implementations of Seq in Scala

2 Answers2