루티시 어레이 스택

*루티시 어레이 스택(Rootish Array Stack)*은 가우스의 합산 기법을 기반으로 공간 낭비를 최소화한 정렬된 배열 기반 구조다. 루티시 어레이 스택은 크기가 점점 커지는 여러 고정 크기 배열을 담고 있는 배열로 구성된다.

크기 조정이 가능한 배열은 블록(고정 크기 배열)에 대한 참조를 보관한다. 블록의 용량은 크기 조정 가능한 배열에서의 인덱스와 동일하다. 블록은 일반적인 Swift 배열처럼 크기가 늘어나거나 줄어들지 않는다. 대신 블록의 용량에 도달하면 약간 더 큰 블록이 새로 생성된다. 블록이 비워지면 마지막 블록이 해제된다. 이는 Swift 배열의 공간 낭비 문제를 크게 개선한 방식이다.

여기서 삽입/삭제 작업이 어떻게 동작하는지 확인할 수 있다. 이는 Swift 배열이 이러한 작업을 처리하는 방식과 매우 유사하다.

가우스의 합계 계산법

유명한 수학자 카를 프리드리히 가우스에 관한 가장 잘 알려진 일화 중 하나는 그가 초등학교에 다닐 때로 거슬러 올라간다. 어느 날, 가우스의 선생님은 학생들에게 1부터 100까지의 모든 숫자를 더하라는 문제를 내며, 이 작업이 시간이 오래 걸릴 것이라 생각하고 잠시 자리를 비웠다. 그러나 선생님은 어린 가우스가 금방 5050이라는 답을 들고 손을 드는 것을 보고 깜짝 놀랐다. 어떻게 이렇게 빨리 답을 찾았을까? 선생님은 가우스가 속임수를 쓴 것이 아닌지 의심했지만, 사실은 아니었다. 가우스는 모든 숫자를 하나씩 더하는 문제를 우회할 수 있는 공식을 발견한 것이었다. 그 공식은 다음과 같다:

1부터 n까지의 합 = n * (n + 1) / 2

이 공식을 이해하기 위해 n개의 블록을 상상해보자. 여기서 x는 1 단위를 나타낸다. 예를 들어 n을 5로 설정해보자:

블록:     [x] [x x] [x x x] [x x x x] [x x x x x]
x의 개수:  1    2      3        4          5

첫 번째 블록은 1개의 x, 두 번째 블록은 2개의 x, 세 번째 블록은 3개의 x를 가지고 있다.

만약 1부터 n까지의 모든 블록의 합을 구하고 싶다면, 하나씩 세어가며 더할 수 있다. 이 방법도 괜찮지만, 블록의 개수가 많아지면 시간이 오래 걸릴 수 있다! 대신, 블록을 반쪽 피라미드 형태로 배열할 수 있다:

# |  블록
--|-------------
1 |  x
2 |  x x
3 |  x x x
4 |  x x x x
5 |  x x x x x

그런 다음 이 _반쪽 피라미드_를 거울에 비추듯 뒤집고, 원래의 _반쪽 피라미드_와 합쳐 직사각형 모양을 만들 수 있다:

x                  o      x o o o o o
x x              o o      x x o o o o
x x x          o o o  =>  x x x o o o
x x x x      o o o o      x x x x o o
x x x x x  o o o o o      x x x x x o

여기서 n개의 행과 n + 1개의 열이 생긴다. 5개의 행과 6개의 열.

이제 면적을 계산하듯이 합계를 구할 수 있다! 너비와 높이를 n으로 표현해보자:

직사각형의 면적 = 높이 * 너비 = n * (n + 1)

우리는 x의 개수만을 계산하고 싶으므로, o의 개수는 제외해야 한다. x와 o의 비율이 1:1이므로 면적을 2로 나누면 된다!

x만의 면적 = n * (n + 1) / 2

이제 블록의 합계를 매우 빠르게 계산할 수 있다! 이 공식은 빠른 블록 및 내부 블록 인덱스 계산식을 유도하는 데 유용하다.

빠른 접근과 설정

다음으로, 무작위 인덱스에 있는 엘리먼트에 효율적이고 정확하게 접근하는 방법을 찾아본다. 예를 들어, rootishArrayStack[12]는 어떤 블록을 가리킬까? 이를 해결하려면 수학적 접근이 필요하다.

내부 블록 index를 구하는 것은 상대적으로 쉽다. 만약 index가 어떤 block 안에 있다면:

내부 블록 index = index - block * (block + 1) / 2

그러나 어떤 block을 가리키는지 알아내는 것은 더 복잡하다. 요청된 엘리먼트까지 포함한 전체 엘리먼트 수는 index + 1이다. 블록 0...block까지의 엘리먼트 수는 (block + 1) * (block + 2) / 2이다 (위에서 도출한 공식). block과 index 사이의 관계는 다음과 같다:

(block + 1) * (block + 2) / 2 >= index + 1

이를 다시 쓰면:

(block)^2 + (3 * block) - (2 * index) >= 0

이차 방정식 공식을 사용하면:

block = (-3 ± √(9 + 8 * index)) / 2

음수 블록은 의미가 없으므로 양의 근을 사용한다. 일반적으로 이 해는 정수가 아니다. 그러나 원래 부등식으로 돌아가면, block => (-3 + √(9 + 8 * index)) / 2를 만족하는 가장 작은 블록을 찾아야 한다. 그리고 그 결과의 천장 값을 취한다:

block = ⌈(-3 + √(9 + 8 * index)) / 2⌉

이제 rootishArrayStack[12]가 무엇을 가리키는지 알아낼 수 있다! 먼저 12가 어떤 블록을 가리키는지 보자:

block = ⌈(-3 + √(9 + 8 * (12))) / 2⌉
block = ⌈(-3 + √105) / 2⌉
block = ⌈(-3 + (10.246950766)) / 2⌉
block = ⌈(7.246950766) / 2⌉
block = ⌈3.623475383⌉
block = 4

다음으로 12가 어떤 내부 블록 index를 가리키는지 확인해 보자:

내부 블록 index = (12) - (4) * ((4) + 1) / 2
내부 블록 index = (12) - (4) * (5) / 2
내부 블록 index = (12) - 10
내부 블록 index = 2

따라서 rootishArrayStack[12]는 4번 블록의 2번 내부 블록 index를 가리킨다.

흥미로운 발견

block 방정식을 사용하면, blocks의 수가 엘리먼트 수의 제곱근에 비례한다는 것을 알 수 있다: O(blocks) = O(√n).

구현 세부사항

먼저 인스턴스 변수와 구조체 선언부터 살펴보자:

import Darwin

public struct RootishArrayStack<T> {

  fileprivate var blocks = [Array<T?>]()
  fileprivate var internalCount = 0

  public init() { }

  var count: Int {
    return internalCount
  }

  ...

}

여기서 엘리먼트는 제네릭 타입 T를 사용하므로, 어떤 종류의 데이터도 리스트에 저장할 수 있다. blocks는 크기를 조절할 수 있는 배열로, 고정 크기의 배열을 담는다. 이 고정 크기 배열은 T? 타입을 사용한다.
T? 타입을 사용하는 이유는 엘리먼트가 제거된 후에도 메모리에 남아있는 참조를 방지하기 위함이다. 예를 들어, 마지막 엘리먼트를 제거하면 마지막 인덱스를 nil로 설정해 접근할 수 없는 인덱스에 엘리먼트가 남아있지 않도록 해야 한다.

internalCount는 엘리먼트의 수를 추적하는 내부 가변 카운터다. count는 internalCount 값을 반환하는 읽기 전용 변수다. Darwin은 ceil()과 sqrt() 같은 간단한 수학 함수를 제공하기 위해 임포트했다.

이 구조체의 capacity는 가우스 합 공식을 사용한다:

var capacity: Int {
  return blocks.count * (blocks.count + 1) / 2
}

다음으로, 엘리먼트를 get하고 set하는 방법을 알아보자:

fileprivate func block(fromIndex: Int) -> Int {
  let block = Int(ceil((-3.0 + sqrt(9.0 + 8.0 * Double(index))) / 2))
  return block
}

fileprivate func innerBlockIndex(fromIndex index: Int, fromBlock block: Int) -> Int {
  return index - block * (block + 1) / 2
}

public subscript(index: Int) -> T {
  get {
    let block = self.block(fromIndex: index)
    let innerBlockIndex = self.innerBlockIndex(fromIndex: index, fromBlock: block)
    return blocks[block][innerBlockIndex]!
  }
  set(newValue) {
    let block = self.block(fromIndex: index)
    let innerBlockIndex = self.innerBlockIndex(fromIndex: index, fromBlock: block)
    blocks[block][innerBlockIndex] = newValue
  }
}

block(fromIndex:)와 innerBlockIndex(fromIndex:, fromBlock:)는 앞서 유도한 block과 inner block index 방정식을 감싸는 함수다. subscript를 사용하면 [index:] 구문으로 구조체에 get과 set 접근을 할 수 있다. get과 set 모두 동일한 로직을 사용한다:

인덱스가 가리키는 블록을 결정한다.
내부 블록 인덱스를 결정한다.
값을 get하거나 set한다.

다음으로, growIfNeeded()와 shrinkIfNeeded()를 살펴보자:

fileprivate mutating func growIfNeeded() {
  if capacity - blocks.count < count + 1 {
    let newArray = [T?](repeating: nil, count: blocks.count + 1)
    blocks.append(newArray)
  }
}

fileprivate mutating func shrinkIfNeeded() {
  if capacity + blocks.count >= count {
    while blocks.count > 0 && (blocks.count - 2) * (blocks.count - 1) / 2 >    count {
      blocks.remove(at: blocks.count - 1)
    }
  }
}

데이터 세트의 크기가 늘어나거나 줄어들면, 데이터 구조가 이를 수용할 수 있어야 한다. Swift 배열과 마찬가지로, 용량 임계값에 도달하면 구조체의 크기를 늘리거나 줄인다. Rootish Array Stack에서는 insert 연산 시 마지막에서 두 번째 블록이 가득 차면 grow하고, 마지막 두 블록이 비어 있으면 shrink한다.

이제 더 익숙한 Swift 배열 동작을 살펴보자:

public mutating func insert(element: T, atIndex index: Int) {
	growIfNeeded()
	internalCount += 1
	var i = count - 1
	while i > index {
		self[i] = self[i - 1]
		i -= 1
	}
	self[index] = element
}

public mutating func append(element: T) {
	insert(element: element, atIndex: count)
}

public mutating func remove(atIndex index: Int) -> T {
	let element = self[index]
	for i in index..<count - 1 {
		self[i] = self[i + 1]
	}
	internalCount -= 1
	makeNil(atIndex: count)
	shrinkIfNeeded()
	return element
}

fileprivate mutating func makeNil(atIndex index: Int) {
  let block = self.block(fromIndex: index)
  let innerBlockIndex = self.innerBlockIndex(fromIndex: index, fromBlock: block)
  blocks[block][innerBlockIndex] = nil
}

insert(element:, atIndex:)는 index 이후의 모든 엘리먼트를 오른쪽으로 한 칸씩 이동한다. 엘리먼트를 위한 공간을 만든 후, subscript 편의 메서드를 사용해 값을 설정한다.
append(element:)는 끝에 엘리먼트를 추가하는 편의 메서드다.
remove(atIndex:)는 index 이후의 모든 엘리먼트를 왼쪽으로 한 칸씩 이동한다. 제거된 값이 다음 값으로 덮인 후, 구조체의 마지막 값을 nil로 설정한다.
makeNil(atIndex:)는 subscript 메서드와 동일한 로직을 사용하지만, 특정 인덱스의 루트 옵셔널을 nil로 설정하는 데 사용한다. (옵셔널의 래핑된 값을 nil로 설정하는 것은 데이터 구조의 사용자만이 해야 할 일이다.)

옵셔널의 값을 nil로 설정하는 것과 래핑된 값을 nil로 설정하는 것은 다르다. 옵셔널의 래핑된 값은 옵셔널 참조 내에 포함된 타입이다. 이는 래핑된 값이 nil인 경우 실제로는 .some(.none)이며, 루트 참조를 nil로 설정하는 것은 .none이다. Swift 옵셔널을 더 잘 이해하려면 @SebastianBoldt의 글 Swift! Optionals?를 참고하는 것을 추천한다.

성능

내부 카운터가 구조체 내 엘리먼트의 개수를 추적한다. count는 O(1) 시간에 실행된다.
capacity는 가우스의 합산 트릭을 사용한 방정식으로 계산할 수 있으며, 이 방정식은 O(1) 시간에 실행된다.
subcript[index:]는 block과 inner block index 방정식을 사용하는데, 이 방정식들은 O(1) 시간에 실행되므로 모든 get 및 set 연산은 O(1) 시간이 걸린다.
grow와 shrink에 소요되는 시간을 무시하면, insert(atIndex:)와 remove(atIndex:) 연산은 지정된 인덱스 오른쪽의 모든 엘리먼트를 이동시키므로 O(n) 시간이 소요된다.

크기 조정(grow와 shrink)에 대한 분석

성능 분석에서는 grow와 shrink 작업의 비용을 고려하지 않았다. 일반적인 Swift 배열과 달리, grow와 shrink 작업은 모든 요소를 백업 배열에 복사하지 않는다. 대신, blocks의 수에 비례하는 배열만 할당하거나 해제한다. blocks의 수는 요소 개수의 제곱근에 비례한다. 따라서 크기 조정 작업은 **O(√n)**의 비용만 발생한다.

낭비되는 공간

낭비되는 공간이란 요소 개수 n에 대해 사용되지 않는 메모리 양을 의미한다. Rootish Array Stack은 절대 2개 이상의 빈 블록을 가지지 않으며, 항상 최소 1개의 빈 블록을 유지한다. 마지막 두 블록은 블록 개수에 비례하며, 블록 개수는 요소 개수의 제곱근에 비례한다. 각 블록을 가리키기 위해 필요한 참조 개수는 블록 개수와 동일하다. 따라서 요소 개수에 따른 낭비되는 공간의 양은 **O(√n)**이 된다.

Written for Swift Algorithm Club by @BenEmdon

With help from OpenDataStructures.org