CODEWITHSUNDEEP
arraysscalacollections
ayvango
ayvango

Reputation: 5977

How to obtain nested WrappedArray

I need read-only structure with fast indexed access and minimum overhead. That structure would be queried quite often by the application. So, as it was supposed on the net, I tried to use Arrays and cast them to IndexedSeq

scala> val wa : IndexedSeq[Int] = Array(1,2,3)
wa: IndexedSeq[Int] = WrappedArray(1, 2, 3)

So far, so good. But I need to use nested Arrays and there the problem lies.

 val wa2d : IndexedSeq[IndexedSeq[Int]] = Array(Array(1,2), Array(3), Array())
<console>:8: error: type mismatch;
found   : Array[Array[_ <: Int]]
required: IndexedSeq[IndexedSeq[Int]]
       val wa2d : IndexedSeq[IndexedSeq[Int]] = Array(Array(1,2), Array(3), Array())

Scala compiler could not apply implicit conversion recursively.

scala> val wa2d : IndexedSeq[IndexedSeq[Int]] = Array(Array[Int](1,2) : IndexedSeq[Int], Array[Int](3) : IndexedSeq[Int], Array[Int]() : IndexedSeq[Int])
wa2d: IndexedSeq[IndexedSeq[Int]] = WrappedArray(WrappedArray(1, 2), WrappedArray(3), WrappedArray())

That worked as expected, but this form is too verbose, for each subarray I need to specify types twice. And I would like to avoid it completely. So I've tried another approach

scala> val wa2d : IndexedSeq[IndexedSeq[Int]] = Array(Array(1,2), Array(3), Array()).map(_.to[IndexedSeq])
wa2d: IndexedSeq[IndexedSeq[Int]] = ArraySeq(Vector(1, 2), Vector(3), Vector())

But all WrappedArrays mysteriously disappeared and was replaced with ArraySeq and Vector.

So what is the less obscure way to define nested WrappedArrays ?

Upvotes: 1

Views: 577

Answers (1)

R&#252;diger Klaehn
R&#252;diger Klaehn

Reputation: 12555

Here is how you do it:

scala> def wrap[T](a: Array[Array[T]]): IndexedSeq[IndexedSeq[T]] = { val x = a.map(x => x: IndexedSeq[T]); x }
scala> wrap(Array(Array(1,2), Array(3,4)))
res13: IndexedSeq[IndexedSeq[Int]] = WrappedArray(WrappedArray(1, 2), WrappedArray(3, 4))

If you want to use implicit conversions, use this:

def wrap[T](a: Array[Array[T]]): IndexedSeq[IndexedSeq[T]] = { val x = a.map(x => x: IndexedSeq[T]); x }
implicit def nestedArrayIsNestedIndexedSeq[T](x: Array[Array[T]]): IndexedSeq[IndexedSeq[T]] = wrap(x)
val x: IndexedSeq[IndexedSeq[Int]] = Array(Array(1,2),Array(3,4))

And here is why you might not want to do it:

val th = ichi.bench.Thyme.warmed()
val a = (0 until 100).toArray
val b = a: IndexedSeq[Int]
def sumArray(a: Array[Int]): Int = { var i = 0; var sum = 0; while(i < a.length) { sum += a(i); i += 1 }; sum }
def sumIndexedSeq(a: IndexedSeq[Int]): Int = { var i = 0; var sum = 0; while(i < a.length) { sum += a(i); i += 1 }; sum }
scala> th.pbenchOff("")(sumArray(a))(sumIndexedSeq(b))
Benchmark comparison (in 439.6 ms)
Significantly different (p ~= 0)
  Time ratio:    3.18875   95% CI 3.06446 - 3.31303   (n=30)
    First     65.12 ns   95% CI 62.69 ns - 67.54 ns
    Second    207.6 ns   95% CI 205.2 ns - 210.1 ns
res15: Int = 4950

The bottom line is that once you access your Array[Int] indirectly via WrappedArray[Int], primitives get boxed. So things get much slower. If you really need the full performance of arrays, you have to use them directly. And if you don't, just use a Vector and stop worrying about it.

I would just go with Vector for prototyping and then go to Array once/if you are sure that this is actually a performance bottleneck. Use a type alias so you can quickly switch from Vector to Array.

Somewhere in your package object:

type Vec[T] = Vector[T]
val Vec = Vector
// type Vec[T] = Array[T]
// val Vec = Array

Then you can write code like this

val grid = Vec(Vec(1,2), Vec(3,4))

and switch quickly to an array version in case you measure that this is actually a performance bottleneck.

Upvotes: 1

Related Questions