代码之家  ›  专栏  ›  技术社区  ›  Jihyun

整合功能要慢得多

  •  6
  • Jihyun  · 技术社区  · 7 年前

    我写了isPrime函数。它检查给定的数字是否为素数。 最后一个“基本”列表单独给出。

    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..]
    

    iPrime 40000000000000000001

    isPrime2 40000000000000000001

    =>19.8秒

    我的机器是Ubuntu 17.10 x86-64。我正在使用ghc 8.2.1。有人知道为什么吗?

    1 回复  |  直到 7 年前
        1
  •  6
  •   chi    7 年前

    第一个代码段将只保留一个 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 ,但不会因为内心的每一次呼唤而导致爆炸 isPrime 将共享相同的列表 首要的 s