performance - 使用无限列表时执行速度较慢

Question

我开始尝试了解 Haskell 的性能，以及是什么让事情变得快和慢，我对此有点困惑。

我有两个函数的实现，可以生成达到特定值的素数列表。第一个直接来自 Haskell wiki:

primesTo :: (Ord a, Num a, Enum a) => a -> [a]
primesTo m = eratos [2..m]  where
   eratos []     = []
   eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..m])

第二个是相同的，但内部使用无限列表:

primes2 :: (Ord a, Num a, Enum a) => a -> [a]
primes2 m = takeWhile (<= m) (eratos [2..])  where
   eratos []     = []
   eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..])

在这两种情况下，减函数都是:

minus :: (Ord a) => [a] -> [a] -> [a]
minus (x:xs) (y:ys) = case (compare x y) of 
           LT -> x : minus  xs  (y:ys)
           EQ ->     minus  xs     ys 
           GT ->     minus (x:xs)  ys
minus  xs _ = xs

后一个实现比前者慢得多(约 100 倍)，我不明白为什么。我本以为 Haskell 的惰性求值会使它们在底层相当等效。

这显然是出于问题目的而减少的测试用例 - 在现实生活中，优化是没有问题的(尽管我不明白为什么需要它)，但对我来说，这是一个只生成无限列表的函数素数比有限列表更有用，但使用起来似乎更慢。

Answer 1

在我看来，两者之间存在很大差异

(xs `minus` [p*p, p*p+p..m])  -- primesTo
(xs `minus` [p*p, p*p+p..])   -- primes2

函数 minus 成对地遍历列表，并在一个列表到达末尾时终止。在上面的第一个 minus 表达式中，当后一个列表耗尽时，这种情况发生在不超过 (m-p*p)/p 步内。在第二个中，它将始终按照 length xs 的顺序执行步骤。

因此，您的无限列表已禁用至少一项有意义的优化。