Prestazioni della funzione splitAt su un vettore

Question

La maggior parte delle operazioni su un vector sono effettivamente costanti a causa della sua rappresentazione trie. Tuttavia, non riesco a capire quale sia il profilo delle prestazioni dell'implementazione splitAt.

Essa è definita nella libreria come:

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

La funzione take ha la seguente definizione:

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

E il dropBack0 ha la seguente definizione:

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 
    } 

Come puoi vedere che dropBack0 sta facendo un bel lavoro chirurgia mplicata.

Il splitAt ha prestazioni costanti o è peggio? Sembra essere effettivamente costante.

Answer 1

È effettivamente costante. Il vettore è un albero con fattore di ramificazione 32. Le operazioni take e drop vengono eseguite in o (registro N * 32). Poiché l'altezza dell'albero non può essere superiore a 5, il numero di operazioni per take, drop o update nel caso peggiore sarà 5 * 32 = 160.

Answer 2

Sì, se si seguono tutti i metodi denominati in dropBack0, tutti richiedono un tempo costante o efficacemente costante (dimensione massima dell'array 32).