OCaml은 표준 라이브러리에서 배열과 리스트를 제공하지만 가변 길이 배열(벡터)은 제공하지 않는다. 그래서 OCaml 연습도 할 겸 가변 길이 배열을 만드는 Vec 모듈을 만들어보기로 하였다.
먼저 레코드를 이용해 'a vec 타입을 만든다. 레코드에는 데이터 data와 벡터의 길이 length를 저장한다. 벡터 특성상 length의 길이는 실제로 Array에 할당된 크기(capacity)보다 작을 수 있는데, 이는 Array.length 함수를 호출하면 가져올 수 있으므로 capacity를 따로 저장할 필요는 없다.
type 'a vec = {
mutable data : 'a Array.t;
mutable length : int;
}
모듈이 하나의 타입을 구현하므로 관습에 맞게 type 'a t를 작성해 준다. (이게 있어야 펑터에 이 모듈을 인자로 전달할 수 있는 경우가 있다)
type 'a t = 'a vec
기본적인 함수들, 즉 make, is_empty, get, 등등을 구현해 준다.
let make : int -> 'a -> 'a vec
= fun n elem -> {
data = Array.make n elem;
length = n;
}
let is_empty : 'a vec -> bool
= fun self -> self.length = 0
let get : 'a vec -> int -> 'a
= fun self idx -> Array.get self.data idx
push 함수를 구현해 본다. push 함수는 length가 capacity보다 작을 경우(공간이 남는 경우) 남는 공간에 push할 인자를 할당하고, length = capacity일 경우 더 큰 array를 할당해 그 array에 기존에 있던 원소를 모두 옮긴 뒤 새롭게 생긴 공간에 push할 인자를 할당한다. 나는 만약 새롭게 array를 할당할 일이 있을 경우 그 크기가 항상 2의 거듭제곱이 되도록 설정했다. 크기가 어떤 값 x의 거듭제곱이어야 항상 push 연산의 시간복잡도가 amortized O(1)이 되기 때문이다. 2보다 작은 수를 써도 되지만, 메모리가 남아돈다면 그냥 2를 써도 된다.
일단 새롭게 array를 할당해야 할 경우 그 크기가 얼마나 되는지 결정하는 함수를 작성한다.
let next_alloc_size : int -> int
= fun size_now ->
let rec f : int -> int -> int
= fun n cont -> if n < cont then cont else f n (cont * 2)
in
f size_now 1
이제 push를 구현할 수 있다. capacity가 꽉 차 새로운 공간을 할당해야 하는지 물어보는 함수 is_full도 작성한다.
let is_full : 'a vec -> bool
= fun self -> self.length = Array.length self.data
let push : 'a vec -> 'a -> unit
= fun self elem ->
let () = if is_full self then
let new_length = next_alloc_size self.length in
let aux = Array.make (new_length - self.length) elem in
self.data <- Array.append self.data aux
else
self.data.(self.length) <- elem
in
self.length <- self.length + 1
pop 함수는 push보다 쉽다. 리턴 값이 pop한 값이었으면 좋겠는데, 빈 벡터에 pop을 하면 아무것도 나오지 않는 경우가 생기므로 함수의 타입을 'a vec -> 'a option으로 잡아 준다.
let pop : 'a vec -> 'a option
= fun self ->
if is_empty self then
None
else
let () = self.length <- self.length - 1 in
Some self.data.(self.length)
댓글