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
} ....
'scala' 카테고리의 다른 글
| [scala] 다른 라이브러리를 포함시킬 수 있는 REPL 환경 (0) | 2016.10.31 |
|---|---|
| [scala] Array, WrappedArray (0) | 2016.10.29 |
| zeppelin 과 spark 연동 (0) | 2016.10.28 |
| [scala] Option 에러 처리 - 펌질.. (0) | 2016.10.26 |
| List에 적용하는 for yield 예시 2 (0) | 2016.10.24 |
