Leistung der Funktion splitAt auf einem Vektor

Question

Die meisten Operationen auf einem vector sind wegen seiner trie Darstellung effektiv konstant. Ich kann jedoch nicht herausfinden, was das Leistungsprofil der Implementierung splitAt ist.

Es in der Bibliothek definiert als:

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

Die take Funktion hat die folgende Definition:

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

Und die dropBack0 hat folgende 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 
    } 

Wie Sie können sehen, dropBack0 macht einige hübsche co komplizierte Operation.

Hat splitAt effektiv konstante Leistung oder ist es schlechter? Es scheint effektiv konstant zu sein.

Answer 1

Es ist effektiv konstant. Vektor ist ein Baum mit Verzweigungsfaktor 32. take und drop Operationen werden in o durchgeführt (Protokoll N * 32). Da die Höhe des Baumes nicht mehr als 5 betragen kann, beträgt die Anzahl der Operationen für take, drop oder update im schlimmsten Fall 5 * 32 = 160.

Answer 2

Ja, wenn Sie jede in dropBack0 aufgerufene Methode befolgen, benötigen alle eine konstante oder effektiv konstante Zeit (maximale Array-Größe 32).