Haskell风格/效率 [英] Haskell style/efficiency
问题描述
在所有前面的素数中是否有一个因子：
primes1 :: [Integer]
primes1 = mkPrimes id [2 ..]
其中mkPrimes f（x：xs）=
if f（const True）x
then
let ghy = y`mod` x> 0&& hy in
x：mkPrimes（f。g）xs
else
mkPrimes f xs
primes2 :: [Integer]
primes2 = mkPrimes id（const True）[2 ..]
其中mkPrimes f f_（x：xs）=
if f_ x
then
let ghy = y`mod` x> 0&& hy in
x：mkPrimes（f。g）（f $ g $ const True）xs
else
mkPrimes f f_ xs
primes3 :: [Integer]
primes3 = mkPrimes [] [2 ..]
其中mkPrimes ps（x：xs）=
（\ p - > x`mod` p> 0）ps
然后
x：mkPrimes（ps ++ [x]）xs
else
mkPrimes ps xs
因此，在我看来， primes2 应该比 primes1 快一点，因为它避免了重新计算
f_ = f（const True）对于每个整数（我认为需要按数字顺序工作
我们发现迄今为止的素数），并且只在我们遇到新的素数时才会更新它。
仅仅从不科学的测试（运行在ghci中取1000 ）看起来像 primes3 运行得更快
比 primes2 。
我应该从中吸取教训，并假设如果我可以将一个函数表示为数组上的操作
，那么我应该以后者的方式实现它以提高效率，或者是否有其他
其他函数在这里执行？
对于 f 需要的第二个参数是什么？在我看来，这两种替代方法都更具可读性，并且不会显着影响性能......
...
让gy = fy&& y`mod` x> 0 in
x：mkPrimes g xs
...
import Control.Arrow - 实例Monad（ - > r）
import Control.Monad - liftM2
（。& ;.）= liftM2（& amp; $）b $ b ...
let gy = y`mod` x> 0
x：mkPrimes（f。&& g）xs
...
无论如何，回到问题。有时使用函数作为数据结构是某个任务的最佳表示，有时不能。就易于编码和性能方面的最佳而言，最佳并不总是一回事。 作为数据结构的功能技术对运行时编译至关重要，但如该页面警告的那样， / p>
运行时编译有时可以为您带来显着的效率提升，但通常可以赢得几乎没有任何东西，但代价是压力增加和生产力降低。
在你的情况中，构建每个 f :: Integer - > ... - > Bool 远高于构造每个 ps :: [Integer] 的开销，调用时几乎没有差异。 f ... x 与所有... ps 。
为了从无限主素筛中挤出周期，摆脱对 mod 的调用！整数乘法，除法和模数比整数加法和减法慢得多。在我的机器上，当计算前1000个素数（GHC 6.10.3 -O2 ）时，此实现的时钟速度提高了40％。
将合格的Data.Map导入为M
primes':: [Integer]
primes'= mkPrimes 2 M.empty
其中
mkPrimes nm = case（M.null m，M.findMin m）
（False，（n'，skips））| n == n' - >
mkPrimes（succ n）（addSkips n（M.deleteMin m）跳过）
_ - > n：mkPrimes（succ n）（addSkip n m n）
addSkip n m s = M.alter（Just。maybe [s]（s :)）（n + s）m
addSkips = foldl'。 addSkip
在操作中（使用一点JSON-ish语法），
mkPrimes 2 {}
=> 2：mkPrimes 3 {4：[2]}
=> 2：3：mkPrimes 4 {4：[2]，6：[3]}
=> 2：3：mkPrimes 5 {6：[2,3]}
=> 2：3：5：mkPrimes 6 {6：[2,3]，10：[5]}
=> 2：3：5：mkPrimes 7 {8：[2]，9：[3]，10：[5]}
=> 2：3：5：7：mkPrimes 8 {8：[2]，9：[3]，10：[5]，14：[7]}
=> 2：3：5：7：mkPrimes 9 {9：[3]，10：[2,5]，14：[7]}
=> 2：3：5：7：mkPrimes 10 {10：[2,5]，12：[3]，14：[7]}
=> 2：3：5：7：mkPrimes 11 {12：[2,3]，14：[7]，15：[5]}
...
地图会追踪未来的倍数，只会使用加法。
So I was working on a way to lazily generate primes, and I came up with these three definitions, which all work in an equivalent way - just checking whether each new integer has a factor among all the preceding primes:
primes1 :: [Integer]
primes1 = mkPrimes id [2..]
where mkPrimes f (x:xs) =
if f (const True) x
then
let g h y = y `mod` x > 0 && h y in
x : mkPrimes (f . g) xs
else
mkPrimes f xs
primes2 :: [Integer]
primes2 = mkPrimes id (const True) [2..]
where mkPrimes f f_ (x:xs) =
if f_ x
then
let g h y = y `mod` x > 0 && h y in
x : mkPrimes (f . g) ( f $ g $ const True) xs
else
mkPrimes f f_ xs
primes3 :: [Integer]
primes3 = mkPrimes [] [2..]
where mkPrimes ps (x:xs) =
if all (\p -> x `mod` p > 0) ps
then
x : mkPrimes (ps ++ [x]) xs
else
mkPrimes ps xs
So it seems to me primes2 should be a little faster than primes1, since it avoids recomputing
f_ = f (const True) for every integer (which I think requires work on the order of the number
of primes we've found thus far), and only updates it when we encounter a new prime.
Just from unscientific tests (running take 1000 in ghci) it seems like primes3 runs faster
than primes2.
Should I take a lesson from this, and assume that if I can represent a function as an operation on an array, that I should implement it in the latter manner for efficiency, or is there something else going on here?
What's the second argument to the f's needed for? In my opinion, both of these alternatives are more readable, and don't significantly impact performance...
...
let g y = f y && y `mod` x > 0 in
x : mkPrimes g xs
...
import Control.Arrow -- instance Monad (-> r)
import Control.Monad -- liftM2
(.&&.) = liftM2 (&&)
...
let g y = y `mod` x > 0 in
x : mkPrimes (f .&&. g) xs
...
Anyhow, back to the question. Sometimes using functions as data structures is the best representation for a certain task, and sometimes not. "Best" in terms of ease-of-coding and "best" in terms of performance are not always the same thing. The "functions as data structures" technique is essential to runtime compilation, but as that page warns,
Runtime compilation can sometimes win you significant efficiency gains, but can often win you almost nothing at the cost of the your increased stress and reduced productivity.
In your case, it's likely that the overhead of constructing each f :: Integer -> ... -> Bool is significantly higher than the overhead of constructing each ps :: [Integer], with little or no difference when calling f ... x versus all ... ps.
To squeeze cycles out of the infinite prime sieve, get rid of the calls to mod! Integer multiplication, division, and modulus are much slower than integer addition and subtraction. On my machine, this implementation clocks in at 40% faster when calculating the first 1000 primes (GHC 6.10.3 -O2).
import qualified Data.Map as M
primes' :: [Integer]
primes' = mkPrimes 2 M.empty
where
mkPrimes n m = case (M.null m, M.findMin m) of
(False, (n', skips)) | n == n' ->
mkPrimes (succ n) (addSkips n (M.deleteMin m) skips)
_ -> n : mkPrimes (succ n) (addSkip n m n)
addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m
addSkips = foldl' . addSkip
In action (using a bit of JSON-ish syntax),
mkPrimes 2 {}
=> 2 : mkPrimes 3 {4: [2]}
=> 2 : 3 : mkPrimes 4 {4: [2], 6: [3]}
=> 2 : 3 : mkPrimes 5 {6: [2, 3]}
=> 2 : 3 : 5 : mkPrimes 6 {6: [2, 3], 10: [5]}
=> 2 : 3 : 5 : mkPrimes 7 {8: [2], 9: [3], 10: [5]}
=> 2 : 3 : 5 : 7 : mkPrimes 8 {8: [2], 9: [3], 10: [5], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 9 {9: [3], 10: [2, 5], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 10 {10: [2, 5], 12: [3], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 11 {12: [2, 3], 14: [7], 15: [5]}
...
the map keeps track of future multiples, using nothing but addition.
这篇关于Haskell风格/效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
