Bir vektörde splitAt işlevinin performansı

Question

vector'daki çoğu işlem, trie gösterimi nedeniyle etkin olarak sabittir. Ancak, performans profilinin splitAt uygulamasının ne olduğunu anlayamıyorum.

Bu gibi kütüphane tanımlanır:

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

take fonksiyonu aşağıdaki tanımı var

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

ve dropBack0 aşağıdaki tanım var

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 görebilirsiniz dropBack0 bazı güzel co yapıyor yapıştırılmış ameliyat.

splitAt etkin bir şekilde sabit performansa sahip mi, yoksa daha mı kötü? Etkin olarak sabit gibi görünüyor.

Answer 1

Etkin olarak sabittir. Vektör, dallanma faktörü 32 olan bir ağaçtır. take ve drop işlemleri o içinde gerçekleştirilir (günlük N * 32). Ağacın yüksekliği 5'ten fazla olamaz, en kötü durumda take, drop veya update işlemlerinin sayısı 5 * 32 = 160 olur.

Answer 2

Evet, dropBack0 olarak adlandırılan her yöntemi izlerseniz, bunların tümü sabit veya etkili sabit (maksimum dizi boyutu 32) süresine gereksinim duyar.