트리구조를 순회하기
디자인패턴에서는 이터레이터패턴이나 비지터패턴, 컴포지트 패턴 등을 통해 노드의 길이가 제각각이며 동시에 상이한 그래프까지도 탐색할 수 있는 알고리즘을 제시합니다.
일반적으로 객체구조까지 도입하지 않는다면 간단한 재귀를 통해 구현할 수도 있습니다.
하지만 재귀로 구현하기엔 HTML의 DOM엘리먼트가 어디까지 자식을 갖을지 예상도 안되고 특히나 HTML은 그 특성상 매우 깊은 자식도 생성될 수 있으므로 스택오버플로우가 될 가능성이 매우 큽니다.
간단한 재귀구조에서 보다 동기적인 루프구현체와 대규모 DOM을 위한 비동기 순회까지 차근차근 알아보죠.
재귀로 구현하기
재귀 구현은 기본적으로 컴포지트 패턴과 같은 원리를 사용합니다.
리스트형태면 다시 분리해서 재귀하고 아니라면 처리하겠다
라는 정책이죠.
구현은 위의 말 그대로 작성하면 됩니다.
function tour( target, action ){
var i, j;
//리스트인 경우
if( target.length ){
//다시 재귀함
for( i = 0, j = target.length ; i < j ; i++ )
tour( target[i], action );
}else{
//엘리먼트마다 해야할 일
action( target );
//자식이 있다면 다시 재귀함
if( target.childNodes && target.childNodes.length ){
for( i = 0, j = target.childNodes.length ; i < j ; i++ )
tour( target.childNodes[i], action );
}
}
}
//사용하기
tour(
document.getElementsByTagName('div'),
function action(el){
console.log( el );
}
);
- 우선 받아온 target 이 리스트면 리스트를 순회하게 됩니다.
- 리스트가 아니라면 해야할 일(action:여기서는 그냥 콘솔에만 출력)을 하죠.
- 그 뒤엔 자식이 있는지 확인하여 자식노드를 다시 순회하게 됩니다.
DOM의 경우 텍스트 노드가 아닌 이상 전부 composite 인 셈이죠.
하지만 처음에 언급한대로 DOM은 매우 깊은 트리가 생성될 수 있습니다. 위의 알고리즘에서 문제가 되는 부분은 3번입니다. 1번의 리스트 순회는 병렬적이기 때문에 스택이 쌓여봐야 1단계지만 3번이 해소되기 위해서는 모든 자식 트리를 순회해야 합니다.
특히 해당 노드가 스택오버플로우까지 가지 않는다고 해도 이 함수를 어떤 함수 안에서 부르면 이미 스택이 쌓여있는 상태에서 시작되므로 더욱 위험하게 됩니다.
재귀의 원리
어째서 이런 문제는 재귀로 해결할 수 있는걸까요?
이는 함수의 호출이 메모리상 독립된 영역을 만들어낸다는 점으로 이해할 수 있습니다.
함수는 호출할 때마다 스택메모리공간을 생성하고 이 공간 내에서의 지역변수와 인자는 별도의 영역으로 보호받습니다. 따라서 함수를 여러번 호출해도 각 호출마다 독립된 메모리 공간에서 실행되는 거죠.
하지만 함수 호출을 처리하면서 그 내부에서 다른 함수를 호출하면 내부에서 호출한 함수가 완전히 처리되기 전에는 이전 함수의 메모리 공간도 해지할 수 없습니다.
이는 다음과 같은 코드로 이해할 수 있습니다.
function sum( a, b ){
return a + b;
}
function result( a, b, c ){
return sum( a, b ) * c;
}
console.log( result( 1, 2, 3 ) );
- 위의 코드에서 result를 호출하면
- result를 위한 독립된 메모리공간이 생성되고,
- 그 안에 a, b, c가 각각 1, 2, 3을 부여받습니다.
- 내부를 실행하다가 sum호출을 만나면 sum함수를 위한 메모리를 공간을 생성합니다.
- 이 sum의 독립메모리공간에는 a = 1, b = 2 가 들어가는데 이는 result의 메모리 공간과 별도입니다.
- sum함수 내부에서 1+2를 처리하여 반환하면 그 반환값에 result의 c값인 3을 곱하여 최종 결과를 반환합니다.
여기서 요점은 result 를 위한 메모리 공간은 sum 을 다 처리하기 전까지 해지할 수 없다 는 것입니다.
만약 미리 해지해버리면 6번에서 c의 3을 꺼낼 수 없겠죠 ^^;
이런 이유로 함수 내부에서 다른 함수를 호출하면 이전 함수의 메모리는 해지하지 못하고 쌓이게 됩니다.
메모리가 쌓이고 해지되는 과정이 자료구조의 스택과 흡사하여 스택메모리로 불리고 있습니다.
다시 앞 서 구현한 tour함수를 보면 함수 내부에서 tour함수를 계속 호출하기 때문에 더 이상 tour함수를 호출하지 않을때까지 메모리가 끊임없이 쌓이게 됩니다.
자바스크립트는 이러한 함수용 스택 메모리가 쌓이는 제한을 100개정도로 엄격하게 제한하고 있습니다.
사실 이는 자바스크립트 뿐만 아니라 기존의 자바나 c같은 언어도 과거에는 시스템의 메모리가 소진될때까지 받아주는 정책에서 어느정도에서 제약을 거는 모델로 변경되고 있습니다.
따라서 스택오버플로우가 일어나지 않게 함수내의 함수 호출을 자제하거나 우회해야합니다.
직접 스택을 구현하기
결국 재귀호출로 얻을 수 있는 것은 함수 호출시마다 생성되는 독립된 스택메모리입니다.
그렇다면 이러한 스택메모리를 자료구조로 옮겨 쌓아주거나 제거하는 것을 반복하는 루프문으로 변경할 수 있을 것입니다.
원리상 모든 재귀호출은 루프문으로 바꿀 수 있습니다.
변수이름을 처리하려면 오브젝트로 배열을 만들면 되겠지만 위의 예에서는 그저 리스트만 등장하므로 2차원 배열과 같은 형태면 충분하겠죠.
function tour( target, action ){
var stack, curr, i;
//최초 스택을 생성한다.
if( target.length ){ //리스트인 경우
stack = [target];
}else{
//리스트가 아니면 강제로 배열화시킴
stack = [[target]];
}
//스택을 해소할때까지 루프
while( curr = stack.pop() ){
//해당 스택의 길이만큼 루프
i = curr.length;
while( i-- ){
//개별 요소 action처리
action( curr[i] );
//자식이 있다면
if( curr[i].childNodes && curr[i].childNodes.length ){
//스택에 추가한다!
stack.push( curr[i].childNodes );
}
}
}
}
//사용하기
tour(
document.getElementsByTagName('div'),
function action(el){
console.log( el );
}
);
사용방법은 동일하지만 내부에서 tour 함수를 재귀적으로 호출하는 부분이 제거되었습니다. 이제 이 함수는 아무리 깊이 자식이 있어도 스택오버플로우를 일으키지 않게 되었습니다.
내부의 구조는 매우 간단합니다.
- stack이라는 배열에 처리해야할 리스트가 계속해서 추가되므로
- pop을 통해 마지막 요소를 제거해가는 큰 루프를 돌립니다.
- 내부에서 자식이 더 이상 존재하지 않아 스택에 추가하지 않게 되면
- 결국 pop해도 아무것도 없게 되므로 루프를 탈출하게 됩니다.
일반적으로 재귀적인 알고리즘을 반복문으로 변경하게 되면 2단 루프가 되는 경우가 많습니다. 스택층마다 배열이 되었든 오브젝트가 되었든 독립된 메모리 구조체를 만들어주기 때문에 스택루프에 개별 스택의 값에 대한 루프를 돌기 때문입니다.
하지만 문제는 여기서 끝나지 않습니다.
동기적 실행의 제한
위에서 구축한 방법으로는 분명 스택오버플로우에는 걸리지 않습니다.
하지만 반복문의 실행이 길어지면 cpu의 사용은 해당 알고리즘을 처리할때까지 빠져나오지 못하고 대기하게 됩니다.
(이는 동기적 실행의 특징으로 특정 문이 해소되지 않으면 다음 문을 처리할 수 없는 노이만 머신의 구조를 따르기 때문입니다)
게다가 자바스크립트는 싱글쓰레드의 특징으로 인해 문을 별도의 시분할쓰레드에 분산시킬 수도 없으므로, 어떤 문이 긴시간 cpu를 점유하게 되면 다른 모든 실행이 대기하게 됩니다.
이는 마치 브라우저가 정지된것처럼 보이므로, 브라우저측에서는 자바스크립트가 동기적 실행을 함에 있어 일정 시간이 지나면 자동으로 실행을 멈추고 에러로 처리하게 됩니다.
이를 동기적 실행에 대한 시간제한이라고 합니다.
브라우저의 자바스크립트 뿐만이 아니라, 현대의 OS는 보다 많은 제어권을 OS측이 갖기 때문에 동기실행에 대한 시간제약을 거는 것은 일반적인 사항이 되었습니다.
안드로이드나 iOS를 비롯한 모바일 OS는 물론이고 윈도우즈8의 app도 마찬가지 제약이 존재합니다.
단 이러한 플랫폼은 쓰레드를 지원하므로 긴 시간을 잡아먹는 동기실행을 별도 쓰레드에서 실행하게끔 강제합니다.
자바스크립트는 쓰레드가 없으므로(웹워커는 별도로 ^^) 보통 타이머를 통해 한번에 일정량으로 실행하도록 분산합니다.
만약 HTML이 충분히 크고 action에서는 하는 일이 무겁다면 위의 tour함수는 한번 실행시 10초도 넘게 걸릴 수 있습니다.
이러면 브라우저가 실행을 중단하고 에러처리가 되므로 그전에 나눠서 실행할 수 있도록 해야합니다.
하지만 한 번에 어느 정도가 적당한 걸까요? 가장 정확하게는 매번 루프를 돌때마다 시간의 경과를 측정하면 되지만 시간측정은 공짜가 아닙니다. 오히려 시간 측정을 하는 비용이 더 큰 편입니다.
따라서 100번에 한번정도 시간을 측정하게 시키면 될 듯합니다. 경과시간이 3초가 넘었다면(모바일브라우저의 제약은 5초이내임) 다음 타이밍에 나머지를 처리하게 하는거죠.
결과적으로 동기적이었던 tour함수는 비동기적으로 변화하게 되고 콜백함수를 통해 완료시점을 통보받게 될 것입니다.
비동기로 전환하기
위의 원리에 따라 기존 tour함수는 완료시 통보받을 콜백함수를 인자에 추가하게 되고, 내부적으로는 타이머관리를 하도록 변경합니다.
//콜백을 인자에 추가하고 이어받는 경우를 위한 isSeries추가
function tour( complete, target, action, isSeries ){
var stack, curr, i, start, timeCounter;
//최초 호출된 경우
if( !isSeries ){
//최초 스택을 생성-이전동일
stack = [target.length ? target : [target]];
}else{
// 이어받는 경우는 target이 stack임
stack = target;
}
//시작시간을 확인한다.
start = Date.now();
//시간확인용 카운터 초기화
timeCounter = 0;
while( curr = stack.pop() ){
i = curr.length;
while( i-- ){
action( curr[i] );
if( curr[i].childNodes && curr[i].childNodes.length ){
stack.push( curr[i].childNodes );
}
}
//카운터가 100이 될때마다 시간을 측정한다.
if( timeCounter++ == 100 ){
//3초가 경과되었다면
if( Date.now() - start > 3000 ){
//다음 프레임으로 넘긴다.
return setTimeout( function(){
//현재 스택을 target으로, isSeries를 true로
tour( complete, stack, action, true );
}, 1);
}
//카운터를 초기화
timeCounter = 0;
}
}
//만약 무사히 나왔다면 완료된것!
complete();
}
//사용하기
tour(
function complte(){
console.log( 'completed!');
},
document.getElementsByTagName('div'),
function action(el){
console.log( el );
}
);
코드를 리뷰해보죠.
- 우선 기존 함수와 다르게 complete가 인자로 추가되어 작업이 끝나면 비동기적으로 통보받게 됩니다.
- 내부적으로는 isSeries가 참인가 아닌가에 따라 모드가 변경되는데
- 최초 호출시에는 인자를 보내지 않으니 당연히 거짓이 되어 target으로부터 stack을 초기화하던 이전 구현을 따르게 됩니다.
- 하지만 isSeries가 참인 경우는 target을 stack으로 전환하여 사용하게 됩니다.
- 시작시간을 측정해둔뒤 루프에 돌입합니다
- 루프의 구조는 이전 구현과 완전히 동일합니다만 각 스택을 한층씩 해소할때마다 timeCounter를 증가시키게 되고
- 이 값이 100이 되면 현재 시간을 다시 측정하게 됩니다.
- 만약 시작시간과 현재 시간의 차이가 3초를 넘게 되면 현재의 스택을 target으로 하고 isSeries를 참으로 하여
- setTimeout을 통해 다음실행 프레임으로 넘겨버리게 됩니다.
- 다음 프레임에서는 tour함수가 나머지 stack의 바통을 이어받아 처리를 이어갑니다.
- 만약 중간 시간제한에 걸리지 않고 무사히 루프가 완료되었다면 모든 처리가 끝난 것이므로 완료콜백을 호출하고 종료됩니다.
사실 100번마다 측정하기엔 너무 자주라는 느낌이 입니다만 action함수가 어디까지 무거워질지 모르니까요.
결론
DOM엘리먼트 순회라는 건수(?)를 이용해서 재귀와 반복문, 동기와 비동기를 살펴봤습니다.
프로그래밍에서는 재귀를 반복으로 반복을 재귀로 바꾸는 일이 흔하게 일어납니다.
꼬리물기 최적화를 내장하고 있는 ES6에서는 재귀로 작성해도 상관없지만 스택메모리가 계속 쌓이기만 하는 ES5까지의 자바스크립트에서는 사실 무조건 반복문으로 구현해야 안전합니다.
이유는 스택오버플로우는 고작 100단계정도에서 멈추지만 반복문의 타임아웃제한은 그 수천배에 실행을 보장하기 때문입니다.
하지만 그것보다 더 방대해지는 경우는 비동기적으로 프레임별 실행횟수를 제한하는 정책을 병행해야합니다.
위의 비동기화 과정이 귀찮다면 인라인웹워커 패턴을 이용하는 것도 좋은 대안이 될 수 있습니다.
테스트페이지는 아래와 같습니다.
[notification type=”alert-info” close=”false” ]http://jsfiddle.net/t5j8py68/[/notification]
recent comment