Comparison of search speeds between Arrays and Sets

!README.md

Comparison of search speeds between Arrays and Sets

Execution

$ node ./index.js

Result

Array/Set	Value Type	Size	Search Count	Time (ms)
array	integer	1000	100	0ms
array	integer	1000	1000	0ms
array	integer	1000	10000	4ms
array	integer	10000	1000	4ms
array	integer	10000	10000	51ms
array	integer	10000	100000	473ms
set	integer	1000	100	0ms
set	integer	1000	1000	0ms
set	integer	1000	10000	1ms
set	integer	10000	1000	0ms
set	integer	10000	10000	0ms
set	integer	10000	100000	4ms
array	uuid	1000	100	1ms
array	uuid	1000	1000	4ms
array	uuid	1000	10000	48ms
array	uuid	10000	1000	38ms
array	uuid	10000	10000	481ms
array	uuid	10000	100000	4762ms
set	uuid	1000	100	0ms
set	uuid	1000	1000	0ms
set	uuid	1000	10000	0ms
set	uuid	10000	1000	0ms
set	uuid	10000	10000	0ms
set	uuid	10000	100000	4ms

index.js

const crypto = require('crypto');

function generateRandomInt() {
  const arr = new Uint32Array(1);
  crypto.getRandomValues(arr);
  return arr[0];
}

function generateData(type) {
  switch (type) {
    case "uuid":
      return crypto.randomUUID();
    case "integer":
      return generateRandomInt();
    default:
      throw new Error(`Undefined type: ${type}`);
  }
}

function getSetData(type, length) {
  const sets = new Set([]);
  while (sets.size < length) {
    sets.add(generateData(type));
  }
  return sets;
}

function getArrayData(type, length) {
  return Array.from(getSetData(type, length))
}

function getRandomValues(arrayLikes, size) {
  const getRandomSortedArr = () => Array.from(arrayLikes).sort(() => generateRandomInt() % 2 === 0 ? -1 : 1)
  const results = [];
  let arr = getRandomSortedArr()
  while (results.length < size) {
    results.push(arr.shift())
    if (arr.length <= 0) {
      arr = getRandomSortedArr()
    }
  }
  return results;
}

function measureMs(callback) {
  const start = new Date().getTime();
  callback();
  return new Date().getTime() - start;
}

function p(str) {
  return String(str).padStart(12, ' ')
}

function pm(str) {
  const start = Math.floor((12 - String(str).length) / 2) - str.length
  return String(str).padStart(start, ' ').padEnd(12, ' ')
}

function measure(arrayOrSet, valueType, size, search) {
  let ms = -1;
  if (arrayOrSet === 'set') {
    const set =  getSetData(valueType, size);
    const values = getRandomValues(set, search)
    ms = measureMs(() => values.forEach((uuid) => set.has(uuid)));
  } else {
    const arr = getArrayData(valueType, size);
    const values = getRandomValues(arr, search)
    ms = measureMs(() => values.forEach((uuid) => arr.includes(uuid)));
  }
  console.log(`| ${pm(arrayOrSet)} | ${pm(valueType)} | ${p(size)} | ${p(search)} | ${p(`${ms}ms`)} |`)
}

console.log('|  Array/Set   |  Value Type  |     Size     | Search Count |  Time (ms)   |');
console.log('|:-------------|:-------------|-------------:|-------------:|-------------:|');
measure('array', 'integer', 1000, 100);
measure('array', 'integer', 1000, 1000);
measure('array', 'integer', 1000, 10000);
measure('array', 'integer', 10000, 1000);
measure('array', 'integer', 10000, 10000);
measure('array', 'integer', 10000, 100000);
measure('set', 'integer', 1000, 100);
measure('set', 'integer', 1000, 1000);
measure('set', 'integer', 1000, 10000);
measure('set', 'integer', 10000, 1000);
measure('set', 'integer', 10000, 10000);
measure('set', 'integer', 10000, 100000);
measure('array', 'uuid', 1000, 100);
measure('array', 'uuid', 1000, 1000);
measure('array', 'uuid', 1000, 10000);
measure('array', 'uuid', 10000, 1000);
measure('array', 'uuid', 10000, 10000);
measure('array', 'uuid', 10000, 100000);
measure('set', 'uuid', 1000, 100);
measure('set', 'uuid', 1000, 1000);
measure('set', 'uuid', 1000, 10000);
measure('set', 'uuid', 10000, 1000);
measure('set', 'uuid', 10000, 10000);
measure('set', 'uuid', 10000, 100000);