Benchmark: Fisher-Yates Shuffle

Script Preparation code:

// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random#getting_a_random_integer_between_two_values_inclusive
function getRandomIntInclusive(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min + 1) + min); //The maximum is inclusive and the minimum is inclusive
}

function shuffleOliver(array) {
    let current;
    let top;
    let tmp = (current = top = array?.length);

    if (!top) {
        return array;
    }

    while (--top) {
        current = getRandomIntInclusive(0, top);
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }
    return array;
};

function shuffleAndrea(array) {
    let {length} = array;
    while (length--) {
        let i = getRandomIntInclusive(0, length);
        [array[i], array[length]] = [array[length], array[i]];
    }
    return array;
};

function shuffleNikolay(array) {
    const t = array.splice(0, array.length);
    while (t.length > 0) {
        const index = getRandomIntInclusive(0, t.length - 1);
        array.push(t.splice(index, 1)[0]);
    }
    return array;
};

window.array_10000 = Array.from(Array(10000).keys());

Tests:

Nikolay
shuffleNikolay(window.array_10000);
Oliver
shuffleOliver(window.array_10000);
Andrea
shuffleAndrea(window.array_10000);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Nikolay
Oliver
Andrea

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

Browser/OS: Chrome 134 on Windows

View result in a separate tab

Test name	Executions per second
Nikolay	30.0 Ops/sec
Oliver	8946.1 Ops/sec
Andrea	8424.7 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's being tested.

**Benchmark Definition**

The benchmark definition json provides a JavaScript function to shuffle an array using three different approaches:

1. `shuffleNikolay(array)`: This function shuffles the array by first creating a copy of the original array, then repeatedly popping elements from the end of the copied array and pushing them to the beginning.
2. `shuffleOliver(array)`: This function uses a custom shuffle algorithm that iterates through the array from right to left, swapping each element with a random element from the remaining unshuffled portion of the array.
3. `shuffleAndrea(array)`: This function shuffles the array by repeatedly iterating through the array and swapping adjacent elements.

**Options being compared**

The three shuffle algorithms are being compared to determine which one is the most efficient in terms of time complexity (i.e., how fast it executes).

**Pros and Cons of each approach:**

1. `shuffleNikolay(array)`: This approach has a time complexity of O(n), where n is the length of the array, making it relatively efficient.
	* Pros: Simple implementation, easy to understand.
	* Cons: Creates an extra copy of the original array, which can be memory-intensive for large arrays.
2. `shuffleOliver(array)`: This approach has a time complexity of O(n), where n is the length of the array, making it relatively efficient.
	* Pros: No extra copies are created, making it more memory-efficient than `shuffleNikolay`.
	* Cons: The algorithm is more complex and harder to understand due to its custom implementation.
3. `shuffleAndrea(array)`: This approach has a time complexity of O(n), where n is the length of the array, making it relatively efficient.
	* Pros: Simple implementation, easy to understand.
	* Cons: Similar to `shuffleNikolay`, this approach creates an extra copy of the original array.

**Library usage**

None of the provided functions use any external libraries. However, the `Math.random()` function is used throughout the benchmark definition and individual test cases.

**Special JS features or syntax**

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

**Other alternatives**

If an alternative implementation were needed, other shuffle algorithms could be considered, such as:

* Fisher-Yates shuffle (already implemented in the benchmark)
* Knuth's shuffle algorithm
* Randomized permutation

However, it's worth noting that these alternatives may not offer significant performance improvements over the existing implementations.

In summary, this benchmark tests three different shuffle algorithms and compares their execution times to determine which one is the most efficient. The `shuffleNikolay` and `shuffleAndrea` approaches are relatively simple but create an extra copy of the original array, while the `shuffleOliver` approach is more complex but does not create any extra copies.

Related benchmarks:

Fisher-Yates Shuffle (version: 0)

Test implementations from https://twitter.com/oliverjumpertz/status/1434779862955405313

Comparing performance of: Nikolay vs Oliver vs Andrea

Created: 4 years ago by: Registered User

Jump to the latest result

Nikolay

Oliver

Andrea

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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