如何优化此随机播放功能？

Question

我正在尝试使用 Haskell 创建一个通用的（type-o-polymophism？）洗牌函数。我需要在几分之一秒内对几千个元素进行排序才能被视为 "good enough"。

evens :: [a] -> [a]
evens l = [l !! i | i <- [0,2..(length l) - 1]]

odds :: [a] -> [a]
odds  l = [l !! i | i <- [1,3..(length l) - 1]]

shuffle :: [a] -> [a]
shuffle s   | length s == 1 = s
        | otherwise = l ++ shuffle r
        where l = evens s
              r = odds s

Answer 1

一个完美的洗牌可以实现为

perfectShuffle = concat . transpose . chunksOf 2

速度提升将来自：

没有重复计算列表的长度。
不会低效地构建 (++) 链，这将需要重复遍历列表并给出 O(n²) 运行时间。

示例输出：

λ> perfectShuffle [1..10]
[1,3,5,7,9,2,4,6,8,10]

chunksOf 在 split 包中可用。 transpose 在 Data.List 中。

Answer 2

您应该避免像在

中那样使用 !! 重复索引到同一个列表

evens l = [l !! i | i <- [0,2..(length l) - 1]]    -- bad

这需要 O(n^2) 时间，其中 n 是 l 的长度，因为 l !! i 需要 O(i) 时间。

而是写这样的东西：

evens [] = []
evens (x:xs) = x : odds xs

odds xs = evens (drop 1 xs)

你的 shuffle 本身没问题。

如何优化此随机播放功能？

How can I optimize this shuffle function?

haskell

shuffle