我的Fisher-Yates洗牌算法有什么问题吗？

Question

我的Fisher-Yates洗牌算法有什么问题吗？

7

意识到当一些东西看起来太好以至于不真实时，我认为我应该提出这个问题，以便希望能排除任何小精灵。我查看了少数相关的线程，但是我的问题仍然存在。

我相对较新于Haskell，在我的实验中，我编写了一个基本的Fisher-Yates shuffle，如下所示。

shuffle :: RandomGen g => [a] -> g -> ([a],g)
shuffle [] g0 = ([],g0)
shuffle [x] g0 = ([x],g0)
shuffle xs g0 = (x:newtail,g2)
  where (i,g1) = randomR (0, length $ tail xs) g0
        (xs1,x:xs2) = splitAt i xs
        (newtail,g2) = shuffle (xs1++xs2) g1

这个实现在处理大型列表时会占用大量内存，但是速度很快——在我的笔记本电脑上，30M个整数的平均时间为5秒，而标准C++ shuffle的时间为2.3秒。实际上，它比其他Haskell实现要快得多（例如：http://www.haskell.org/haskellwiki/Random_shuffle）。

考虑到我看过的其他Haskell洗牌算法既更复杂又更慢，我想知道这种加速/简化是否只是因为我无所顾忌地使用了更多的内存，还是我错过了一些微小但至关重要的细节，使我的算法有偏差。我没有进行过广泛的测试，但初步的观察似乎显示出一个均匀分布的排列。

我希望有更多Haskell和/或洗牌经验的人对此进行评估。非常感谢所有抽出时间回复的人。

- Tientuinë

2

考虑到这个算法在每次迭代中都要计算列表的长度，我觉得你提供的性能数据难以置信。这是一个O(n^2)的算法。 - Carl

9

你是否在计时算法，而没有强制评估整个结果？ - C. A. McCann

1

展示计时代码。使用该代码对3000万个整数进行完整洗牌需要数天时间。 - Daniel Fischer

5

“我几乎希望能够穿越时空，阻止自己发布这个问题。” 为什么？你从中学到了一些东西，是吧？这是一件好事。（你还从中获得了一些声望，这也不错。）所以你陷入了没有足够考虑懒惰的陷阱，多尴尬——好像这种情况并没有发生在我们大多数人身上。你在这方面有很好的伙伴。 - Daniel Fischer

2

自己摸索出一些东西比被告知要更令人满意？是的，没错。但如果弄清楚需要太长时间，那么就应该寻求帮助。是否会很快自己弄清楚，只有你自己能够判断，如果有人的话。 - Daniel Fischer

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Carl · Accepted Answer

让我们进行一些适当的基准测试。这里有一些代码，其中将您的洗牌重命名为shuffle1，并且我的个人最爱变体被命名为shuffle2。

import System.Random

import Control.Monad

import Control.Monad.ST.Strict
import Data.STRef.Strict

import Data.Vector.Mutable

import Prelude as P

import Criterion.Main


shuffle1 :: RandomGen g => [a] -> g -> ([a], g)
shuffle1 [] g0 = ([],g0)
shuffle1 [x] g0 = ([x],g0)
shuffle1 xs g0 = (x:newtail,g2)
  where (i,g1) = randomR (0, P.length $ P.tail xs) g0
        (xs1,x:xs2) = P.splitAt i xs
        (newtail,g2) = shuffle1 (xs1++xs2) g1


shuffle2 :: RandomGen g => [a] -> g -> ([a], g)
shuffle2 xs g0 = runST $ do
    let l = P.length xs
    v <- new l
    sequence_ $ zipWith (unsafeWrite v) [0..] xs

    let loop g i | i <= 1 = return g
                 | otherwise = do
            let i' = i - 1
                (j, g') = randomR (0, i') g
            unsafeSwap v i' j
            loop g' i'

    gFinal <- loop g0 l
    shuffled <- mapM (unsafeRead v) [0 .. l - 1]
    return (shuffled, gFinal)


main = do
    let s1 x = fst $ shuffle1 x g0
        s2 x = fst $ shuffle2 x g0
        arr = [0..1000] :: [Int]
        g0 = mkStdGen 0
    -- make sure these values are evaluated before the benchmark starts
    print (g0, arr)

    defaultMain [bench "shuffle1" $ nf s1 arr, bench "shuffle2" $ nf s2 arr]

那么，让我们来看一些结果：

carl@ubuntu:~/hask$ ghc -O2 shuffle.hs
[1 of 1] Compiling Main             ( shuffle.hs, shuffle.o )
Linking shuffle ...
carl@ubuntu:~/hask$ ./shuffle 
(1 1,[0, .. <redacted for brevity>])
warming up
estimating clock resolution...
mean is 5.762060 us (160001 iterations)
found 4887 outliers among 159999 samples (3.1%)
  4751 (3.0%) high severe
estimating cost of a clock call...
mean is 42.13314 ns (43 iterations)

benchmarking shuffle1
mean: 10.95922 ms, lb 10.92317 ms, ub 10.99903 ms, ci 0.950
std dev: 193.8795 us, lb 168.6842 us, ub 244.6648 us, ci 0.950
found 1 outliers among 100 samples (1.0%)
variance introduced by outliers: 10.396%
variance is moderately inflated by outliers

benchmarking shuffle2
mean: 256.9394 us, lb 255.5414 us, ub 258.7409 us, ci 0.950
std dev: 8.042766 us, lb 6.460785 us, ub 12.28447 us, ci 0.950
found 1 outliers among 100 samples (1.0%)
  1 (1.0%) high severe
variance introduced by outliers: 26.750%
variance is moderately inflated by outliers

好的，我的系统非常嘈杂，不适合用于类似数字的严格基准测试。但这在这里并不重要。shuffle2 在一个包含1001个元素的列表中大约比shuffle1 快40倍。由于O(n)和O(n^2)之间的差异，在更大的列表中只会增加速度。我相信你测试代码所计时的内容不是洗牌算法。

实际上，我有一个猜测。你的版本足够懒惰，可以逐步返回结果。如果在调用生成器后从未触摸它，那么5秒就是获得前几个结果的合理时间。也许这就是你计时的原因。