[scala] Vector

Java의 Vector와 달리 Scala의 Vector의 오퍼레이션은 거의 상수 시간대의 성능이 나올 정도로 훌륭하다. (정확히 말하면 효율적 상수 시간이다)

http://docs.scala-lang.org/overviews/collections/performance-characteristics.html

	head	tail	apply	update	prepend	append	insert

Vector

eC

eC

eC

eC

eC

eC

-

Vector는 Immutable 컬렉션이고, 트라이(https://en.wikipedia.org/wiki/Trie)라 부르는 순서가 있는 트리 데이터 구조로 구현되어 있다. 트라이에서, 키는 Vector에 저장된 값의 인덱스이다.

Vector의 구현은 패리티(parity) 32의 트리 구조이다. 각 노드는 32개의 배열로 구현되고, 

자식 노드 참조를 32개까지 저장하거나, 32개까지 값을 저장할 수 있다. 

* 주석을 보면, 다음과 같이 설명되어 있다. 

It is backed by a little
*  endian bit-mapped vector trie with a branching factor of 32.

32진 트리 구조는 Vector의 복잡도가 왜 "상수 시간" 대신 "효율적 상수 시간"인지 설명한다. Vector의 실제 복잡도는  log(32, N)이며, N은 벡터의 크기를 말한다. 이는 사실 상 상수 시간과 매우 근접하다고 말할 수 있다. 

Vector는 메모리가 32개의 엘리먼트 청크(chunk)로 할당되기 때문에 매우 큰 순서 집합을 저장하기에 좋은 선택이다. 

해당 청크는 트리의 모든 레벨로 미리 할당하지 않으며 필요할 때마다 할당된다.

간단한 테스트 코드이다.

val vectorEmpty = scala.collection.immutable.Vector.empty
val v = vectorEmpty :+ 1 :+ 2 :+ 3
println(v)
println(v(2))

결과는 다음과 같다.

Vector(1, 2, 3)

3

val is = collection.immutable.IndexedSeq(1, 2, 3)
// scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)
val v2 = is :+ 4 :+ 5
println(v2)
println(v2(4))

결과는 다음과 같다.

Vector(1, 2, 3, 4, 5)

5

Vector의 2번째 엘리먼트를 구하는 함수는 다음과 같이 개발할 수 있다. 

def returnSecondElement[A](vector: Vector[A]): Option[A] = vector match {
  case _ +: x +: _ => Some(x)
  case _ => None
}
println(returnSecondElement(v))

결과는 Some(2)이다.

좀 더 내용을 살펴본다.

:+의 구현은 다음과 같다. 커리된 함수와 암시가 쓰였다. 

override def :+[B >: A, That](elem: B)
              (implicit bf: CanBuildFrom[Vector[A], B, That]): That =
  if (isDefaultCBF(bf))
    appendBack(elem).asInstanceOf[That] 
  else super.:+(elem)(bf)

appendBack 함수를 들어가보면, 32진 트리 구조임을 드러나는 코드(31 and 연산)이 나온다. 

또한 Vector를 새로 만들어서 리턴하고 있음을 보여준다. Vector는 Immutable이다. 

  private[immutable] def appendBack[B>:A](value: B): Vector[B] = {
//    //println("------- append " + value)
//    debug()
    if (endIndex != startIndex) {
      val blockIndex = endIndex & ~31
      val lo = endIndex & 31

      if (endIndex != blockIndex) {
        //println("will make writable block (from "+focus+") at: " + blockIndex)
        val s = new Vector(startIndex, endIndex + 1, blockIndex)
        s.initFrom(this)
        s.dirty = dirty
        s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
        s.display0(lo) = value.asInstanceOf[AnyRef]
        s
      }
....