计算最小除数的两个替代函数的性能

Question

在这本书中" 哈斯克尔道逻辑,数学和编程 ",目前找到最小除数的两种替代方式作者k一批n有k > 1,声称第二个版本比第一个要快得多.我有理解为什么(我是初学者)的问题.

这是第一个版本(第10页):

ld :: Integer -> Integer -- finds the smallest divisor of n which is > 1
ld n = ldf 2 n

ldf :: Integer -> Integer -> Integer
ldf k n | n `rem` k == 0 = k
        | k ^ 2 > n      = n
        | otherwise      = ldf (k + 1) n

如果我理解正确的话,ld函数基本上会迭代遍历区间中的所有整数,[2..sqrt(n)]并在其中一个分割n后立即停止,并将其作为结果返回.

第二个版本,作者声称要快得多,就像这样(第23页):

ldp :: Integer -> Integer -- finds the smallest divisor of n which is > 1
ldp n = ldpf allPrimes n

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p
              | p ^ 2 > n    = n
              | otherwise    = ldpf ps n

allPrimes :: [Integer]
allPrimes = 2 : filter isPrime [3..]

isPrime :: Integer -> Bool
isPrime n | n < 1     = error "Not a positive integer"
          | n == 1    = False
          | otherwise = ldp n == n

作者声称这个版本更快,因为它只通过区间内的素数列表2..sqrt(n)进行迭代,而不是迭代该范围内的所有数字.

然而,这个论点并没有让我信服:递归函数ldpf逐个吃掉素数列表中的数字allPrimes.通过filter对所有整数列表进行操作来生成此列表.

因此,除非我遗漏了某些内容,否则第二个版本最终会遍历区间内的所有数字2..sqrt(n),但是对于每个数字,它首先检查它是否为素数(相对昂贵的操作),如果是,则检查它是否分开n(a比较便宜的).

我要说的是,只检查是否k分裂n为每个k应该会更快.我的推理中的缺陷在哪里？

Answer 1

第二种解决方案的主要优点是您只计算allPrimes一次素数列表.由于延迟评估,每个调用只计算它需要的素数,或者重用已经计算过的素数.因此,昂贵的部分只计算一次,然后重新使用.

为了计算仅一个数字的最小除数,第一个版本确实更有效.但是尝试运行,ldp并且ld对于所有数字,假设1和100000,你会看到差异.