Benchmark: grouping anagrams

Script Preparation code:

var arr = ['cook', 'eat', 'ate', 'cat', 'cat', 'save', 'vase', 'state', 'taste'];

Tests:

looping to compare properties
const objStr = {}; for (const str of arr) { const strCount = {}; for (const letter of str) { strCount[letter] = (strCount[letter] || 0) + 1; } objStr[str] = strCount; } const result = []; for (const str of arr) { let indexed = null; for (const grouped of result) { const [indexedStr] = grouped; if (str.length !== indexedStr.length) { continue; } const strCount = objStr[str]; const indexedCount = objStr[indexedStr]; let isAnagram = true; for (const letter in indexedCount) { if (strCount[letter] !== indexedCount[letter]) { isAnagram = false; break; } } if (isAnagram) { indexed = grouped; break; } } if (!indexed) { result.push([str]); } else { indexed.push(str); } }
less loop but with char code and json stringify
const objStr = {}; for (const str of arr) { const strCount = {}; for (const letter of str) { const charCode = letter.charCodeAt(0); strCount[charCode] = (strCount[charCode] || 0) + 1; } const strCodes = JSON.stringify(strCount); if (objStr[strCodes]) { objStr[strCodes].push(str); } else { objStr[strCodes] = [str]; } } const hasil = Object.values(objStr);
using sort
const sorted = arr.map((s) => s.split('').sort().join('')); const result = Object.values(sorted.reduce((o, s, i) => (o[s]?.push(arr[i]) || (o[s] = [arr[i]]), o), {}));

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
looping to compare properties
less loop but with char code and json stringify
using sort

Fastest: N/A

Slowest: N/A

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

LLMs can make mistakes. Check important info.

The provided benchmark measures the performance of different approaches to solve an anagram grouping problem. Anagrams are words or phrases formed by rearranging the letters of another word or phrase, typically using all the original letters exactly once.

Let's break down each individual test case:

1. "looping to compare properties":

This approach uses two nested loops to compare the properties (i.e., character counts) of each string in the input array (`arr`) with the corresponding string in the `objStr` object. The loop iterates through the strings, creates a count of each letter's frequency using another inner loop, and then updates the `objStr` object accordingly.

Pros:

* Easy to understand and implement.
* Does not require any specialized data structures or libraries.

Cons:

* Has a high time complexity due to the nested loops, resulting in slower performance compared to other approaches.

2. "less loop but with char code and json stringify":

This approach uses a single loop that iterates through each string in the input array. For each string, it calculates its character codes using `charCodeAt(0)` and then uses `JSON.stringify` to convert these codes into a unique string (`strCodes`). The resulting string is used as a key in the `objStr` object to group matching strings together.

Pros:

* Reduces the number of loops compared to the first approach.
* Uses built-in functions like `JSON.stringify`, which can provide some performance benefits.

Cons:

* Requires an additional loop to process each character's code, which still results in slower performance compared to more optimized approaches.

3. "using sort":

This approach uses the `Array.prototype.sort` method to sort the input array based on the sorted version of each string (`sorted`). The resulting array is then flattened and used as a base for grouping matching strings together using another object (`result`).

Pros:

* Can provide good performance due to the optimized sorting algorithm.
* Eliminates the need for explicit loops, making it easier to maintain.

Cons:

* Requires the input array to be sorted, which can introduce additional overhead.
* The use of `sort` may not always lead to optimal grouping results if the input data is not well-suited for this approach.

Now, let's discuss some other alternatives that could have been considered:

* Using a more advanced data structure like a Trie (prefix tree) or a suffix tree, which can provide efficient prefix matching and anagram detection.
* Implementing a sorting-based approach using a more optimized algorithm, such as counting sort or radix sort.
* Utilizing parallel processing techniques to take advantage of multiple CPU cores.
* Using specialized libraries or modules that optimize string operations, like `string-similarity` or `anagram-filter`.

Regarding the libraries used in these benchmarks, none are explicitly mentioned. However, if we were to identify some potential dependencies based on the code:

* The use of `charCodeAt(0)` suggests that JavaScript's built-in string methods and primitive types might be sufficient for this benchmark.
* The reliance on `JSON.stringify` implies that JavaScript's serialization mechanism could provide an additional performance boost.

Specialized features or syntax used in these benchmarks include:

* String iteration using loops (`for...of`, `for...in`)
* Object property access and updates (`objStr[str] = ...;`)
* Use of the `||` operator for conditional assignment
* Use of object destructuring (`const [indexedStr] = grouped;`)

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/102.0.0.0 Safari/537.36

Browser/OS: Chrome 102 on Windows

View result in a separate tab

Test name	Executions per second
looping to compare properties	142021.7 Ops/sec
less loop but with char code and json stringify	28620.7 Ops/sec
using sort	76517.1 Ops/sec

Related benchmarks:

grouping anagrams (version: 0)

Comparing performance of: looping to compare properties vs less loop but with char code and json stringify vs using sort

Created: one year ago by: Guest

Jump to the latest result

looping to compare properties

less loop but with char code and json stringify

using sort

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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