prefix-search-tree-vs-filter.js

/**
 *
 * Search value with tree vs filter()
 *
 * Generate data file:
 * echo "module.exports = [" > /tmp/data.js; for n in {1..1000000}; do echo "\"bk-${n}\"," >> /tmp/data.js; done; echo "]" >> /tmp/data.js;
 *
 * Run search:
 * node --max-old-space-size=4096 ./prefix-search-tree-vs-filter.js
 *
 */

/**
 * Output example:
 * 
 * -- Search, data array length: 1000000
 *
 * -- create tree 1656ms
 * -- search "bk-111111" [Search Tree]: 1
 * -- time 1ms
 *
 * -- search "bk-111111" [.filter()]: 1
 * -- time 79m
 *      
 */

const data = require('/tmp/data.js');

console.log(`-- Search, data array length: ${data.length}`);
console.log(``);

let startTime = +new Date();

const Node = function () {
  this.key = null;
  this.left = null;
  this.right = null;
}

Node.prototype.insert = function (key) {
  if (this.key === null) {
    this.key = key;
  } else if (key <= this.key) {
    if (this.left === null) {
      this.left = new Node();
    }
    this.left.insert(key);
  } else if (key > this.key) {
    if (this.right === null) {
      this.right = new Node();
    }
    this.right.insert(key);
  } else {
    throw new Error(`Can not insert key "${key}"`);
  }
}

Node.prototype.search = function (key) {
  if (this.key === key) {
    return [key];
  } else if (key <= this.key && this.left !== null) {
    return this.left.search(key);
  } else if (key > this.key && this.right !== null) {
    return this.right.search(key);
  } else {
    return [];
  }
}

const root = new Node();

data.forEach((v) => {
  root.insert(v);
});

function search(text) {
  return new Set(root.search(text));
}

console.log(`-- create tree ${+new Date() - startTime}ms`);

const v = 'bk-111111';

startTime = +new Date();
console.log(`-- search "${v}" [Search Tree]: ${search(v).size}`);
console.log(`-- time ${+new Date() - startTime}ms`);
console.log(``);

startTime = +new Date();
console.log(`-- search "${v}" [.filter()]: ${data.filter((i) => i === v).length}`);
console.log(`-- time ${+new Date() - startTime}ms`);
console.log(``);