Running splitAt on a vector

Question

Most vector operations are actually persistent due to the trie view. However, I cannot figure out which performance profile the splitAt implementation splitAt .

It is defined in the library as:

 override /*IterableLike*/ def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) 

The take function has the following definition:

  override def take(n: Int): Vector[A] = { if (n <= 0) Vector.empty else if (startIndex + n < endIndex) dropBack0(startIndex + n) else this } 

And dropBack0 has the following definition:

  private def dropBack0(cutIndex: Int): Vector[A] = { val blockIndex = (cutIndex - 1) & ~31 val xor = startIndex ^ (cutIndex - 1) val d = requiredDepth(xor) val shift = (startIndex & ~((1 << (5*d))-1)) val s = new Vector(startIndex-shift, cutIndex-shift, blockIndex-shift) s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) s.preClean(d) s.cleanRightEdge(cutIndex-shift) s } 

As you can see, dropBack0 performs a rather complicated operation.

Does splitAt effective consistent performance or worse? It seems to be almost constant.

Answer 1

He is effectively permanent. A vector is a tree with a branching coefficient of 32. The take and drop operations are performed in o (log ₃₂ N * 32). Since the height of the tree cannot be greater than 5, the number of operations for take , drop or update in the worst case will be 5 * 32 = 160.

Answer 2

Yes, if you follow each method named in dropBack0 , all of them require constant or effective constant time (maximum array size 32).