자료구조(stack, queue, Maxheap)와 고차함수(forEach, filter, map)의 polyfill과 관련된 내용입니다.
글을 쓰게된 계기
모던 자바스크립트 DeepDive 책 27장을 보면 생성자함수, 클래스로 자료구조를 구현한 부분과 고차함수가 정확히 어떤식으로 작동하는 지 보여주기 위해 polyfill로 작성한 코드 부분이 있었습니다.
그 부분에는 자료구조에 stack과 queue, 고차함수 forEach polyfill 밖에 작성이 되어있지 않았는데 Maxheap과 map, filter의 polyfill을 작성해보면서 생성자 함수로 생성한 자료구조와 고차함수의 작동원리에 대한 깊은 이해를 하기위해 글을 작성하게 되었습니다.
자료구조
이 글에서 다뤄볼 자료구조는 아래와 같습니다.
- Stack
- Queue
- Heap
책에는 생성자 함수와 클래스로 구현한 대표적인 자료구조인 Stack, Queue가 있었고 추가한 부분은 MaxHeap입니다. MaxHeap은 보통 그리디 알고리즘이나 다익스트라 알고리즘을 사용할때, 많이 사용하는 경우가 있어서 작성하게 되었습니다.
Stack
생성자 함수 ver
const Stack = (function () {
function Stack(array = []) {
if (!Array.isArray(array)) {
throw new TypeError('Not an array!');
}
this.array = array;
}
Stack.prototype = {
constructor: Stack,
push(value) {
return this.array.push(value);
},
pop() {
return this.array.pop();
},
entries() {
return [...this.array];
}
};
return Stack;
})();
const stack = new Stack([1, 2]);
stack.push(3);
console.log(stack.entries());
stack.pop();
console.log(stack.entries());생성자 함수로 만드는 부분이 즉시실행함수를 사용하여 만들기 때문에 처음에 헷갈렸습니다. 이 부분은 응집도를 높이기 위해 이렇게 즉시실행함수로 만들어 작성한듯 합니다.
생성자 함수와 동일한 이름을 갖는 function Stack을 안에 정의하여 클래스의 constructor와 유사한 역할을 하도록 만들고, prototype을 사용한 이유는 인스턴스에 각각 메서드를 주게되면 메모리의 낭비가 생기기 때문에 Stack.prototype을 정의하여 만듭니다. 프로토타입을 정의할 시, constructor: Stack 또한 정의해야 함을 놓치면 안됩니다.
생성자 함수로 정의할 시 문제점이 있다면, array가 인스턴스.array로 접근 시 접근이 가능하여 완전한 은닉이 가능하지는 않다는 점입니다.
클래스 ver
class Stack {
#array;
constructor(array = []) {
if (!Array.isArray(array)) {
throw new TypeError('Not an array!');
}
this.#array = array;
}
push(value) {
return this.#array.push(value);
}
pop() {
return this.#array.pop();
}
entries() {
return [...this.#array];
}
}
const stack = new Stack([1, 2]);
stack.push(3);
console.log(stack.entries());
stack.pop();
console.log(stack.entries());클래스의 경우 제안단계에 있는 private 필드 정의를 사용하여 배열을 선언하여 정보 은닉을 가능하게 합니다.
생성자 함수로 만들때와 달리 좀 더 간편하게 construcor 및 메서드를 작성할 수 있어서 편하고, 객체 리터럴로 만들지 않기 때문에 ,(콤마)를 넣어주지 않아도 됩니다.
Queue
생성자 함수 ver
const Queue = (function () {
function Queue(array = []) {
if (!Array.isArray(array)) {
throw new TypeError('Not an array!');
}
this.array = array;
}
Queue.prototype = {
constructor: Queue,
enqueue(value) {
return this.array.push(value);
},
dequeue() {
return this.array.shift();
},
entries() {
return [...this.array];
}
};
return Queue;
})();
const queue = new Queue([1, 2]);
queue.enqueue(3);
console.log(queue.entries());
queue.dequeue();
console.log(queue.entries());스택과 크게 다르지 않지만, dequeue의 경우 pop이 아닌 shift임에 유의하여 작성하여야 합니다. 생성자 함수이므로 완전한 정보 은닉이 가능하진 않습니다.
클래스 ver
class Queue {
#array;
constructor(array = []) {
if (!Array.isArray(array)) {
throw new TypeError('Not an array!');
}
this.#array = array;
}
enqueue(value) {
return this.#array.push(value);
}
dequeue() {
return this.#array.shift();
}
entries() {
return [...this.#array];
}
}
const queue = new Queue([1, 2]);
queue.enqueue(3);
console.log(queue.entries());
queue.dequeue();
console.log(queue.entries());클래스로 만든 큐입니다.
Heap
생성자 함수 ver
const MaxHeap = (function () {
function MaxHeap(array = []) {
if (!Array.isArray(array)) {
throw new TypeError('Not an array!');
}
this.array = array;
this.array.push(Number.MAX_SAFE_INTEGER);
}
MaxHeap.prototype = {
constructor: MaxHeap,
insert(val) {
this.array.push(val);
this.upheap(this.array.length - 1);
},
upheap(pos) {
while (pos >= 1 && this.array[pos] > this.array[Math.floor(pos / 2)]) {
const curValue = this.arary[pos];
this.array[pos] = this.array[Math.floor(pos / 2)];
this.array[Math.floor(pos / 2)] = curValue;
pos = Math.floor(pos / 2);
}
},
get() {
const val = this.array[1];
if (this.array.length === 2) {
return this.array.pop();
}
this.array[1] = this.array.pop();
this.downheap(1, this.array.length - 1);
return val;
},
downheap(pos, len) {
const val = this.array[pos];
while (pos <= Math.floor(len / 2)) {
let child = pos * 2;
if (this.array[child] < this.array[child + 1]) child += 1;
if (val >= this.array[child]) break;
this.array[pos] = this.array[child];
pos = child;
}
},
size() {
return this.array.length - 1;
},
show() {
for (let i = 1; i <= this.size(); i++) {
console.log(this.array[i]);
}
}
};
return MaxHeap;
})();
const newHeap = new MaxHeap();
newHeap.insert(10);
newHeap.insert(9);
newHeap.insert(8);
console.log(newHeap.show());
console.log(newHeap.get());
Stack이나 Queue와 달리 구현함에 있어서 MaxHeap은 고려해야할 부분이 많습니다.
우선 Heap을 구현할 시 배열을 사용하여 구현하였으며, MaxHeap이므로 가장 큰 값이 트리의 최상단에 위치하게 됩니다. 0번 index에 가장 큰 값을 설정해두고, 1번 인덱스부터 사용하는 방식입니다.
값의 삽입 시, 그 값이 부모의 값보다 크다면 위로 올려주어야하기 때문에 upheap함수를 호출하여 값이 제자리를 찾아가도록 만들어줍니다.
값을 get함수를 통해 최 상단의 값을 가져오고 나면, 그 부분을 채우기 위해 MaxHeap의 가장 마지막에 존재하는 값(제일 작은 값)을 꺼내 그 자리에 위치 시킨뒤, downheap 함수를 통해 자식과 값을 비교하면서 제자리를 찾아가도록 만들어 줍니다.
클래스 ver
class MaxHeap {
#array;
constructor(array = []) {
if (!Array.isArray(array)) {
throw new TypeError('Not an array!');
}
this.#array = array;
this.#array.push(Number.MAX_SAFE_INTEGER);
}
insert(val) {
this.#array.push(val);
this.upheap(this.#array.length - 1);
}
upheap(pos) {
while (pos >= 1 && this.#array[pos] > this.#array[Math.floor(pos / 2)]) {
const curValue = this.#array[pos];
this.#array[pos] = this.#array[Math.floor(pos / 2)];
this.#array[Math.floor(pos / 2)] = curValue;
pos = Math.floor(pos / 2);
}
}
get() {
const val = this.#array[1];
if (this.#array.length === 2) {
return this.#array.pop();
}
this.#array[1] = this.#array.pop();
this.downheap(1, this.#array.length - 1);
return val;
}
downheap(pos, len) {
const val = this.#array[pos];
while (pos <= Math.floor(len / 2)) {
let child = pos * 2;
if (this.#array[child] < this.#array[child + 1]) child += 1;
if (val >= this.#array[child]) break;
this.#array[pos] = this.#array[child];
pos = child;
}
}
size() {
return this.#array.length - 1;
}
show() {
for (let i = 1; i <= this.size(); i++) {
console.log(this.#array[i]);
}
}
}
const newHeap = new MaxHeap();
newHeap.insert(10);
newHeap.insert(9);
newHeap.insert(8);
console.log(newHeap.show());
console.log(newHeap.get());생성자 함수 부분에서 코드에 대한 설명은 다하였고, 클래스로 사용하여 구현하는 방식이 그나마 조금 더 간단한 것을 볼 수 있을 것입니다.
Polyfill
forEach
if (!Array.prototype.forEach) {
Array.prototype.forEach = function (callback, thisArg) {
if (typeof callback !== 'function') {
throw new TypeError(callback + 'is not a function');
}
// this로 사용할 두 번재 인수를 전달받지 못하면 전역 객체를 this로 사용한다.
thisArg = thisArg || window;
for (let i = 0; i < this.length; i++) {
callback.call(thisArg, this[i], i, this);
}
};
}forEach의 인자로 전달받은 callback이 함수가 아니면 TypeError를 발생시킵니다. polyfill이기 때문에 템플릿 리터럴을 사용하지 않고 문자열을 표현하는 작음따옴표나 큰 따옴표를 사용합니다.
thisArg를 인수로 받지 못했다면 window를 사용하고, for 문으로 배열을 순회하면서 콜백함수를 호출하여 thisArg를 전달하고, 배열요소, 인덱스, 배열 자신을 전달합니다.
map
if (!Array.prototype.map) {
Array.prototype.map = function (callback, thisArg) {
if (typeof callback !== 'function') {
throw new TypeError(callback + 'is not a function');
}
var arr = new Array(this.length);
thisArg = thisArg || window;
for (let i = 0; i < this.length; i++) {
arr[i] = callback.call(thisArg, this[i], i, this);
}
return arr;
};
}앞의 forEach polyfill을 약간만 수정해서 작성해보았습니다. map은 원본 배열과 동일한 길이의 배열을 반환하므로 arr을 동일한 길이의 배열로 만들고 콜백함수가 반환하는 요소들을 순서대로 arr에 담아 리턴합니다.
mdn
출처: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/map
if (!Array.prototype.map) {
Array.prototype.map = function (callback, thisArg) {
let T;
let A;
let k;
if (this == null) {
throw new TypeError(' this is null or not defined');
}
const O = Object(this);
const len = O.length >>> 0;
if (typeof callback !== 'function') {
throw new TypeError(callback + ' is not a function');
}
if (arguments.length > 1) {
T = thisArg;
}
A = new Array(len);
k = 0;
while (k < len) {
var kValue;
var mappedValue;
if (k in O) {
kValue = O[k];
mappedValue = callback.call(T, kValue, k, O);
A[k] = mappedValue;
}
k++;
}
return A;
};
}mdn 에서는 다음과 같이 map 폴리필을 작성하였습니다. mdn에서는 상세한 부분까지 조건들을 만들어 주느라 코드가 복잡해졌지만, 간단하게만 작성하는 경우 forEach를 변형한 map 폴리필이 더 쉽게 이해가 갈 것입니다.
filter
if (!Array.prototype.filter) {
Array.prototype.filter = function (callback, thisArg) {
if (typeof callback !== 'function') {
throw new TypeError(callback + 'is not a function');
}
var arr = [];
thisArg = thisArg || window;
for (let i = 0; i < this.length; i++) {
if (callback.call(thisArg, this[i], i, this)) {
arr.push(this[i]);
}
}
return arr;
};
}마찬가지로 처음 forEach 폴리필을 변형하여 조건에 충족되는 것들만 arr배열에 담아 리턴해주는 방식으로 filter 폴리필을 작성하였습니다.
mdn
출처: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/filter
if (!Array.prototype.filter){
Array.prototype.filter = function(func, thisArg) {
'use strict';
if ( ! ((typeof func === 'Function' || typeof func === 'function') && this) )
throw new TypeError();
var len = this.length >>> 0,
res = new Array(len), // preallocate array
t = this, c = 0, i = -1;
if (thisArg === undefined){
while (++i !== len){
// checks to see if the key was set
if (i in this){
if (func(t[i], i, t)){
res[c++] = t[i];
}
}
}
}
else{
while (++i !== len){
// checks to see if the key was set
if (i in this){
if (func.call(thisArg, t[i], i, t)){
res[c++] = t[i];
}
}
}
}
res.length = c; // shrink down array to proper size
return res;
};
}mdn에서는 다음과 같이 unsigned right shift operator (>>>)와 같은 비트 연산자를 사용하여 조건을 정하여 구현을 하였습니다. map과 마찬가지로 간단하게 구현하는 경우, forEach를 변형하여 배열리터럴로 배열을 생성해두고 콜백의 결과가 true인 경우에 값을 넣어주고 그 배열을 반환시키면 더 쉽게 구현을 할 수 있습니다.
결론
자료구조의 경우, 생성자 함수와 클래스를 이용하여 한 번 구현을 해보았는데 클래스의 경우 private을 지원하기 때문에 감추고 싶은 프로퍼티나 메서드를 감출 수 있게 되어 정보은닉이 가능하였습니다. 따라서 개발자의 의도가 정보 은닉을 지원하는 자료구조를 만들고 싶을 때에는 생성자 함수보다는 클래스를 사용하여 구현하는 것이 더 알맞다고 생각이 들었습니다.
또한, forEach, map, filter의 polyfill을 코드를 구현해보고 알아보면서, 코드가 안에서 실제로 어떻게 돌아가는 지 확인할 수 있었고, 그에 따른 고차함수에 대한 이해를 할 수 있었습니다.
