4장 이터레이터
이 장에서는 개미 수열을 이터레이터로 접근해 본다. 왜 갑자기 이터레이터를 이야기하는지 배경부터 살펴보자.
개미 수열의 특성
먼저 개미 수열의 100번 줄을 출력해 보자. 지금까지 만들어본 Java 프로그램으로 100번 줄을 출력하고자 하면 한참 시간이 지나 아래의 결과를 보게 된다.
JavaScript라고 다를 것은 없다. 고작 100번 줄을 출력하는데 메모리가 모자란다. 반면 1장에서 보여준 Haskell 프로그램은 100번 줄을 문제없이 출력한다. 3장에서 개미 수열을 리스트 처리 관점으로 구현하면서 Haskell과 거의 동등한 모양을 갖추긴 했지만 동작에 있어서는 큰 차이가 있음을 알 수 있다.
개미 수열은 각 줄이 약 30%씩 길어지는 특성이 있다.1 따라서 100번 줄의 길이는 666,450,031,706이며, 숫자 하나를 1바이트로 보아도 100번 줄만을 위해 약 600G 이상의 메모리가 필요하다. 당연히 메모리가 모자랄 수 밖에 없다.2
개미 수열 한 줄 전체를 문자열이나 리스트에 담을 수 없다면 리스트를 나타내는 새로운 방법을 써야 한다. 대표적인 방법이 이터레이터다.
이터레이터와 이터러블
이터레이터(iterator)는 이미 오래전부터 많은 언어들이 기본으로 제공하는 기능이다. 이터레이터는 리스트나 트리처럼 값을 저장하고 있지는 않지만, 이들 자료 구조의 값을 순차적으로 참조할 수 있는 일관된 방법을 제공한다. 이터레이터를 제공하는 컬렉션은 이터러블(iterable)이라 한다.
- JavaScript의 이터러블/이터레이터 프로토콜
- 이터러블 객체는
Symbol.iterator키에 이터레이터를 반환하는 함수를 가진다. JavaScript 이터레이터는next()메쏘드를 가지는데, 호출할 때마다 값을 반환하거나 종료 여부를 알린다. - Java의
Iterable/Iterator인터페이스 -
Iterable인터페이스는iterator()메쏘드가 있어서, 이를 통해 이터레이터를 생성한다.Iterator인터페이스는hasNext()로 종료 여부를 판단하고,next()로 값을 얻어온다.
JavaScript 이터레이터의 next() 메쏘드는 Java의 Iterator 인터페이스에 있는 두 개의 메쏘드를 합쳐놓은 것이다. JavaScript와 Java는 각각 for 문에서 이터러블을 순회할 수 있도록 문법적으로 지원한다.
일반적으로 이터러블을 컬렉션, 그리고 이터레이터는 컬렉션을 순회하기 위한 인터페이스라고 봐도 되지만, 항상 그렇지만은 않다. 이터레이터는 무언가를 순차적으로 하나씩 살펴보기 위한 범용적인 인터페이스일 뿐이다. 예를 들어, Java에서 입력 스트림의 텍스트 처리를 위한 Scanner 클래스는 Iterator를 구현하고 있다. Scanner를 이용하기 위해서 사용자의 입력을 모두 기다리거나 메모리에 올려둘 필요가 없다.
개미 수열과 이터레이터
개미 수열 문제에서 핵심이 되는 것은 다음 줄을 계산하는 next() 함수가 구현하는 로직이다. 1장의 for 루프 구현을 보면 앞 줄에서 한 글자씩 읽으면서 다음 줄을 만들어 낸다.
개미 수열 49번 줄의 길이는 약 90만이고 다음 줄인 50번 줄의 길이는 110만을 넘는다. 50번 줄의 첫 숫자를 계산하려면 49번 줄에서 몇 글자만 알면 될까? 단지 첫 네 숫자만 알면 된다. 49번 줄은 “1113…” 으로 시작하는데, 3을 읽으면 50번 줄이 “31…” 으로 시작하는 것을 알 수 있다.
마찬가지로 50번 줄의 100번째 숫자를 계산하는 경우를 보자. 49번 줄의 70번째 위치의 “…32112…” 부분에서 가운데 “11”로 결정되는 “21”이 50번 줄의 100번째 숫자가 된다. 즉, 75번째 숫자까지만 읽으면 벌써 100번째 숫자까지 계산이 된다. 비슷하게 49번 줄의 75번째 숫자 2를 계산하려면 48번 줄에서는 53개의 숫자까지 계산하면 된다.
이렇게 50번 줄을 계산하기 위해 길이가 90만이 넘는 49번 줄 전체를 참조하지 않는다. 다만 순차적으로 하나씩만 참조할 수 있으면 된다. 그리고 이미 읽고 처리한 값들을 따로 저장해 둘 필요도 없다.
개미 수열은 이터레이터를 이용하기 딱 좋은 경우다. 입력으로 한 줄 전체가 아니라 이터레이터를 받아도 되며, 물론 다음 줄도 이터레이터로 전달하면 된다. 50번째 줄의 이터레이터를 순회할 때, 그 이전 줄들의 이터레이터도 함께 진행되며, 각 이터레이터는 마치 커서처럼 해당 줄의 데이터를 다음 이터레이터로 하나씩 전달한다.
JavaScript #1 - 이터레이터
이제 JavaScript 이터레이터를 이용하여 개미 수열을 구현해 보자.
개미 수열의 각 줄을 이터레이터로 나타내면, 개미 수열의 다음 줄을 계산하는 next() 함수는 이터레이터(앞 줄)를 입력으로 받아서 새로운 이터레이터(다음 줄)를 만들어야 한다. next()를 곧바로 구현할 수도 있겠지만3 3장의 추상화를 재사용할 수도 있다.
ant()와 next() (JavaScript)function ant(n) {
let s = iter([1]);
for (let i = 0; i < n; i++) {
s = next(s);
}
return s;
}
function next(ns) {
return concat(map(g => iter([g.length, g[0]]), group(ns)));
}
사실 앞의 코드는 3장의 리스트 처리 버전과 거의 똑같다. 어차피 문제의 본질은 바뀌지 않았고 데이터 표현만 리스트나 배열이 아닌 이터레이터로 바뀐 것이다.
이제 이터레이터에 대해 동작하는 group(), map(), concat()을 만들면 된다. 세 함수는 모두 이터레이터를 입력으로 받아서 새로운 이터레이터를 만들어 반환한다. JavaScript에서 이터레이터를 생성하는 함수는 아래와 같은 기본 뼈대를 가진다.4
function makeIterator() {
return { // iterator object
next() {
return { done: true }; // or {done: false, value: ...}
}
}
}
리스트 처리에서 구현했던 것보다 조금 더 어려울 것이다. 가장 쉬운 map()부터 하나씩 살펴보자.
이터레이터 map()
map()은 변환 함수와 이터레이터를 인자로 받아서 새로운 이터레이터를 반환한다. 입력 이터레이터가 종료될 때 출력 이터레이터도 종료되고 값도 일대일 매칭되기 때문에 어렵지 않다.
map() 함수 (JavaScript)function map(f, it) {
return {
next() {
let { value, done } = it.next();
if (done) {
return { done: true };
} else {
return { done: false, value: f(value) };
}
}
};
}
이터레이터 concat()
concat()은 중첩된 이터레이터(이터레이터의 요소가 다시 이터레이터)를 순환하므로 종료가 조금 까다롭다.
concat() 함수 (JavaScript)function concat(it) {
let inner = null;
return {
next() {
while (true) {
if (inner === null) {
let { value, done } = it.next();
if (done) {
return { done: true }; // no more iterators
} else {
inner = value;
}
}
let { value, done } = inner.next();
if (done) {
inner = null;
} else {
return { done: false, value };
}
}
}
};
}
입력 이터레이터 it에서 꺼낸 내부 이터레이터를 순환하여야 하므로 상태로서 저장해둬야 한다. 내부 이터레이터 inner가 종료된 경우에는 곧바로 다음 이터레이터를 꺼낼 수 있어야 하므로 루프도 필요하다.
이터레이터 group()
group()이 반환하는 이터레이터는 next()가 호출될 때마다 입력 이터레이터를 1~n번 진행한다. 그런데 동일한 요소들을 묶은 그룹을 하나 반환하려면 반환하는 그룹에 포함되지 않는 요소를 하나 더 읽은 상태가 되며, 이 상태 때문에 구현이 까다롭다.
group() 함수 (JavaScript)function group(it) {
let g = null;
return {
next() {
while (true) {
let { value, done } = it.next();
if (done && g === null) {
return { done: true };
} else if (done) {
let result = g;
g = null;
return { done: false, value: result };
} else if (g === null) {
g = [value];
} else if (g[0] === value) {
g.push(value);
} else {
let result = g;
g = [value];
return { done: false, value: result };
}
}
}
};
}
입력 이터레이터가 종료된 경우라도 이미 읽은 값이 있는 경우와 그렇지 않은 경우(처음부터 빈 이터레이터)를 고려해야 한다.
이터레이터 도움 함수 iter()와 uniter()
대개는 직접 이터레이터를 사용하기 보다는 컬렉션(이터러블)을 사용한다. 우리는 이터레이터를 바로 사용하므로 이터러블을 요구하는 다른 코드들(예를 들어 for)과 매끄럽게 연결되지 않는 문제가 있다. 이런 문제는 iter()와 uniter()같은 도움 함수로 해결할 수 있다. iter()는 이터러블을 이터레이터로 바꿔주고, uniter()는 이터레이터로부터 이터러블을 만들어준다.
function iter(obj) {
return obj[Symbol.iterator]();
}
function uniter(it) {
return {
[Symbol.iterator]: function() {
return it;
}
};
}
이제 아래의 코드로 개미 수열의 100번 줄을 출력해 볼 수 있다.
for (let a of uniter(ant(100))) {
process.stdout.write(`${a}`);
}
메모리 문제없이 잘 출력되는지 직접 확인해 보자. :-)
11131221131211132221232112111312111213111213211231132132211211131221232112111312
21121311121312211213211321322112311311222113311213212322211211131221131211221321
123113213221121113122113121113222112131112131221121321131211132221121321...
지연 리스트로서의 이터레이터
한 번에 모두 담을 수 없는, 사실상 무한의 길이를 가진 리스트를 이터레이터로 표현하였다. 이러한 리스트를 지연 리스트라고 한다5. 이터레이터는 지연 리스트 혹은 무한 리스트의 일종이다. 이터레이터의 next() 메쏘드를 호출할 때까지 리스트의 꼬리 부분 계산은 지연된다.
일반적인 리스트와 구분하기 위하여 지연 리스트를 스트림(stream)이라고 부르는 경우도 있다. Java 8의 Stream 역시 무한대를 표현할 수 있는데, 그 밑에는 바로 이터레이터가 깔려있다.
이터레이터 구현 리뷰
이터레이터를 지연 리스트로 사용함으로써 개미 수열의 100번 줄을 출력할 수 있었다. 하지만 구현이 복잡하다. 게다가 이미 확인해 본 사람도 있겠지만, n을 1,000 혹은 10,000 이상으로 늘려보면 더 이상 동작하지 않는다.
먼저 이터레이터 구현이 복잡한 이유부터 살펴보자. 지연 리스트의 다음 값을 하나 계산하여 반환하기만 하면되는데 왜 복잡한 것일까? 이유는 이터레이터가 루프의 제어권을 가지고 있지 않다는 점이다. 이터레이터는 값을 생성하는 로직과 루프를 분리하였다. 값을 생성하는 로직이 단순하여 루프를 반복할 때마다 값을 하나씩만 생성하는 경우(예, map())는 이터레이터를 만드는 것도 간단하다. 해당 루프의 몸체만 추출하면 된다. 매우 자연스럽다. 하지만 요소 값을 생성(혹은 접근)하는 로직이 선형적이지 않은 경우에는 이터레이터가 자체적으로 상태 정보를 관리해야 한다. 예를 들어 이 장에서 구현한 concat()이나 group()을 보면, 각각 상태 정보를 가진다. next() 호출 시 다음 값을 계산하려면 마지막 상태를 따지거나 추가적인 루프가 필요하다. 트리나 그래프 자료 구조에 대한 이터레이터 구현이 복잡한 이유도 마찬가지다. 애초에 이터레이터 인터페이스가 나오게 된 이유가 이러한 복잡성을 감추고 단순한 인터페이스를 노출하기 위한 것이다.
이터레이터 구현이 복잡해지는 문제는 빈번하게 발생하기 때문에 언어 차원에서 좀더 쉬운 방법을 제공하기도 한다. 제너레이터(generator)가 그것이다. 5장에서 제너레이터를 살펴볼 것이다.
n이 커질 때 드러나는 한계는 조금 더 근원적인 것이다. 이 문제를 해결하기 위한 방법은 6장 코루틴부터 다룬다.