2022.8.16. 화요일 stack, queue 자료 구조 구현하기 & V8엔진에서 배열이란?

Dorito·2022년 8월 16일

공부기록

공부 기록

목록 보기

3/71

[참고 자료]

JavaScript Queue 구현: 파란제이님 티스토리 출처
JS 알고리즘 구현: 큐(Queue) 구현 vs Array 메서드(shift, splice) 사용했을때 속도 비교
사진 자료 출처

개요

자료구조를 공부하는데 어제는 스택하고 오늘은 큐를 한번 다뤄봐야겠다! 하고 막상 봤더니 바로 난관에 봉착했다.
이유는 ... 자바스크립트에 큐가 지원이 안된다! 이게 뭔소린고 하면

일단 기본적으로 자바스크립트에서 스택, 큐를 구현하려면
stack은 배열에 push(), pop()
queue는 배열에 push(), shift() 메서드를 쓰면 된다.

근데 하나 의문이었던건 우리가 큐를 사용하는 이유는 시간 복잡도가 O(1)이어서 아닌가?

자바스크립트의 shift() 메서드는 O(n)일텐데, 사용하는 의미가 있을까? 해서 열심히 찾아봤다.
( cf: shift() 메서드가 O(n)인 이유는 제일 앞에 있는 걸 뺀 나머지 element들을 재정렬해야하기 때문이다)

C++의 경우 STL을 통해 사용할 수 있고,
Python의 경우 dequeue를 써서 삽입, 삭제 시 O(1)의 시간복잡도를 갖는 큐 자료구조를 활용할 수 있다고 한다.
근데 자바스크립트만 ...! pop(), push() 는 O(1)인데...!!!! 왜!!!! shift()는...!!!
너무 찝찝했다.

아 물론 구글링해보니 만약 N이 1,000 이하라면 shift()를 사용해도 무방하다고 한다.
그러나 데이터 수가 많아진다면? 어떻게 대처를 해야할까?
하고 열심히 찾아보니 자바스크립트는 따로 class 객체로 구현한다고 한다.

자바스크립트에서 배열이란? 배열의 정체성을 찾아서.

아 좀 글 흐름이랑 갑툭튀인 정보이긴 한데 이것도 궁금했어서 찾아봤다.

우리 자스만 왜 이럴까! 하고 곰곰이 생각해보니
어렴풋이 자스에서는 배열이 객체..라는 이야기를 들었던 것이 생각이 났다.
그래서 조금 서칭해보니
역시나 V8 엔진이 최적화를 하면서 동적으로 관리한다고.. 그리고 또

자바스크립트에서 배열은 객체다!!

라고 한다. ㅋㅋㅋ 예ㅖ 약간 매트릭스 세계관인가요 ???!!
아무튼 그래서 개발자들이 추측하기 힘들다고 한다.

읽어보면 좋을 글
https://devkly.com/nodejs/javascript-array/ (한글 자료)
https://poiemaweb.com/js-array-is-not-arrray (한글 자료)
https://woong-jae.com/javascript/220419-v8-array-internals (한글 자료)
https://blog.dashlane.com/how-is-data-stored-in-v8-js-engine-memory/

V8은 자바스크립트 코드를 실행하는 동안 각 배열이 어떤 element kind를 가지는지 기록한다. Element kind에 따라 V8은 배열에 대한 연산(reduce, map, forEach 등)을 최적화한다고 한다.

자바스크립트는 숫자가 integer든, float든, double이든 모두 number로 처리하는데
엔진 레벨에서는 더욱 정밀한 구분을 한다고 한다. (element kind라고 구분하는건 총 21가지인데.. 크롬코드를 볼 수 있는 여기에서 확인 가능하다.)

자바스크립트 Array는 number-property Object이다.
자바스크립트 엔진(v8)은 Array와 Object를 명백히 구분한다.
number-properties는 Heap에 존재하는 JS Object.elements에 저장/관리 된다.
자바스크립트 배열은 인덱스를 프로퍼티 키로 갖으며 length 프로퍼티를 갖는 특수한 객체이다. 자바스크립트 배열의 요소는 사실 프로퍼티 값이다.
자바스크립트에서 사용할 수 있는 모든 값은 객체의 프로퍼티 값이 될 수 있으므로 어떤 타입의 값이라도 배열의 요소가 될 수 있다.

그리고 3번째 글이랑 여기를 읽어보면 V8 엔진이 배열을 어떻게 처리하는가에 대해서 자세히 나와있는데 배열 성능을 높이기 위해서 흥미로운 내용이 있어서 가져와봤다.

배열 처리 성능 높이는 법

배열을 사용할 때 new Array(n)보다 []를 사용하는 것이 더 좋다
new Array(n)을 사용하면 배열은 무조건 HOLEY가 되기 때문이다. (= 배열의 요소가 연속적이지 않고, 사이사이에 'hole'이 있다) ~ V8은 hole이 많은 배열은 메모리를 아끼기 위해 해쉬 테이블로 저장한다. 해쉬 테이블에 대한 연산은 해시 코드 계산, 엔트리 룩업, 리해싱 때문에 배열에 대한 연산보다 느리다.

배열을 사용할 때 가능한 구체적인 element kind를 사용하는 것이 성능에 좋다.

-> 성능저하 일어남

배열의 길이 밖 인덱스를 읽는 것을 삼가해야 한다.
Out-of-bound 인덱스를 읽게되면 프로퍼티가 배열에 없기 떄문에 자바스크립트 엔진은 프로토타입 체인을 뒤지게 된다. 이렇게 되면 V8은 "이 배열은 특별한 경우를 처리해야 한다"라는 것을 기억하고, out-of-bound를 읽기 전만큼 빠르게 동작하지 않게된다.

더 파고 가면 안될 것 같아서 대충 아~ 자바스크립트는 C++처럼 배열 메모리 정적/동적 할당 이런거랑은 완전 다른 얘기구나~ V8엔진이 지 알아서 객체로 처리하는데 좀 까다롭게 최적화를 하는구나 ~ 최적화는 이런 방식으로 하는구나 ~ 즈음으로 이해했다.

(아.. 쓰면서 생각난건데 C++ 에서 배열 메모리 관련 이해가 힘들어서 나중에 또 다시 복습해야할 듯 하다. 할 것 많다.. 독학 단점... 갑자기 삼천포로 빠져서 희안한 걸로 삽질한다)

자료구조 구현

아무튼 각설하고 큐만 구현하기에는 심심한 것 같아서,
스택부터 열심히 구글링하고 코드를 이해하려고 열심히 노력했다.

자스 객체..에 대한 개념이 충분하지 않아서 기초자료부터 보려니 너무 할게 많았다!
객체에 대해서 아직 까막눈인데 덕분에 이렇게 또 공부를 이렇게 연관지어서 공부하니까 재밌었다. :D

Stack 자료구조 구현

스택은 LIFO (Last In First Out)

class Stack {
    constructor() {
        this.storage = {};
        this.size = 0;
    }

    push(element) {
        this.size++; 
        this.storage[this.size] = element;
    }

    pop() {
        let removed = this.storage[this.size];
        delete this.storage[this.size];
        this.size--;
        return removed;
    }


    peek() {
        return this.storage[this.size];
    }
}

스택 코드 출처

stack 테스트


const stack = new Stack();
stack.push('dog');
stack.push('cat');
stack.push('hamster');

console.log(stack); 
// 출력: Stack { storage: { '1': 'dog', '2': 'cat', '3': 'hamster' }, size: 3 }
console.log('pop', stack.pop()); 
// 출력: hamster
console.log(stack); 
// 출력: Stack { storage: { '1': 'dog', '2': 'cat' }, size: 2 }
console.log(stack.peek()); 
// 출력: cat

큐 자료구조 구현 (이해하기 쉬운 ver.)

큐는 FIFO
자바스크립트에서 객체(Object)는 key-value의 구조로 사용할 수 있으며, key 값을 통해 O(1) 시간으로 접근할 수 있다. 즉 일종의 해시(Hash)로 활용이 가능한데 이를 통해 큐를 구현해보자.

class Queue {
    constructor() {
        this.storage = {}
        this.head = 0;
        this.tail = 0;
    };

    enqueue(element) {
        this.storage[this.tail] = element;
        this.tail++;
    };

    dequeue() {
        let removed = this.storage[this.head];
        delete this.storage[this.head];
        this.head++;
        return removed;
    };
}

큐 테스트

const queue = new Queue();

queue.enqueue('first');
queue.enqueue('second');
queue.enqueue('third');

console.log(queue);
/* 출력:
Queue {
    storage: { '0': 'first', '1': 'second', '2': 'third' },
    head: 0,
    tail: 3
  } 
*/

console.log('dequeue', queue.dequeue());
// 출력: dequeue first

console.log(queue);
// 출력: Queue { storage: { '1': 'second', '2': 'third' }, head: 1, tail: 3 }

큐 자료구조 구현 (더 좋아보이는 ver.)

상세한 설명과 함께 있는 큐

JS 알고리즘 구현: 큐(Queue) 구현 vs Array 메서드(shift, splice) 사용했을때 속도 비교


class Node{
    constructor(value){
        this.next = null;
        this.value = value;
    }
}
class Queue{
    constructor (){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    enqueue(value){
        let node = new Node(value);
        this.tail = node;
        this.size == 0 ? this.head = node : this.tail.next = node; 
        this.size++;
    }

    dequeue(){
        if(this.size == 0){
            this.tail = null;
            return null;
        }
        let value = this.head.value;
        this.head = this.head.next;
        this.size--;
        return value;
    }
    isEmpty(){
        return this.size == 0;
    }
}


// 테스트 코드
const queue = new Queue;
console.log(queue); 
queue.enqueue("first");
console.log(queue);
queue.enqueue("second");
console.log(queue);
queue.enqueue("third");
console.log(queue);
console.log('deque', queue.dequeue());
console.log(queue);