Benchmark: graph or reduce - MeasureThat.net

Tests:

reduce
let inputData = [ [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [4, 9], [9, 11], [14, 4], [13, 12], [12, 9], ]; const store = new Map(); let a = 3; let b= 8; const getParents = (unit) => { return inputData.reduce((sum, [parent, child]) => { if (unit === child) { sum.add(parent); } return sum; }, new Set()); }; const reduceParents = (parents1, unit = b) => { const isFam = store.get([...parents1, unit].join()); if (typeof isFam === 'boolean') { return isFam; } const parents = getParents(unit); const result = parents?.size ? [...parents1].some((parent) => parents.has(parent)) || [...parents].some((parent) => reduceParents(parents1, parent)) : false; store.set([...parents1, unit].join(), result); return result; }; const isFam = (unit = a) => { const parents = getParents(unit); return parents?.size ? reduceParents(parents) || [...parents].some((parent) => isFam(parent)) : false; }; const result = isFam(); return result;
graph
let inputData = [ [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [4, 9], [9, 11], [14, 4], [13, 12], [12, 9], ]; let a = 3; let b= 8; const graph = {}; inputData.forEach((pair) => { const [parent, child] = pair; if (!graph[child]) { graph[child] = []; } graph[child].push(parent); }); // Function for finding ancestors function findAncestors(node, ancestors) { if (graph[node]) { graph[node].forEach((parent) => { ancestors.push(parent); findAncestors(parent, ancestors); }); } } // Find ancestors for both individuals const ancestorsA = []; const ancestorsB = []; findAncestors(a, ancestorsA); findAncestors(b, ancestorsB); // Check for common ancestors const commonAncestors = ancestorsA.filter((x) => ancestorsB.includes(x)); return commonAncestors.length > 0;

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
reduce
graph

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 years ago)

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

Browser/OS: Chrome 121 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
reduce	184834.0 Ops/sec
graph	1435623.0 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

**Overview**

The provided benchmark definition measures the performance of two different approaches to find common ancestors in a graph data structure: the `graph` approach and the `reduce` approach.

**Graph Approach**

In the `graph` approach, we create an adjacency list representation of the graph using the input data. We then use a recursive function `findAncestors` to traverse the graph and find the ancestors of each individual. The common ancestors are found by filtering the ancestors lists of both individuals.

**Pros**

* Easy to understand and implement
* Does not require additional data structures beyond the input graph

**Cons**

* May be slower due to the recursive function call stack
* Requires manual handling of edge cases, such as disconnected graphs or invalid input data

**Reduce Approach**

In the `reduce` approach, we use the `Map` data structure to store intermediate results and optimize memoization. We define two functions: `getParents` and `reduceParents`. The former returns a set of parents for a given unit (i.e., individual), and the latter checks if a unit is an ancestor of another unit by traversing the graph using `getParents`.

**Pros**

* Efficient use of memoization to optimize performance
* Handles edge cases, such as disconnected graphs or invalid input data

**Cons**

* More complex implementation due to memoization and recursive function calls
* Requires careful handling of data structures and algorithmic details

**Library Usage**

The benchmark definition uses the `Map` data structure from the JavaScript standard library. The `Map` object is used to store intermediate results and optimize memoization in the `reduceParents` function.

**Special JS Feature/Syntax**

There are no special JavaScript features or syntax used in this benchmark definition.

**Other Alternatives**

If you were to reimplement these approaches, you could consider using:

* Iterative algorithms instead of recursive ones
* Using a more efficient data structure, such as a trie or a suffix tree
* Leveraging modern JavaScript features, such as async/await and generators

In summary, the `graph` approach is easier to understand but may be slower due to recursive function calls, while the `reduce` approach is more efficient with memoization but has a more complex implementation.

Related benchmarks:

graph or reduce (version: 0)

Comparing performance of: reduce vs graph

Created: 2 years ago by: Guest

Jump to the latest result

reduce

graph

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):