Benchmark: two sum - MeasureThat.net

Tests:

brute force
var twoSum = function(nums, target) { for(let i=0; i<nums.length; i++) { for(let j=i+1; j<nums.length; j++) { if(nums[i]+nums[j]===target) return [i,j] } } return []; }; twoSum([2,7,11,15], 9)
memo
var twoSum = function(nums, target) { let sol = []; for(let i=0; i<nums.length; i++) { if(sol.length) break; for(let j=i+1; j<nums.length; j++) { if(sol.length) break; if(nums[i]+nums[j]===target) sol = [i,j] } } return sol; } twoSum([2,7,11,15], 9)
hash
var twoSumHash = function (nums, target) { let hashTable = [] let pair = [] let i = 0; let foundPair = false while (i < nums.length) { hashTable[nums[i]] = i i += 1 } i = 0 while (i < nums.length && !foundPair) { let compliment = target - nums [i] if (compliment in hashTable) { if (i !== hashTable[compliment]) { pair.push(i) pair.push(hashTable [compliment]) foundPair = true } } i += 1 } return pair } console.log(twoSumHash([2,7,11,15], 9))

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
brute force
memo
hash

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 3 months ago)

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

Browser/OS: Chrome 132 on Windows

View result in a separate tab

Test name	Executions per second
brute force	57758608.0 Ops/sec
memo	49313092.0 Ops/sec
hash	143626.4 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):

LLMs can make mistakes. Check important info.

I'll break down the benchmark and its test cases for you.

**Benchmark Definition**

The benchmark is defined by a JSON object with the following properties:

* `Name`: The name of the benchmark, which is "two sum".
* `Description`: An empty string, indicating that there is no description provided.
* `Script Preparation Code` and `Html Preparation Code`: Both are null, meaning that no code needs to be executed before running the benchmark.

**Individual Test Cases**

There are three test cases:

1. **Brute Force**
	* The JavaScript function `twoSum` uses two nested loops to iterate over the input array `nums` and find pairs of elements that add up to the target value.
	* The loop iterates from the first element of the array (`i=0`) to the second-to-last element (`j<nums.length-1`). For each pair, it checks if the sum equals the target. If a match is found, the function returns an array containing the indices of the two elements. Otherwise, the function returns an empty array.
	* The test name "brute force" refers to this approach, which involves checking every possible pair of elements in the input array.
2. **Memoization**
	* This JavaScript function `twoSum` uses a technique called memoization to optimize the brute-force approach. It maintains an internal data structure (an array) to store previously computed results for each element in the input array.
	* For each iteration, it first checks if the current element has been seen before and stored in the memo table. If so, it returns the corresponding index from the table. Otherwise, it computes the result as in the brute-force approach and stores the result in the table for future use.
3. **Hashing**
	* This JavaScript function `twoSumHash` uses a hash table to store elements of the input array and their indices.
	* For each iteration, it adds the current element to the hash table with its index as the value. Then, it iterates over the remaining elements and checks if the difference between the target and the current element is present in the hash table. If so, it finds the corresponding index and returns an array containing both indices.
	* The test name "hash" refers to this approach, which uses a data structure (a hash table) to store elements of the input array for efficient lookups.

**Pros and Cons**

Here's a brief summary of the pros and cons of each approach:

1. **Brute Force**
	* Pros: Easy to implement, straightforward.
	* Cons: Exponential time complexity (O(n^2)), not suitable for large inputs.
2. **Memoization**
	* Pros: Reduces time complexity to O(n), can be faster than brute force for large inputs.
	* Cons: Requires additional memory to store the memo table, which may impact performance in other scenarios.
3. **Hashing**
	* Pros: Fast lookups using a hash table, can handle large inputs efficiently.
	* Cons: Requires extra memory to store the hash table, and may not be suitable for small input sizes.

**Other Considerations**

When choosing between these approaches, consider the size of the input array, the computational power available, and the trade-offs between time complexity and memory usage. For very large inputs or performance-critical scenarios, hashing might be a better choice. However, for smaller inputs or development environments where code simplicity is prioritized, brute force or memoization might be more suitable.

**Library Used**

None of these test cases use external libraries. The JavaScript functions are standalone implementations.

**Special JS Features or Syntax**

No special JavaScript features or syntax are used in these examples. They are straightforward vanilla JavaScript implementations.

Related benchmarks:

two sum (version: 0)

Comparing performance of: brute force vs memo vs hash

Created: 2 years ago by: Guest

Jump to the latest result

brute force

memo

hash

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):