Fisher-Yates shuffle in Scheme
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.