Benchmark: graph test - MeasureThat.net

Tests:

array
const graph = Array.from({ length: 101 }, () => []); for (let i = 0; i < 100; i++) { const a=Math.floor(Math.random() * 100) + 1 graph[i].push(a); graph[a].push(i) } for (let i = 0; i < 100; i++) { const a=Math.floor(Math.random() * 100) + 1 const b=Math.floor(Math.random() * 100) + 1 graph[a].push(b) graph[b].push(a) } function dfs(i) { const stack = [i]; const visited = Array.from({ length: 101 }, () => 0); visited[i] = 1; while (stack.length) { const target = stack.pop(); for (let i = 0; i < graph[target].length; i++) { if (!visited[graph[target][i]]) { stack.push(graph[target][i]); visited[graph[target][i]] = 1; } } } } for (let i = 0; i <100; i++) { dfs(i); }
map
class Graph { constructor() { this.list = new Map(); } add(v1, v2) { if (!this.list.has(v1)) this.list.set(v1, []); if (!this.list.has(v2)) this.list.set(v2, []); this.list.get(v2).push(v1); this.list.get(v1).push(v2); } dfs(start) { const stack = [start]; const visited = new Map(); visited.set(start, true); while (stack.length) { const target = this.list.get(stack.pop()); for (let i = 0; i < target.length; i++) { if (!visited.has(target[i])) { stack.push(target[i]); visited.set(target[i], true); } } } return } } const graph = new Graph(); for (let i = 0; i < 100; i++) { graph.add(i, Math.floor(Math.random() * 100) + 1); } for (let i = 0; i < 100; i++) { graph.add(Math.floor(Math.random() * 100) + 1, Math.floor(Math.random() * 100) + 1); } for (const [num, _] of graph.list) { graph.dfs(num); }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
array
map

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/124.0.0.0 Whale/3.26.244.21 Safari/537.36

Browser/OS: Chrome 124 on Windows

View result in a separate tab

Test name	Executions per second
array	1293.4 Ops/sec
map	851.3 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's break down the provided benchmark and explain what is being tested, compared options, pros and cons of those approaches, and other considerations.

**Benchmark Overview**

The benchmark measures the performance of two different data structures: an array and a map (hash table). The test case creates a graph with 101 nodes, each node having multiple connections to other nodes. The graph is then traversed using depth-first search (DFS) algorithm.

**Options Compared**

There are two options being compared:

1. **Array-based implementation**: This approach uses an array to represent the graph, where each element in the array corresponds to a node and its index represents the node's value.
2. **Map-based implementation**: This approach uses a Map data structure to represent the graph, where each key-value pair represents a node and its corresponding value.

**Pros and Cons of Each Approach**

1. **Array-based implementation**
	* Pros:
		+ Easy to implement and understand
		+ Fast access and modification times for nodes with high frequencies
	* Cons:
		+ May lead to poor performance if the graph is sparse (i.e., most nodes have few or no connections)
		+ Node values are stored as indices, which may not be efficient for large datasets
2. **Map-based implementation**
	* Pros:
		+ More efficient for dense graphs (i.e., most nodes have many connections)
		+ Fast lookups and insertions
	* Cons:
		+ May be more complex to implement and understand
		+ More memory-intensive due to the overhead of storing keys and values

**Other Considerations**

1. **Randomization**: The benchmark uses random numbers to create the graph, which helps to ensure that the results are not skewed by specific graph structures.
2. **DFS Algorithm**: The DFS algorithm used in both implementations has a time complexity of O(V + E), where V is the number of nodes and E is the number of edges.
3. **Cache Efficiency**: The cache efficiency of each implementation may vary depending on the size of the input data and the specific hardware.

**Benchmark Results**

The latest benchmark results show that the Map-based implementation outperforms the Array-based implementation in terms of executions per second, with a difference of around 121 seconds.

**Libraries Used**

There is no explicit library mentioned in the Benchmark Definition or test cases. However, it's possible that the `Math` and `Array` libraries are being used implicitly.

**Special JS Features or Syntax**

None of the provided code uses any special JavaScript features or syntax beyond standard JavaScript language constructs.

**Alternatives**

Other data structures that could be tested instead of arrays and maps include:

1. **Linked Lists**: A linked list can be used to represent a graph, but it may not be as efficient as an array-based implementation.
2. **Trie**: A trie (also known as a prefix tree) can be used to store the nodes in a graph, which can be useful for certain types of queries.
3. **Graph Libraries**: Specialized libraries like GraphLib or NetworkX could be used to implement the graph data structure and algorithms.

Keep in mind that this is just an analysis of the provided benchmark, and there may be other factors at play that affect its results.

Related benchmarks:

graph test (version: 0)

Comparing performance of: array vs map

Created: one year ago by: Guest

Jump to the latest result

array

map

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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