JS - BST와 Array의 구현, 성능비교

BST가 검색 성능이 빠르다고 알고 있었지만, 실제로 사용 해본 경험이 없어서 하는김에 JS Array에서 보통 사용하는 includes와 성능 비교를 해보려고 합니다.

BST 소스

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }
  
  class BinarySearchTree {
    constructor() {
      this.root = null;
    }
  
    insert(value) {
      const newNode = new TreeNode(value);
  
      if (!this.root) {
        this.root = newNode;
      } else {
        this.insertNode(this.root, newNode);
      }
    }
  
    insertNode(node, newNode) {
      if (newNode.value < node.value) {
        if (!node.left) {
          node.left = newNode;
        } else {
          this.insertNode(node.left, newNode);
        }
      } else {
        if (!node.right) {
          node.right = newNode;
        } else {
          this.insertNode(node.right, newNode);
        }
      }
    }
  
    search(value) {
      return this.searchNode(this.root, value);
    }
  
    searchNode(node, value) {
      if (!node) {
        return false;
      }
  
      if (node.value === value) {
        return true;
      } else if (value < node.value) {
        return this.searchNode(node.left, value);
      } else {
        return this.searchNode(node.right, value);
      }
    }
  }
  
  const tree = new BinarySearchTree();
  tree.insert(n);
  tree.search(n);

TreeNode 클래스는 노드 생성, BinarySearchTree 클래스는 이진트리 생성입니다.
BinarySearchTree에서 데이터가 들어올 때 마다 TreeNode를 생성해서 저장하며,
insert, insertNode를 이용해서 노드에 데이터를 삽입하고
search, searchNode를 이용해서 BST를 검색 해보았습니다.

Array 소스

let data = [];
data.push(n);
data.includes(n);

전체 소스

function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }
  
  class BinarySearchTree {
    constructor() {
      this.root = null;
    }
  
    insert(value) {
      const newNode = new TreeNode(value);
  
      if (!this.root) {
        this.root = newNode;
      } else {
        this.insertNode(this.root, newNode);
      }
    }
  
    insertNode(node, newNode) {
      if (newNode.value < node.value) {
        if (!node.left) {
          node.left = newNode;
        } else {
          this.insertNode(node.left, newNode);
        }
      } else {
        if (!node.right) {
          node.right = newNode;
        } else {
          this.insertNode(node.right, newNode);
        }
      }
    }
  
    search(value) {
      return this.searchNode(this.root, value);
    }
  
    searchNode(node, value) {
      if (!node) {
        return false;
      }
  
      if (node.value === value) {
        return true;
      } else if (value < node.value) {
        return this.searchNode(node.left, value);
      } else {
        return this.searchNode(node.right, value);
      }
    }
  }
  
  const maxNum = 10000000;
  const find1 = 5000;
  const find2 = 3978;

  let bst_s1 = new Date().getTime();
  // 예제를 실행해봅시다.
  const tree = new BinarySearchTree();
  for(let i=1; i<maxNum; i++){
    tree.insert(getRandomInt(1, maxNum));
  }
  let bst_e1 = new Date().getTime();
  let bst_s2 = new Date().getTime();
  const result_bst1 = tree.search(find1);
  const result_bst2 = tree.search(find2);
  let bst_e2 = new Date().getTime();
  console.log(bst_e1-bst_s1, bst_e2-bst_s2, result_bst1, result_bst2);


  let arr_s1 = new Date().getTime();
  let data = [];
  for(let i=1; i<maxNum; i++){
    data.push(getRandomInt(1, maxNum));
  }
  let arr_e1 = new Date().getTime();
  let arr_s2 = new Date().getTime();
  const result_arr1 = data.includes(find1);
  const result_arr2 = data.includes(find2);
  let arr_e2 = new Date().getTime();
  console.log(arr_e1-arr_s1, arr_e2-arr_s2, result_arr1, result_arr2);

순차적인 데이터는 테스트 의미가 없으므로 getRandomInt() 을 이용해서 랜덤 함수를 입력 해줍니다.
maxNum : 최대 랜덤수
find ~ : 검색하려는 수

간단히 테스트를 해보니 1억건에서는 heap out of memory가 나버렸다.
4GB의 메모리까지는 잘 올라가다가 heap oom이 나버려서 결과 값을 얻지는 못했다.

1000만건에 대해서는 유의미한 결과를 확인 할 수 있었는데,

일반 순차검색은 O(n), BST는 O(logn) 이기 때문에 검색 속도가 다를것으로 예상 되었다.

보통 데이터가 입력되는 시간은 15624, 242 ms로 BST가 약 70배정도 느리지만 이렇게 한번에 데이터를 넣는 경우는 없을거라 생각되고, 하나씩 넣는다고 가정하면 상관 없다고 생각한다.

검색 속도는 0, 17 ms로 검색 되었는데, 지금은 두개의 데이터만 검색해서 그렇지 동시접속 사용자가 많아지거나, 많은 검색이 이루어 질때에는 유의미한 검색 속도라고 생각된다.

결론

1억건은 js에서 따로 설정이 필요하거나, 설정이 안되면 힘들다고 판단되고,
1000만건은 BST 사용 고려가 유의미 하다고 판단된다.
100만건에서는 검색 속도 차이가 나긴 하지만 1ms 정도의 미세한 차이기 때문에 Array를 써도 상관 없다고 판단된다.