合并功能要慢得多
consolidated function is much slower
我写了 isPrime 函数。它检查给定数字是否为素数。
最后一个"prime"列表单独给出
prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime
我认为如果可能的话,将两个函数合并为一个总是更好..所以我将 isPrime 和 prime 合并为一个函数 isPrime2。但是isPrime2的性能很差。
isPrime2 :: Integer -> Bool
isPrime2 n | n < 2 = False
isPrime2 n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : filter isPrime2 [3..]
isPrime 40000000000000000001
=> 0.5 秒
isPrime2 40000000000000000001
=> 19.8 秒
我的机器是 Ubuntu 17.10 x86-64。我正在使用 ghc 8.2.1。有谁知道为什么?
第一个片段将只在内存中保留一个 prime
列表。
第二个代码段将计算自己的 prime
,直到 n^2
每次 isPrime2
被调用。以前发现的素数在每次调用时都会被丢弃并从头开始重新计算。
由于 isPrime2
是递归的,这会导致爆炸。
中间方法可以是这个:
isPrime2 :: Integer -> Bool
isPrime2 m = isPrime m
where
prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime
这将在每次调用 isPrime2
时重新计算 prime
,但不会导致爆炸,因为内部 isPrime
的每次调用都将共享相同的 prime
s.
我写了 isPrime 函数。它检查给定数字是否为素数。 最后一个"prime"列表单独给出
prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime
我认为如果可能的话,将两个函数合并为一个总是更好..所以我将 isPrime 和 prime 合并为一个函数 isPrime2。但是isPrime2的性能很差。
isPrime2 :: Integer -> Bool
isPrime2 n | n < 2 = False
isPrime2 n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : filter isPrime2 [3..]
isPrime 40000000000000000001
=> 0.5 秒
isPrime2 40000000000000000001
=> 19.8 秒
我的机器是 Ubuntu 17.10 x86-64。我正在使用 ghc 8.2.1。有谁知道为什么?
第一个片段将只在内存中保留一个 prime
列表。
第二个代码段将计算自己的 prime
,直到 n^2
每次 isPrime2
被调用。以前发现的素数在每次调用时都会被丢弃并从头开始重新计算。
由于 isPrime2
是递归的,这会导致爆炸。
中间方法可以是这个:
isPrime2 :: Integer -> Bool
isPrime2 m = isPrime m
where
prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime
这将在每次调用 isPrime2
时重新计算 prime
,但不会导致爆炸,因为内部 isPrime
的每次调用都将共享相同的 prime
s.