渔户-耶茨洗牌计划

Question

洗牌列表有很多种方法；例如，Racket的内置shuffle为每个list元素分配一个随机数作为排序键，然后对列表进行排序，这提供了一个O(n log )运行时。然而，我想要的东西是O(n)，这就是费舍-耶茨进来的地方。

Fisher-Yates设计用于随机访问数据结构，如向量.除非首先复制到向量，否则它不会有效地处理列表。这就是我的实现所做的。然而，我在以下几个方面对我的版本进行了微观优化：

1. 我不执行普通交换(val = v[j]; v[j] = v[i-1]; v[i-1] = val)，而只是执行相当于val = v[j]; v[j] = v[i-1]; yield val的操作。在每次迭代时，我都不关心i-1之后向量的值，所以没有必要更新v[i-1]的值。我已经描述了这个实现策略这里。
2. 在将每个被洗牌的值直接累加到结果列表中时，我跳过了vector->list调用。

当然，这些优化是次要的；运行时仍然是O(n)。总之，下面是代码(需要SRFI 27作为random-integer过程)：

(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))))))

我正在寻找使代码更快和/或更优雅的方法，但是正确性和性能是我的首要任务。如果有方法可以在不影响性能或正确性的情况下以更好的风格编写这篇文章，我也很想听听这些。

我的代码最初是用Racket编写的，您也可以对此进行评论：

(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)))

(注意:使用for/fold而不是for/list是一种微观优化:我不在乎洗牌列表是否反转，因此使用for/fold跳过了for/list在幕后使用的reverse步骤。)

Answer 1

你的回答是含蓄的假设：

Racket的内置shuffle为每个list元素分配一个随机数作为排序键，然后对列表进行排序，这将提供一个O( n )运行时。然而，我想要的东西是O(n)，这就是费舍-耶茨进来的地方。

这个假设是，O(n)必然比O(n log )快。我觉得这个案子不是这样的。

考虑到您按名称引用了Racket的shuffle，我想与您的实现相比，我应该使用该函数做一些简单的分析。为了完整起见，我决定对两种洗牌实现进行基准测试。我已经将使用for/fold的版本重命名为fisher-yates-shuffle*。

所有这些过程都对列表进行操作，而且由于它们没有进行任何排序或类似的操作，所以我决定在使用Racket的range函数生成的列表上对它们进行测试。我的测试工具最终看起来是这样的：

(define lst (range 10000))

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

使用Racket的for，结果会被丢弃，所以唯一需要分析的就是算法本身。然后，我使用了以下代码来实际计时这三个过程：

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

我调整了正在被洗牌的列表的长度，以及它被洗牌的次数，通过几种不同的方式来了解算法如何与不同大小的列表交互作用。

我做了一些初步的、相对简单的基准测试，它似乎表明，您的算法基本上从来没有比简单地调整列表更快。这对我来说是不太可能的，因为各种原因，所以我决定优化所有的东西，让你的算法尽可能广泛地发挥我的作用。

我使用Racket的字节码编译器编译了该文件，并在启用所有优化的情况下运行它。以下是我的研究结果：

==============================================================================
|           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 |
==============================================================================

这就对了。现在，fisher-yates-shuffle似乎已经登上了榜首。这似乎有点奇怪，尽管.为什么这一切都突然逆转了，为什么手动循环版本比用于循环的版本快得多呢？

实际上，我意识到还有另外一个因素--随机数发生器。这是一个相当奇怪的因素，甚至有问题。为什么Racket的random会与SRFI 27中的random-integer实现不同呢？答案是:我不知道。

无论是哪种方式，将所有实现规范化为使用random而不是random-integer，我得到了一些稍微不同的时间。

==============================================================================
|           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 |
==============================================================================

显然，这些都不是确凿的证据。尽管如此，我认为可以得出一些有效的结论。

• 实现费舍-耶茨洗牌和默认的shuffle内置到球拍之间的区别是非常微不足道的。我发现，任何用例都不太可能成为所有事情的瓶颈。
• 不同实现之间的性能差异可能很大。方案实际上只是一个标准，而对“方案”的微优化没有真正的意义，除非您有一个可以进行微优化的具体实现。
• 任何基准测试都很可能代表您的排序算法，就像它们代表随机数生成器一样。伪随机数的生成并不是免费的，而且您使用的生成器质量越高，所需的时间就越长。

我的建议？不必为那事担心了。内置的shuffle很好，而且是标准的.使用它。

哦，你的密码？很好，我想。