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

Oliver

9K/s

Andrea

8K/s

Nikolay

30/s

View exact numbers

Test name	Executions per second
✓ Oliver	8,946 Ops/sec
Andrea	8,425 Ops/sec
Nikolay	30 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.

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

Go 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):

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

Go 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):

Related benchmarks

Comparing performance of: `Nikolay vs Oliver vs Andrea`