[스칼라] 컬렉션 자세히 보기

Programming in scala 4th edition 24장

 

1. 변경 가능, 변경 불가능 컬렉션

• 변경 가능: 컬렉션 원소의 추가/제거/변경이 가능함
• 변경 불가능: 메모리상 한 번 할당되면 그 내용을 수정할 수 없음

스칼라 컬렉션은 scala.collection 패키지에 존재한다. scala.collection은 immutable, mutable, generic 세 가지 하위 패키지를 갖는다.

• collection: mutable과 immutable에서 상속 받아 사용하도록 루트 컬렉션들을 지원
• mutable: 변경 가능한 컬렉션이 정의되어있음
• immutable: 변경 불가능한 컬렉션이 정의되어있음
• generic: 추상화용 구성 요소들이 정의되어있음

 

2. Iterable 트레이트

컬렉션 계층의 가장 꼭대기에는 Iterable[A] 트레이트가 있다. Iterable을 구현하려면 아래 메서드만 정의하면 된다.

def iterator: Iterator[A]

Iterable이 가지고 있는 구체 메서드는 아래와 같다.

• 이터레이션 연산: foreach, grouped, sliding같은 메서드

val numbers = List(1, 2, 3, 4, 5)

numbers.foreach(println)
val groupedNumbers = numbers.grouped(2)
groupedNumbers.next()
groupedNumbers.next()
groupedNumbers.next()

val slidingNumbers = numbers.sliding(3)
slidingNumbers.next()
slidingNumbers.next()
slidingNumbers.next()

• 추가 메서드: ++(concat)
• 맵 연산: map, flatMap, collect
• 변환 연산: toList, toIndexedSeq, toIterable, toMap, toSet emd
• 복사 연산: copyToArray
• 크기 연산: isEmpty, size, knownsize, sizeCompare, sizeIs
• 원소를 가져오는 연산: head, last, find
• 하위 컬렉션을 가져오는 연산: takeWhile, tail, init, slice, take
• 분할 연산: groupBy, groupMap, splitAt, span, partition
• 원소 테스트 메서드: exists, forall
• 폴드 연산: foldLeft, foldRight, rdeuceLeft
• 특정 폴드 메서드: sum, min, max, product는 숫자 타입 같은 곳에만 적용 가능함
• 문자열 연산: mkString, addString, 컬렉션을 문자열로 바꾸는 방식 제공
• 뷰 연산

Iterable의 하위 분류

Iterable 아래에는 Seq, Set, Map 세 가지 트레이트가 존재한다.

 

3. 시퀀스 트레이트: Seq, IndexedSeq, LinearSeq

시퀀스: 길이가 정해져 있음. 0부터 시작하는 고정 인덱스를 가짐

• 인덱스와 길이 연산: apply, isDefinedAt, length, indices, lengthCompare등. Seq의 apply는 인덱스로 원소를 읽는 기능을 한다. length는 size의 별명이다.
• 인덱스 찾기 연산: indexOf, lastIndexOf, indexOfSlice, lastIndexOfSlice 등
• 추가 연산: +: (prepended), ++: (prependedAll), :+ (appended), :++ (appendedAll)
• 변경 연산: updated, patch 일부 원소 변경
• 정렬 연산: sorted, sortWith, sortBy
• 반전 연산: reverse, reverseIterator
• 비교 연산: startsWith, endsWith, contains, corresponds
• 중복 집합 연산: intersect, diff, distinct, distinctBy 두 시퀀스에 대해 집합 연산을 수행

변경 가능한 Seq에서는 InPlace라는 글자를 포함하는 사용중인 메모리 안에서 변경할 수 있는 메서드를 제공한다. 아래는 예시이다.

val numbersBuffer = scala.collection.mutable.ListBuffer(1, 2, 3, 4, 5)

numbersBuffer.mapInPlace(_ * 10) // ListBuffer(10, 20, 30, 40, 50)

IndexedSeq, LinearSeq는 Seq의 서브 트레이트이다.

• LinearSeq: 효율적인 head, tail 연산 제공, List, LazyList
• IndexedSeq: 효율적인 apply, length, update 제공, Array, ArrayBuffer

 

버퍼

변경 가능한 시퀀스의 하위 범주이다. 원소를 추가하고 제거하는 동작을 지원하고 맨 뒤에 효율적으로 추가/제거를 할 수 있도록 해준다. ListBuffer, ArrayBuffer가 있고 각각 List, Array로 변경할 수 있다.

 

4. 집합(Set)

집합: 중복 없는 Iterable

• 검사: apply, contains, subsetOf와 같은 검사 연산을 제공한다. 집합의 apply는 원소가 존재하면 true 존재하지 않으면 false를 반환한다.

val numberSet = Set(1, 2, 3, 4, 5)
numberSet(1) // true
numberSet(10) // false

• 추가/제거: 추가 연산(+, ++), 제거 연산(-, --)

Set(1) + 2 // Set(1, 2)
Set(1) ++ Set(2, 3) // Set(1, 2, 3)

Set(1, 2, 3) -- Set(0, 1) // 1, 2, 3 중에서 1이 제거됨

• 집합 연산: 합집합, 교집합, 차집합 연산 제공

Set(1, 2) | Set(2, 3) // 합집합 Set(1, 2, 3)
Set(1, 2) union Set(2, 3) // 합집합 Set(1, 2, 3)

Set(1, 2) & Set(2, 3) // 교집합 Set(2)
Set(1, 2) intersect Set(2, 3) // 교집합 Set(2)

Set(1, 2) &~ Set(2, 3) // 차집합 Set(1)
Set(1, 2) diff Set(2, 3) // 차집합 Set(1)

 

5. 맵

맵: 키와 쌍을 가진 Iterable

• 검색 연산: apply, get, getOrElse, contains, isDefinedAt. 맵의 apply는 key를 받아 value를 리턴한다. get도 같은 기능을 하는데 apply는 타입 그대로 리턴하기 때문에 없는 키를 받으면 에러를 발생시킨다. get은 Some으로 감싸 리턴하기 때문에 없는 키를 받으면 None이 리턴된다.

val numberMap = Map("a" -> 1, "b" -> 2, "c" -> 3)

numberMap("a") // 1
numberMap get "b" // Some(2)

• 추가/변경/제거 연산: +(updated), ++(concat), updateWith, updatedWith으로 원소를 추가/변경할 수 있음. -(removed), --(removedAll)로 제거.

numberMap + ("d" -> 4) // Map(a -> 1, b -> 2, c -> 3, d -> 4)
numberMap.updatedWith("a")(x => Option[Int](x.get * 10)) // Map(a -> 10, b -> 2, c -> 3)

• 하위 컬렉션 생성 메서드: keys, keySet, keysIterator, valuesIterator, values는 키, 값을 다양한 형태로 반환한다.
• 변환 연산: filterKeys, mapValues는 기존 맵의 바인딩을 필터링하거나 변환한 새 맵을 만든다. 

맵을 이용해서 캐시로 사용할 때는 아래와 같이 getOrElseUpdate를 생성하여 사용하는것이 권장된다. getOrElseUpdate는 키와 함수를 하나 받게된다. 두번째 인자로 받는 함수는 이름에 의한 호출로 키가 없을때만 실행되는 형태이다.

import scala.collection.mutable.Map

def f(x: String) = {
  println("Time...")
  Thread.sleep(100)
  x.reverse
}

val cache = Map[String, String]();

def cachedF(s: String) = cache.getOrElseUpdate(s, f(s))

 

6. 변경 불가능한 구체 컬렉션 클래스

리스트

변경 불가능한 유한한 시퀀스. head, tail 접근은 상수 시간, 그 외 연산은 선형 시간이 소요됨.

 

LazyList

요청을 받았을 때만 원소를 계산하는 리스트. 갯수가 무한할 수도 있다. 원소를 추가하는 연산자는 #::을 사용한다. 다른 부분에서는 리스트와 동일하다.

val str = 1 #:: 2 #:: 3 #:: LazyList.empty

def fibFrom(a: Int, b: Int): LazyList[Int] =
  a #:: fibFrom(a, a + b) // def fibFrom(a: Int, b: Int): LazyList[Int]


val fibs = fibFrom(1, 1).take(7)
// val fibs: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>)

 

변경 불가능한 배열 시퀀스

시퀀스의 앞부분에서 동작이 주로 일어나면 리스트가 적합하지만 뒷쪽 원소 조작이 자주 발생하면 비효율적이다.

ArraySeq는 어느 위치에 있는 원소든 상수 시간에 접근할 수 있다. 하지만 맨 앞에 원소를 추가하는경우 선형 시간이 걸린다.

 

벡터

벡터는 List, ArraySeq의 비효율적인 경우들을 보완하는 구조이다. 임의의 원소에 접근할 때 사실상 상수 시간이 소요된다.

val vec = scala.collection.immutable.Vector.empty
val vec2 = vec :+ 1 :+ 2
vec2 // Vector(1, 2)

벡터는 넓고 얕은 트리로 표현된다. 각 트리의 노드는 32개이고 하나의 원소를 갖거나 또다른 트리를 갖는다. 벡터는 변경이 불가능하다.

immutable.IndexedSeq의 기본 구현은 벡터를 기반으로 한다.

 

변경 불가능한 큐

변경 불가능한 큐는 아래와 같이 사용할 수 있다. 

val immutableQueue = Queue[Int]() // EmptyQueue
val lengthOneQueue = immutableQueue enqueue 1 // Queue(1)
val (element, emptyQueue) = lengthOneQueue.dequeue // 1, EmptyQueue

 

범위

정수를 일정한 간격으로 나열한 시퀀스이다.

1 to 5 // 1 to 5
1 to 5 by 2 // 1 to 5 by 2

1 until 5 // 1 until 5

• to: a to b 에서 a부터 b까지를 포함하는 시퀀스
• until: a until b 에서 a 부터 b를 제외한 시퀀스

 

압축 해시 배열에 매핑한 접두사 트리(compressed hash-array mapped prefix tree)

immutable 집합이나 맵을 효율적으로 구현하는데에 사용되는 트리로 트라이 구조에서 원소의 해시값을 5비트씩 나누어 원소가 트라이 내에서 저장될 위치를 정하는 방식으로 구현되어있다.

 

적흑트리(red-black tree)

트리 노드를 검은색 빨간색으로 구분하여 구성한 valanced binary tree이다. TreeSet이나 TreeMap, SortedSet이 red-black tree로 구현되어있다.

 

변경 불가능한 BitSet

예를 들어서 3, 2, 0을 표현하는 비트 집합은 1101, 13으로 표현할 수 있다. 비트 집합은 64비트 Long 배열을 사용한다. 

val bits = BitSet.empty
val writtenBits = bits + 3 + 3 + 4
writtenBits // BitSet(3, 4)

 

벡터 맵

Vector, HashMap을 사용해 구현한 맵으로 삽입 순서대로 원소를 반환한다.

 

리스트 맵

리스트의 특성을 갖고 있는 맵. 첫 원소에 자주 접근할 경우 유리하다.

 

7. 변경 가능한 구체 컬렉션 클래스

배열 버퍼

배열 끝 추가가 효율적이며 대부분의 연산의 효율이 배열과 같다. 

val arrayBuffer =  new ArrayBuffer[Int]
arrayBuffer += 1
arrayBuffer += 2
arrayBuffer.toArray // Array(1, 2)

 

리스트 버퍼

val listBuffer =  new ListBuffer[Int]
listBuffer += 1
listBuffer += 2
listBuffer.toList // List(1, 2)

 

문자열 빌더

val stringBuilder = new StringBuilder
stringBuilder += 'a'
stringBuilder ++= "bcde"

stringBuilder.toString // "abcde"

 

배열 데크

ArrayDeque: 맨 앞과 맨 뒤에서 효율적으로 데이터를 추가할 수 있는 변경 가능한 시퀀스. 뒤쪽에 원소를 추가하는것만으로 충분하다면 Buffer를, 앞 뒤에서 동시에 추가하는 기능이 필요하다면 Deque를 사용한다.

 

큐

변경 가능한큐는 변경 불가능한 큐와 기능은 같지만 그 특성상 API 사용 예시가 조금 다르다.

val mutableQueue = new scala.collection.mutable.Queue[Int]()
mutableQueue += 1 // Queue(1)
mutableQueue += 2 // Queue(2)
mutableQueue ++= List(3, 4) // Queue(1, 2, 3, 4)
mutableQueue.dequeue // 1

 

스택

변경 가능한 스택은 후입 선출을 지원한다. List가 변경 불가능한 스택의 역할을 할 수 있으므로 변경 불가능한 스택은 별도로 제공되지 않는다.

val mutableStack = new mutable.Stack[Int]()
mutableStack.push(1) // Stack(1)
mutableStack.push(2) // Stack(1, 2)

mutableStack.pop() // 2
mutableStack.pop() // 1

 

해시 테이블

해시 테이블은 원소를 배열에 저장한다. 스칼라의 변경 가능 맵, 변경 가능 집합의 기본 구현은 해시 테이블을 기반으로 한다.

 

동시적 맵

여러 스레드에서 동시에 접근하는 경우 원자적 연산을 제공하는 동시적 맵을 사용할 수 있다.

val concurrentMap = new ConcurrentHashMap[String, Int]()
val trieMap = new TrieMap[String, Int]

 

8. 배열

스칼라 배열은 자바 배열과 두 가지 측면에서 차이가 있다.

• 제네릭할 수 있음. Array[T]를 만들 수 있음
• 스칼라 배열은 스칼라 시퀀스와 호환 가능함

먼저 스칼라 배열이 스칼라 시퀀스와 호환 가능한 것에 대한 설명이다.

val integerArray = Array(1, 2, 3, 4)
integerArray map (_ * 10)

배열이 시퀀스와 호환이 가능하므로 위와 같이 Iterable에서 사용하는 기능을 모두 활용할 수 있다. 스칼라는 배열을 Seq로 사용할 때마다 Seq의 서브타입으로 배열을 감싸준다.

// 배열은 아래의 ArraySeq로 감싸짐
// scala.collection.mutable.ArraySeq

val integerArray = Array(1, 2, 3, 4)
val integerArraySeq: mutable.ArraySeq[Int] = integerArray

integerArray == integerArraySeq.toArray // false 출력. 원래 배열과 다른 배열을 반환한다.

또 ArrayOps로 변경하는 암시적 변환이 있어 모든 시퀀스 메서드를 추가해 준다. 

val integerArrayOps: ArrayOps[Int] = integerArray

integerArray.reverse
integerArrayOps.reverse
intArrayOps(integerArray).reverse

위의 세 가지 reverse의 결과는 Array(4, 3, 2, 1)로 같다. Array에 Seq 메서드를 적용하면 intArrayOps와 같은 ArrayOps 타입으로의 암시적 변환이 발생하고 reverse가 수행된다. 기본적으로 ArrayOps 변환이 ArraySeq 변환보다 우선순위가 더 높다.

스칼라 배열이 제네릭하게 사용될 수 있는것에 대한 설명이다.

 기본적으로 Array[T]는 실행 시점에 구체적인 타입을 알 수 없기 때문에 AnyRef 타입의 배열로 선언해둔다. 이후 실행 시점에 Array[T]에 접근할 때마다 타입검사를 진행한다. 이 검사는 구체적인 타입이 지정된 배열보다 느리기 때문에 왠만하면 타입이 지정되어있는 배열을 우선적으로 사용하는 것이 좋다.

아래는 함수 내에서 제네릭 배열을 생성하는 예제이다. 

def evenElems[T](xs: Vector[T]): Array[T] = {
  val arr = new Array[T]((xs.length + 1) / 2) // 에러 발생
  for (i <- 0 until xs.length by 2)
    arr(i / 2) = xs(i)
  arr
}

스칼라는 실행 시점에 T에 대한 정보를 지워버리기 때문에 함수 본문에 new Array[T]는 에러를 발생시킨다. 따라서 개발자가 이 타입을 명시해주어야한다. scala.reflect.ClassTag 타입의 클래스 태그를 명시해서 소거된 타입을 알 수 있도록 해야한다. 

import scala.reflect.ClassTag
def evenElemsWithClassTag[T: ClassTag](xs: Vector[T]): Array[T] = {
  val arr = new Array[T]((xs.length + 1) / 2)
  for (i <- 0 until xs.length by 2)
    arr(i / 2) = xs(i)
  arr
}

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

T: ClassTag 를 명시해두면 스칼라 컴파일러는 T에 대한 클래스 태그를 자동으로 만들어서 evenElemsWithClassTag의 암시적 파라미터에 전달한다.

 

9. 문자열

문자열도 시퀀스 메서드를 자유롭게 쓸 수 있다. 문자열은 StringOps로의 암시적 변환, WrappedString으로의 암시적 변환을 사용한다. 

 

10. 동일성

컬렉션은 시퀀스, 셋, 맵으로 구분된다. 이 세 컬렉션에서 동일하다의 판단은 각 범주가 같고 원소가 같다면 동일하다고 한다.

List(1, 2, 3) == Vector(1, 2, 3) // List와 Vector는 동일범주, 원소도 같음 true
Set(1, 2, 3) == List(1, 2, 3)    // Set과 List는 범주가 다름 false

 

11. 뷰

변환기(transformer)는 map, filter와 같이 컬렉션을 이용해서 새로운 컬렉션을 만드는 메서드들을 말한다. 변환기에는 엄격한 변환기와 게으른 변환기가 있다. 기본적으로 스칼라의 변환기는 LazyList를 제외하고 엄격한 변환기이다.

• 엄격한 transformer: 새 컬렉션을 만들어 모든 원소를 다 집어넣는다.
• 게으른 transformer: 프록시만 만들어두고 요청이 있을때마다 원소를 만든다.

뷰는 모든 변환기를 게으른 변환기로 구현할 수 있도록 도와주는 특별한 컬렉션이다.

val v = Vector(1 to 10: _*)
v map (_ + 1) map (_ * 2) // Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

위의 예시에서 v는 1이 증가된 Vector를 만들고 2배를 한다. 문제는 1이 증가된 Vector가 쓸데없이 생성된다는 점과 1을 증가시키고 2배하는 연산을 한번에 진행할 수도 있다는 것이다. 

(v.view map (_ + 1) map (_ * 2)).to(Vector) // Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

val vv = v.view // IndexedSeqView(<not computed>)
val incresedVv = vv map (_ + 1) // IndexedSeqView(<not computed>)
val twicedVv = incresedVv map (_ * 2) // IndexedSeqView(<not computed>)
twicedVv.toVector // Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

 

12. 이터레이터

이터레이터는 컬렉션은 아니지만 컬렉션 원소를 하나씩 접근하도록 해주는 도구다.

val stringList = List("Apple", "Banana", "Can")
val it = stringList.iterator
while(it.hasNext) {
  println(it.next()) // Apple, Banana, Can을 개행을 붙여 출력함
}

map이나 foreach 같은 반복문, for표현식을 사용할 수도 있다. iterator에서 foreach를 수행하면 원소의 맨 끝으로 iterator를 옮긴다.

stringList.map(_.length).foreach(println) // Apple Banana Can을 개행을 붙여 출력

val it2 = stringList.iterator
it2.foreach(println) // Apple Banana Can을 개행을 붙여 출력
it2.hasNext // false

 

버퍼 이터레이터

이터레이터의 한가지 문제점은 it.next()로 원소를 확인한 뒤에 저장해두지않으면 다시 볼 수 없다는 것이다. 이를 위해서 버퍼 이터레이터를 제공하는데 버퍼 이터레이터는 it.head를 사용하면 이터레이터를 다음 차례로 보내지 않으면서 원소를 읽을 수 있다.

def skipEmptyWords(it: Iterator[String]): String = {
  while (it.next.isEmpty) {}
  it.next
}

skipEmptyWords(stringList.iterator) // Banana
// Apple을 건너 뛰어버림 next로 순회하기 때문에

def skipEmptyWords(it: BufferedIterator[String]): String = {
  while (it.head.isEmpty) {it.next()}
  it.head
}

skipEmptyWords(stringList.iterator.buffered) // Apple

 

13. 컬렉션 처음 만들기

컬렉션은 동반객체의 apply에 원소들을 받아 생성하는 메서드가 정의되어있다. 빈 컬렉션으 empty를 이용해 생성한다.

List(1, 2, 3)
Vector(1, 2, 3)
Map("a" -> 1, "b" -> 2)

fill, tabulate 같은 메서드로 고정 크기의 컬렉션을 생성할 수도 있다.

List.fill(2)(1)
List.tabulate(5)(x => x + 1)