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

Mapping a pair of numbers (2 numbers) to another number [Algorithm 1] (version: 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.

Comparing performance of: 2-Level Map (Map<K1, Map<K2, V>>) vs 2-Level Array (V[][]) vs 2-Level Object (Object.<K1, Object.<K2, V>>) vs 1-Level Array (V[]) vs 1-Level Object (Object.<[K1, K2], V>)

Created: 24 days ago by: Registered User

Jump to the latest result

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());

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
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>)

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 24 days ago)

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/OS: Chrome 131 on Mac OS X 10.15.7

View result in a separate tab

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

Autogenerated LLM Summary (model gpt-4o-mini, generated 24 days ago):

LLMs can make mistakes. Check important info.

### Benchmark Overview

The benchmark titled "Mapping a pair of numbers (2 numbers) to another number [Algorithm 1]" focuses on comparing the performance of multiple implementations of a caching mechanism designed to map pairs of numbers (tuples) to a single result. The benchmark aims to assess the efficiency of these implementations when used for memoizing a recursive algorithm—specifically, a solution for counting distinct ways to form a sum using a given set of integers.

### Implementations Compared

The benchmark evaluates five different caching implementations, each using a different underlying data structure:

1. **Two-Level Map (Map<K1, Map<K2, V>>)**
   - Utilizes nested `Map` objects. The outer `Map` holds keys of the first value, each pointing to another `Map` that holds keys of the second value.
   - **Pros:** Efficient key lookups due to hashed keys; offers clear logical separation.
   - **Cons:** Overhead of maintaining multiple maps; potential memory usage could be higher with sparse keys.

2. **Two-Level Array (V[][])**
   - Uses a two-dimensional array where the first index corresponds to the first key and the second to the second key.
   - **Pros:** Lightweight and fast access as arrays have contiguous memory allocations.
   - **Cons:** Inefficient space usage if keys are sparse or if the range of keys is large; not suitable for non-integer keys.

3. **Two-Level Object (Object.<K1, Object.<K2, V>>)** 
   - Uses nested objects where an outer object maps the first key to an inner object mapping the second key to the value.
   - **Pros:** Well-structured; key-value pairs are easy to understand and manipulate; good for small datasets.
   - **Cons:** Potential performance drop due to prototype chain lookups when deeply nested.

4. **One-Level Array (V[])**
   - A single-dimensional array where the composite key (a combination of both values) determines the index.
   - **Pros:** Simple structure, efficient indexing for a known key range.
   - **Cons:** Not scalable for a very large or sparse dataset; difficult to manage composite keys.

5. **One-Level Object (Object.<[K1, K2], V>)**
   - A single object that uses stringified composite keys derived from the two numbers, serving as a unique identifier.
   - **Pros:** Flexible key types; native JavaScript object functionality.
   - **Cons:** Performance hits due to string manipulation for composite keys; potential collisions with more complex key structures.

### Libraries Utilized

- **No external libraries** are utilized in this benchmark, as the implementations rely solely on built-in JavaScript constructs—`Map` and `Object`, which handle data storage and retrieval.

### JavaScript Features Utilized

- **Maps and Objects**: These are essential constructs in JavaScript for maintaining key-value pair data efficiently. The benchmark highlights their use as caching mechanisms. Maps provide ordered iterability and non-string keys, while objects are more traditional and allow for accessing properties through dot or bracket notation.
  
### Alternative Approaches and Considerations

- **Using More Specialized Data Structures**: While this benchmark compares simple combinations (arrays, objects, maps), alternatives could include more specialized data structures such as tries or binary search trees, particularly for varying ranges of keys or when keys are non-integer types.
  
- **Performance Optimization Considerations**: Memory usage varies greatly across implementations. In practice, the choice between these implementations may depend on expected key distributions and access patterns. For instance, a `Map` is generally preferred over an object for larger dynamic datasets due to its performance characteristics in frequent DOM modifications.
  
- **Scalability**: For applications dealing with a wide range of possible key combinations, the scalability of these solutions should be examined closely, especially the `One-Level Array` and `Object` implementations that may run into efficiency problems.

In summary, each of these approaches to caching has its strengths and weaknesses that would cater to different use cases depending on the specific requirements of the application, such as performance, memory consumption, and complexity of key management.

Related benchmarks:

Mapping a pair of numbers (2 numbers) to another number [Algorithm 1] (version: 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.

Comparing performance of: 2-Level Map (Map<K1, Map<K2, V>>) vs 2-Level Array (V[][]) vs 2-Level Object (Object.<K1, Object.<K2, V>>) vs 1-Level Array (V[]) vs 1-Level Object (Object.<[K1, K2], V>)

Created: 24 days ago by: Registered User

Jump to the latest result

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>)

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model gpt-4o-mini, generated 24 days ago):