Run results for: Mapping a pair of numbers (2 numbers) to another number [Algorithm 1]

Comparing the performance of different implementations of 2-Tuple cache (mapping a pair of numbers to another number) when being used to achieve memoization a recursive algorithm.

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36

Browser: Chrome 131

Operating system: Mac OS X 10.15.7

Device Platform: Desktop

Date tested: 24 days ago

Test name	Executions per second
2-Level Map (Map<K1, Map<K2, V>>)	1.9 Ops/sec
2-Level Array (V[][])	4.6 Ops/sec
2-Level Object (Object.<K1, Object.<K2, V>>)	5.4 Ops/sec
1-Level Array (V[])	0.2 Ops/sec
1-Level Object (Object.<[K1, K2], V>)	0.2 Ops/sec

HTML Preparation code:

<h1>Concepts</h1>
<div id="log"></div>

Script Preparation code:

/*
 * These functions are related to the "Concepts" section, and are unrelated to
 * the benchmark. Please find the "Actual Benchmark" section under the
 * "Concepts" section below. */

function fixUI() {
  const iFrame = window.frameElement;
  if (iFrame) {
    console.log(iFrame.tagName);
    iFrame.style.width = "100%";
    iFrame.style.minHeight = "50vh";
  }
}

fixUI();

const messageWidth = 40;

function logValue(message, value) {
  const spanMessage = document.createElement("span");
  spanMessage.append(message);

  const spanSpace = document.createElement("span");
  if (message.length < messageWidth) {
    spanSpace.append(" ".repeat(messageWidth - message.length));
  }

  const spanSlashSlash = document.createElement("span");
  spanSlashSlash.append("// ");

  const spanValue = document.createElement("span");
  spanValue.append(value);

  const divLine = document.createElement("div");
  divLine.style.fontFamily = "monospace";
  divLine.style.whiteSpace = "pre";
  divLine.append(spanMessage);
  divLine.append(spanSpace);
  divLine.append(spanSlashSlash);
  divLine.append(spanValue);

  const divLog = document.querySelector("div#log");
  divLog.appendChild(divLine);
}

function logMessage(message1, message2 = undefined) {
  const divLine = document.createElement("div");
  divLine.style.fontFamily = "monospace";
  divLine.style.whiteSpace = "pre";

  const spanMessage1 = document.createElement("span");
  spanMessage1.append(message1);
  divLine.append(spanMessage1);

  if (undefined !== message2) {
    if (message1.length < messageWidth) {
      const spanSpace = document.createElement("span");
      spanSpace.append(" ".repeat(messageWidth - message1.length));
      divLine.append(spanSpace);
    }

    const spanSlashSlash = document.createElement("span");
    spanSlashSlash.append("// ");
    divLine.append(spanSlashSlash);

    const spanMessage2 = document.createElement("span");
    spanMessage2.append(message2);
    divLine.append(spanMessage2);
  }

  const divLog = document.querySelector("div#log");
  divLog.appendChild(divLine);
}

function logSeparator() {
  const divLine = document.createElement("div");
  divLine.style.fontFamily = "monospace";
  divLine.style.whiteSpace = "pre";
  divLine.append("-".repeat(80));

  const divLog = document.querySelector("div#log");
  divLog.appendChild(divLine);
}

// -----------------------------------------------------------------------------

/* ******** *
 * Concepts *
 * ******** */

logMessage("Please make sure you understand these results before moving on");
logValue(`[1,2].toString()`,        [1,2].toString());          // 1,2
logValue(`[3,4].toString()`,        [3,4].toString());          // 3,4
logValue(`{a:1,b:2}.toString()`,    {a:1,b:2}.toString());      // [object Object]
logValue(`{a:3,b:4}.toString()`,    {a:3,b:4}.toString());      // [object Object]
logValue(`[1,2] === [1,2]`,         [1,2] === [1,2]);           // false
logValue(`{a:1,b:2} === {a:1,b:2}`, {a:1,b:2} === {a:1,b:2});   // false
logSeparator();

logMessage("These are keys for the following demonstrations");
const arr45 = [4, 5]; logMessage("const arr45 = [4,5];");
const obj89 = { a: 8, b: 9 }; logMessage("const obj89 = {a:8,b:9};");
logSeparator();

logMessage("Keys of an object are coerced into their string representations");
const m1 = {};      logMessage("const m1 = {};");
m1[-1] = 0;         logMessage("m1[-1] = 0;",           `m1["-1"] = 0`);
m1[0] = 10;         logMessage("m1[0] = 10;",           `m1["0"] = 10`);
m1[10] = 20;        logMessage("m1[10] = 20;",          `m1["10"] = 20`);
m1[[2,3]] = 30;     logMessage("m1[[2,3]] = 30;",       `m1["2,3"] = 30`);
m1[arr45] = 40;     logMessage("m1[arr45] = 40;",       `m1["4,5"] = 40`);
m1[{a:6,b:7}] = 50; logMessage("m1[{a:6,b:7}] = 50;",   `m1["[object Object]"] = 50`);
m1[obj89] = 60;     logMessage("m1[obj89] = 60;",       `m1["[object Object]"] = 60`);
logValue(`m1[-1]`,                  m1[-1]);                    // 0
logValue(`m1["-1"]`,                m1["-1"]);                  // 0
logValue(`m1[0]`,                   m1[0]);                     // 10
logValue(`m1["0"]`,                 m1["0"]);                   // 10
logValue(`m1[10]`,                  m1[10]);                    // 20
logValue(`m1["10"]`,                m1["10"]);                  // 20
logValue(`m1[[2,3]]`,               m1[[2,3]]);                 // 30
logValue(`m1["2,3"]`,               m1["2,3"]);                 // 30
logValue(`m1[[4,5]]`,               m1[[4,5]]);                 // 40
logValue(`m1[arr45]`,               m1[arr45]);                 // 40
logValue(`m1["4,5"]`,               m1["4,5"]);                 // 40
logValue(`m1[{a:6,b:7}]`,           m1[{a:6,b:7}]);             // 60
logValue(`m1[{a:8,b:9}]`,           m1[{a:8,b:9}]);             // 60
logValue(`m1[obj89]`,               m1[obj89]);                 // 60
logValue(`m1["[object Object]"]`,   m1["[object Object]"]);     // 60
logValue(`m1.length`,               m1.length);                 // undefined
logValue(`m1.size`,                 m1.size);                   // undefined
logSeparator();

logMessage("Keys of an array are coerced into their string representations");
const m2 = [];      logMessage("const m2 = [];");
m2[-1] = 0;         logMessage("m2[-1] = 0;",           `m2["-1"] = 0`);
m2[0] = 10;         logMessage("m2[0] = 10;",           `m2["0"] = 10`);
m2[10] = 20;        logMessage("m2[10] = 20;",          `m2["10"] = 20`);
m2[[2,3]] = 30;     logMessage("m2[[2,3]] = 30;",       `m2["2,3"] = 30`);
m2[arr45] = 40;     logMessage("m2[arr45] = 40;",       `m2["4,5"] = 40`);
m2[{a:6,b:7}] = 50; logMessage("m2[{a:6,b:7}] = 50;",   `m2["[object Object]"] = 50`);
m2[obj89] = 60;     logMessage("m2[obj89] = 60;",       `m2["[object Object]"] = 60`);
logValue(`m2[-1]`,                  m2[-1]);                    // 0
logValue(`m2["-1"]`,                m2["-1"]);                  // 0
logValue(`m2[0]`,                   m2[0]);                     // 10
logValue(`m2["0"]`,                 m2["0"]);                   // 10
logValue(`m2[10]`,                  m2[10]);                    // 20
logValue(`m2["10"]`,                m2["10"]);                  // 20
logValue(`m2[[2,3]]`,               m2[[2,3]]);                 // 30
logValue(`m2["2,3"]`,               m2["2,3"]);                 // 30
logValue(`m2[[4,5]]`,               m2[[4,5]]);                 // 40
logValue(`m2[arr45]`,               m2[arr45]);                 // 40
logValue(`m2["4,5"]`,               m2["4,5"]);                 // 40
logValue(`m2[{a:6,b:7}]`,           m2[{a:6,b:7}]);             // 60
logValue(`m2[{a:8,b:9}]`,           m2[{a:8,b:9}]);             // 60
logValue(`m2[obj89]`,               m2[obj89]);                 // 60
logValue(`m2["[object Object]"]`,   m2["[object Object]"]);     // 60
logValue(`m2.length`,               m2.length);                 // 11
logValue(`m2.size`,                 m2.size);                   // undefined
logSeparator();

/* Keys of a Map are NOT coerced into their string representations */
/* When retrieving a value from a Map, the key is compared by reference */
const m3 = new Map();   logMessage("const m3 = new Map();");
m3.set(-1, 0);          logMessage("m3.set(-1, 0);");
m3.set(0, 10);          logMessage("m3.set(0, 10);");
m3.set(10, 20);         logMessage("m3.set(10, 20);");
m3.set([2,3], 30);      logMessage("m3.set([2,3], 30);");
m3.set(arr45, 40);      logMessage("m3.set(arr45, 40);");
m3.set({a:6,b:7}, 50);  logMessage("m3.set({a:6,b:7}, 50);");
m3.set(obj89, 60);      logMessage("m3.set(obj89, 60);");
logValue(`m3.get(-1)`,                  m3.get(-1));                // 0
logValue(`m3.get("-1")`,                m3.get("-1"));              // undefined
logValue(`m3.get(0)`,                   m3.get(0));                 // 10
logValue(`m3.get("0")`,                 m3.get("0"));               // undefined
logValue(`m3.get(10)`,                  m3.get(10));                // 20
logValue(`m3.get("10")`,                m3.get("10"));              // undefined
logValue(`m3.get([2, 3])`,              m3.get([2, 3]));            // undefined
logValue(`m3.get("2,3")`,               m3.get("2,3"));             // undefined
logValue(`m3.get([4, 5])`,              m3.get([4, 5]));            // undefined
logValue(`m3.get(arr45)`,               m3.get(arr45));             // 40
logValue(`m3.get("4,5")`,               m3.get("4,5"));             // undefined
logValue(`m3.get({a:6,b:7})`,           m3.get({a:6,b:7}));         // undefined
logValue(`m3.get({a:8,b:9})`,           m3.get({a:8,b:9}));         // undefined
logValue(`m3.get(obj89)`,               m3.get(obj89));             // 60
logValue(`m3.get("[object Object]")`,   m3.get("[object Object]")); // undefined
logValue(`m3.length`,                   m3.length);                 // undefined
logValue(`m3.size`,                     m3.size);                   // 7
logSeparator();

// -----------------------------------------------------------------------------

/* *************************** *
 * Actual Benchmark: Interface *
 * *************************** */

/**
 * Conceptually equivalent to a dictionary mapping a pair (K1, K2) to V.
 * @template K1 The type of the 1st value of the key pair.
 * @template K2 The type of the 2nd value of the key pair.
 * @template V The type of the element associated with the specified key pair.
 */
class Cache {
  /**
   * Returns a specified element from the Cache object. If the value that is
   * associated to the provided key pair is an object, then you will get a
   * reference to that object and any change made to that object will
   * effectively modify it inside the Cache.
   * 
   * @param {K1} key1 The 1st value of the key pair.
   * @param {K2} key2 The 2nd value of the key pair.
   * @returns {V | undefined} Returns the element associated with the specified
   * key pair. If no element is associated with the specified key pair,
   * undefined is returned.
   */
  get(key1, key2) {
  }

  /**
   * Adds a new element with a specified key pair and value to the Cache.
   * If an element with the same key pair already exists, the element will be
   * updated.
   * 
   * @param {K1} key1 The 1st value of the key pair.
   * @param {K2} key2 The 2nd value of the key pair.
   * @param {V} value The element associated with the specified key pair.
   * @returns {Cache<K1, K2, V>} Returns this Cache object.
   */
  set(key1, key2, value) {
    return this;
  }
}


// -----------------------------------------------------------------------------

/* ********************************** *
 * Actual Benchmark: Implementation 1 *
 * ********************************** */

/**
 * @augments {Cache<K1, K2, V>}
 */
class TwoLevelMapDict {
  constructor() {
    /** @type {Map<K1, Map<K2, V>>} */
    this.map = new Map();
  }

  get(key1, key2) {
    const map2 = this.map.get(key1);
    if (undefined === map2) {
      return undefined;
    }
    return map2.get(key2);
  }

  set(key1, key2, value) {
    let map2 = this.map.get(key1);
    if (undefined === map2) {
      map2 = new Map();
      map2.set(key2, value);
      this.map.set(key1, map2);
    } else {
      map2.set(key2, value);
    }
    return this;
  }
}

// -----------------------------------------------------------------------------

/* ********************************** *
 * Actual Benchmark: Implementation 2 *
 * ********************************** */

/**
 * @augments {Cache<K1, K2, V>}
 */
class TwoLevelArrayDict {
  constructor() {
    /** @type {V[][]} */
    this.map = [];
  }

  get(key1, key2) {
    const map2 = this.map[key1];
    if (undefined === map2) {
      return undefined;
    }
    return map2[key2];
  }

  set(key1, key2, value) {
    let map2 = this.map[key1];
    if (undefined === map2) {
      map2 = [];
      map2[key2] = value;
      this.map[key1] = map2;
    } else {
      map2[key2] = value;
    }
    return this;
  }
}

// -----------------------------------------------------------------------------

/* ********************************** *
 * Actual Benchmark: Implementation 3 *
 * ********************************** */

/**
 * @augments {Cache<K1, K2, V>}
 */
class TwoLevelObjectDict {
  constructor() {
    /** @type {Object.<K1, Object.<K2, V>>} */
    this.map = {};
  }

  get(key1, key2) {
    const map2 = this.map[key1];
    if (undefined === map2) {
      return undefined;
    }
    return map2[key2];
  }

  set(key1, key2, value) {
    let map2 = this.map[key1];
    if (undefined === map2) {
      map2 = {
        key2: value
      };
      this.map[key1] = map2;
    } else {
      map2[key2] = value;
    }
    return this;
  }
}

// -----------------------------------------------------------------------------

/* ********************************** *
 * Actual Benchmark: Implementation 4 *
 * ********************************** */

/**
 * @augments {Cache<K1, K2, V>}
 */
class OneLevelArrayDict {
  constructor() {
    /** @type {V[]} */
    this.map = [];
  }

  get(key1, key2) {
    return this.map[[key1, key2]];
  }

  set(key1, key2, value) {
    this.map[[key1, key2]] = value;
    return this;
  }
}

// -----------------------------------------------------------------------------

/* ********************************** *
 * Actual Benchmark: Implementation 5 *
 * ********************************** */

/**
 * @augments {Cache<K1, K2, V>}
 */
class OneLevelObjectDict {
  constructor() {
    /** @type {Object.<[K1, K2], V>} */
    this.map = {};
  }

  get(key1, key2) {
    return this.map[[key1, key2]];
  }

  set(key1, key2, value) {
    this.map[[key1, key2]] = value;
    return this;
  }
}

// -----------------------------------------------------------------------------

/* *************************** *
 * Actual Benchmark: Algorithm *
 * *************************** */

/**
 * Returns the number of distinct ways that the integer {@link n} could be
 * written as a sum of integers in {@link sortedChoices}[0] (inclusive) to
 * {@link sortedChoices}[{@link k}] (inclusive). Each integer in
 * {@link sortedChoices} could be used zero or more times.
 * @param {number} n The integer.
 * @param {number} k The maximum index in {@link sortedChoices} allowed to be used.
 * @param {number[]} sortedChoices The integer array of choices, sorted in ascending order.
 * @param {Cache<number, number, number} cache The result cache.
 * @returns {number} The number of distinct ways descibed above.
 */
function countWaysToSumImpl(n, k, sortedChoices, cache) {
  let count = cache.get(n, k);
  if (undefined === count) {
    const newN = n - sortedChoices[k];
    // NOTE: The (newN < 0) branch should be unreachable.
    if (newN == 0) {
      count = 1;
    } else {
      count = 0;
      for (let i = 0; i <= k && newN >= sortedChoices[i]; ++i) {
        count += countWaysToSumImpl(newN, i, sortedChoices, cache);
      }
    }
    cache.set(n, k, count);
  }
  return count;
}

/**
 * Returns the number of distinct ways that the integer {@link n} could be
 * written as a sum of integers in {@link choices}. Each integer in
 * {@link choices} could be used zero or more times.
 * @param {number} n The non-negative integer.
 * @param {number[]} choices The array of postive integer choices.
 * @param {Cache<number, number, number} cache The result cache.
 * @returns {number} The number of distinct ways descibed above.
 */
function countWaysToSum(n, choices, cache) {
  // NOTE: If compareFn is ommited, the default one sorts the elements as string.
  const sortedChoices = [...choices];
  sortedChoices.sort((a, b) => a - b);
  let count = 0;
  for (let i = 0; i < sortedChoices.length && n >= sortedChoices[i]; ++i) {
    count += countWaysToSumImpl(n, i, sortedChoices, cache);
  }
  return count;
}

// -----------------------------------------------------------------------------

/* *************************** *
 * Actual Benchmark: Test Case *
 * *************************** */

function randomInt(low, high) {
  if (high < low) {
    throw new Error(`high (${high}) is smaller than low (${low})`);
  }
  return Math.trunc(Math.random() * (high - low + 1)) + low;
}

function randomIntArray(lengthLow, lengthHigh, low, high) {
  if (lengthHigh < lengthLow) {
    throw new Error(`lengthHigh (${lengthHigh}) is smaller than lengthLow (${lengthLow})`);
  }
  if (high < low) {
    throw new Error(`high (${high}) is smaller than low (${low})`);
  }
  const length = randomInt(lengthLow, lengthHigh);
  const array = new Array(length);
  for (let i = 0; i < length; ++i) {
    array[i] = randomInt(low, high);
  }
  return array;
}

function randomIntArrayWithUniqueElements(lengthLow, lengthHigh, low, high) {
  if (lengthHigh < lengthLow) {
    throw new Error(`lengthHigh (${lengthHigh}) is smaller than lengthLow (${lengthLow})`);
  }
  if (high < low) {
    throw new Error(`high (${high}) is smaller than low (${low})`);
  }
  const numberCount = high - low + 1;
  if (lengthLow > numberCount) {
    throw new Error(`lengthLow (${lengthLow}) to high for range (${low} to ${high})`);
  }
  if (lengthHigh > numberCount) {
    lengthHigh = numberCount;
  }
  const size = randomInt(lengthLow, lengthHigh);
  const set = new Set();
  while (size !== set.size) {
    set.add(randomInt(low, high));
  }
  return [...set];
}

const n = randomInt(10, 1000);
const choices = randomIntArrayWithUniqueElements(1, n - 1, 1, n - 1);

Tests:

2-Level Map (Map<K1, Map<K2, V>>)
countWaysToSum(n, choices, new TwoLevelMapDict());
2-Level Array (V[][])
countWaysToSum(n, choices, new TwoLevelArrayDict());
2-Level Object (Object.<K1, Object.<K2, V>>)
countWaysToSum(n, choices, new TwoLevelObjectDict());
1-Level Array (V[])
countWaysToSum(n, choices, new OneLevelArrayDict());
1-Level Object (Object.<[K1, K2], V>)
countWaysToSum(n, choices, new OneLevelObjectDict());

Run results for: Mapping a pair of numbers (2 numbers) to another number [Algorithm 1]

Comparing the performance of different implementations of 2-Tuple cache (mapping a pair of numbers to another number) when being used to achieve memoization a recursive algorithm.

2-Level Map (Map<K1, Map<K2, V>>)

2-Level Array (V[][])

2-Level Object (Object.<K1, Object.<K2, V>>)

1-Level Array (V[])

1-Level Object (Object.<[K1, K2], V>)