fulltext-prefix-search-tree-vs-filter.js

/**
 *
 * Search 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 ./fulltext-prefix-search-tree-vs-filter.js
 *
 */

/**
 * Output example:
 *
 * -- Search, data array length: 1000000
 *
 * -- root map keys: MapIterator { 'b', '1', '-', 'k', '2', '3', '4', '5', '6', '7', '8', '9', '0' } / insert calls: 726580472
 *
 * -- create tree 60907ms
 *
 * -- search "a", limit: 10
 *      [Prefix Search Tree] results: 0,  time: 0ms
 *      [for + .includes() ] results: 0,  time: 83ms
 *
 * -- search "b", limit: 10
 *      [Prefix Search Tree] results: 10, time: 1ms
 *      [for + .includes() ] results: 10, time: 0ms
 *
 * -- search "99999", limit: 10
 *      [Prefix Search Tree] results: 10, time: 0ms
 *      [for + .includes() ] results: 10, time: 85ms
 *
 * -- search "999999", limit: 10
 *      [Prefix Search Tree] results: 1,  time: 0ms
 *      [for + .includes() ] results: 1,  time: 86ms
 *
 */

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

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

let startTime = +new Date();

let n = 0;
const LIMIT = 10;
const Node = function (root) {
  this.root = (root || this);
  this.indexes = new Set();
  this.children = new Map();
}

Node.prototype.insert = function (value, index) {
  n++;
  //if (n % 1000000 === 0) console.log('--n', n, index)
  if (value.length === 0) {
    this.indexes.add(index);
    return;
  }

  const key = value.slice(0, 1);
  const childrenStr = value.slice(1);

  let child = this.children.get(key);
  if (!child) {
    child = new Node(this.root);
    this.children.set(key, child);
  }

  child.insert(childrenStr, index);

  if (childrenStr.length) {
    this.root.insert(childrenStr, index);
  }
}

Node.prototype.print = function (i) {
  i = (i || 0) + 1;
  const p = (new Array(i)).fill('').join(' | ');
  for (let [k, v] of this.children.entries()) {
    console.log(p, `'${k}' {`);
    v.print(i);
    console.log(p, `}`);
  }
  const indexes = [];
  for (let [v] of this.indexes.entries()) {
    indexes.push(v);
  }
  console.log(p, 'indexes: ', indexes.join(','));
}

Node.prototype.search = function (s, value) {
  if (s.size == LIMIT) return;
  if (value === '') {
    for (let [v] of this.indexes.entries()) {
      s.add(v);
    }
    for (let [i, c] of this.children) {
      c.search(s, value);
    }
  } else {
    const key = value.slice(0, 1);
    const child = this.children.get(key);
    if (child) {
      child.search(s, value.slice(1, value.length));
    }
  }
}

const root = new Node();

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

console.log('-- root map keys:', root.children.keys(), '/ insert calls:', n);
//root.print();
console.log('');

function search(text) {
  const s = new Set();
  root.search(s, text);
  return s;
}

function searchDefault(text) {
  const s = new Set();
  for (let i = 0; i < data.length; i++) {
    if (data[i].includes(text)) {
      s.add(i);
      if (s.size === LIMIT) {
        break;
      }
    }
  }
  return s;
}

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

function test(v) {
  startTime = +new Date();
  console.log(`-- search "${v}", limit: ${LIMIT}`);
  console.log(`     [Prefix Search Tree] results: ${search(v).size}, \ttime: ${+new Date() - startTime}ms`);
  startTime = +new Date();
  console.log(`     [for + .includes() ] results: ${searchDefault(v).size}, \ttime: ${+new Date() - startTime}ms`);
  console.log(``);
}

test('a');
test('b');
test('99999');
test('999999');