Fisher-Yates shuffle in Scheme

Question

There are many ways to shuffle lists; for example, Racket's built-in shuffle assigns each list element with a random number as a sort key, then sorts the list, which provides an O(n log n) runtime. However, I'd like something that's O(n), and that's where Fisher-Yates comes in.

Fisher-Yates is designed for use with random-access data structures, like vectors. It will not behave efficiently for lists, unless copied to a vector first. That's what my implementation does. However, I micro-optimised my version in a couple of ways:

1. Instead of doing the normal swap (val = v[j]; v[j] = v[i-1]; v[i-1] = val), I simply do the equivalent of val = v[j]; v[j] = v[i-1]; yield val. I don't care about the values of the vector after i-1 at each iteration, so there's no point in updating the value of v[i-1]. I've described this implementation strategy here.

2. In accumulating each shuffled value into the result list directly, I skip the vector->list call.

Of course, these optimisations are minor; the runtime is still O(n). Anyway, here's the code (requires SRFI 27 for the random-integer procedure):

(define (fisher-yates-shuffle lst)
  (define vec (list->vector lst))
  (let loop ((result '())
             (i (vector-length vec)))
    (if (zero? i)
        result
        (let* ((j (random-integer i))
               (val (vector-ref vec j)))
          (vector-set! vec j (vector-ref vec (- i 1)))
          (loop (cons val result) (- i 1))))))

I'm looking for ways to make the code faster and/or more elegant, but correctness and performance are my top priorities. If there are ways to write this in a better style without impacting performance or correctness, I'd love to hear about those too.

---

My code was initially written in Racket, which you're welcome to critique too:

(define (fisher-yates-shuffle lst)
  (define vec (list->vector lst))
  (for/fold ((result '()))
            ((i (in-range (vector-length vec) 0 -1)))
    (define j (random i))
    (define val (vector-ref vec j))
    (vector-set! vec j (vector-ref vec (sub1 i)))
    (cons val result)))

(Note: using for/fold instead of for/list is a micro-optimisation: I don't care if the shuffled list is reversed, so using for/fold skips the reverse step that for/list uses behind the scenes.)

Answer 1

Your answer makes an implicit assumption:

Racket's built-in shuffle assigns each list element with a random number as a sort key, then sorts the list, which provides an O(n log n) runtime. However, I'd like something that's O(n), and that's where Fisher-Yates comes in.

That assumption is that O(n) will necessarily be faster than O(n log n). I don't think that's true for this particular case.

Considering you referenced Racket's shuffle by name, I figured I'd do some simple profiling using that function compared to your implementation. Just for completeness, I decided to benchmark both of your shuffle implementations. I've renamed the version that uses for/fold to fisher-yates-shuffle*.

All of these procedures operate on lists, and since they're not doing any sorting or anything like that, I just decided to test them on lists generated using Racket's range function. My test harness ended up looking like this:

(define lst (range 10000))

(define (shuffle-lst shuffle-proc)
  (for ([i (in-range 10000)])
    (shuffle-proc lst)))

Using Racket's for, the result is discarded, so the only thing being profiled is the algorithm itself. I then used the following code to actually time the three procedures:

(time (shuffle-lst shuffle))
(time (shuffle-lst fisher-yates-shuffle))
(time (shuffle-lst fisher-yates-shuffle*))

I adjusted the length of the list being shuffled as well as the number of times it was shuffled in a few different ways to figure out how the algorithms interacted with different sizes of lists.

I did some initial, relatively simple benchmarking, and it seemed to indicate that your algorithm was basically never faster than simply shuffling a list. This seemed unlikely to me for a variety of reasons, so I decided to optimize everything to give your algorithm as wide a benefit as I could possibly give it.

I compiled the file using Racket's bytecode compiler and ran it with all optimizations enabled. Here were my results:

==============================================================================
|           list length |       100 |   1,000 | 10,000 | 100,000 | 1,000,000 |
|-----------------------|-----------|---------|--------|---------|-----------|
|       loop iterations | 1,000,000 | 100,000 | 10,000 |   1,000 |       100 |
|=======================|===========|=========|========|=========|===========|
|               shuffle |    11,585 |  11,929 | 12,020 |  12,394 |    16,119 |
|-----------------------|-----------|---------|--------|---------|-----------|
|  fisher-yates-shuffle |     9,676 |   9,816 |  9,888 |  10,730 |    13,285 |
|-----------------------|-----------|---------|--------|---------|-----------|
| fisher-yates-shuffle* |    10,738 |  11,112 | 11,162 |  11,895 |    14,978 |
==============================================================================

There we go. Now fisher-yates-shuffle seems to be coming out on top. That seems sort of odd, though... why did it all suddenly reverse, and why is the manual loop version so much faster than the one using for loops?

Actually, I realized there was another factor in play—the random number generator. This is a rather odd factor to even matter at all. Why would Racket's random be different from its own implementation of random-integer from SRFI 27? The answer is: I don't know.

Either way, normalizing all the implementations to use random instead of random-integer, and I got some slightly different times.

==============================================================================
|           list length |       100 |   1,000 | 10,000 | 100,000 | 1,000,000 |
|-----------------------|-----------|---------|--------|---------|-----------|
|       loop iterations | 1,000,000 | 100,000 | 10,000 |   1,000 |       100 |
|=======================|===========|=========|========|=========|===========|
|               shuffle |    12,191 |  12,178 | 11,497 |  12,733 |    16,763 |
|-----------------------|-----------|---------|--------|---------|-----------|
|  fisher-yates-shuffle |    11,313 |  11,601 | 10,831 |  12,559 |    16,002 |
|-----------------------|-----------|---------|--------|---------|-----------|
| fisher-yates-shuffle* |    11,441 |  11,269 | 10,814 |  12,716 |    15,766 |
==============================================================================

Obviously, none of this is conclusive evidence one way or the other. That said, I think some valid conclusions can be drawn.

• The difference between your implementation of the Fisher-Yates shuffle and the default shuffle built-in to Racket is pretty trivial. I find it unlikely that any use-case would have shuffling as a bottleneck, of all things.
• The performance differences likely vary wildly across implementations. Scheme is really just a standard, and micro-optimizing for "Scheme" doesn't really make sense unless you have a specific implementation you can micro-optimize for.
• Any benchmarks are just as likely to be representative of your sorting algorithm as they are of your random number generator. Pseudorandom number generation is not free, and the higher quality generator you use, the more time it will take.

My advice? Don't worry about it. The built-in shuffle is fine, and it's standard. Use it.

---

Oh, your code? It's fine, I guess.