我正在上一门数学类(class),其中我们必须进行一些整数因式分解作为解决问题的中间步骤。我决定编写一个 Python 程序来为我做这件事(我们没有测试我们的因式分解能力,所以这是完全光明正大的)。程序如下:
#!/usr/bin/env python3
import math
import sys
# Return a list representing the prime factorization of n. The factorization is
# found using trial division (highly inefficient).
def factorize(n):
def factorize_helper(n, min_poss_factor):
if n <= 1:
return []
prime_factors = []
smallest_prime_factor = -1
for i in range(min_poss_factor, math.ceil(math.sqrt(n)) + 1):
if n % i == 0:
smallest_prime_factor = i
break
if smallest_prime_factor != -1:
return [smallest_prime_factor] \
+ factorize_helper(n // smallest_prime_factor,
smallest_prime_factor)
else:
return [n]
if n < 0:
print("Usage: " + sys.argv[0] + " n # where n >= 0")
return []
elif n == 0 or n == 1:
return [n]
else:
return factorize_helper(n, 2)
if __name__ == "__main__":
factorization = factorize(int(sys.argv[1]))
if len(factorization) > 0:
print(factorization)
我也一直在自学一些 Haskell,所以我决定尝试用 Haskell 重写程序。该程序如下:
import System.Environment
-- Return a list containing all factors of n at least x.
factorize' :: (Integral a) => a -> a -> [a]
factorize' n x = smallestFactor
: (if smallestFactor == n
then []
else factorize' (n `quot` smallestFactor) smallestFactor)
where
smallestFactor = getSmallestFactor n x
getSmallestFactor :: (Integral a) => a -> a -> a
getSmallestFactor n x
| n `rem` x == 0 = x
| x > (ceiling . sqrt . fromIntegral $ n) = n
| otherwise = getSmallestFactor n (x+1)
-- Return a list representing the prime factorization of n.
factorize :: (Integral a) => a -> [a]
factorize n = factorize' n 2
main = do
argv <- getArgs
let n = read (argv !! 0) :: Int
let factorization = factorize n
putStrLn $ show (factorization)
return ()
(注意:这需要 64 位环境。在 32 位上,导入 Data.Int
并使用 Int64
作为 read 上的类型注释( argv !! 0)
)
写完这篇文章后,我决定比较两者的性能,认识到有更好的算法,但两个程序使用的算法本质上是相同的。例如,我会执行以下操作:
$ ghc --make -O2 factorize.hs
$ /usr/bin/time -f "%Uu %Ss %E" ./factorize 89273487253497
[3,723721,41117819]
0.18u 0.00s 0:00.23
然后,为 Python 程序计时:
$ /usr/bin/time -f "%Uu %Ss %E" ./factorize.py 89273487253497
[3, 723721, 41117819]
0.09u 0.00s 0:00.09
当然,每次我运行其中一个程序时,时间略有不同,但它们总是在这个范围内,Python 程序比编译的 Haskell 程序快几倍。在我看来,Haskell 版本应该能够运行得更快,我希望你能告诉我如何改进它以实现这种情况。
我看到了一些关于优化 Haskell 程序的技巧,如对 this question 的回答。 ,但似乎无法让我的程序运行得更快。循环比递归快这么多吗? Haskell 的 I/O 是不是特别慢?我在实际实现算法时犯了错误吗?理想情况下,我希望拥有一个仍然相对易于阅读的 Haskell 优化版本
最佳答案
如果您计算 limit = ceiling 。平方。 fromIntegral $ n
只有一次,而不是每次迭代一次,然后我发现 Haskell 版本更快:
limit = ceiling . sqrt . fromIntegral $ n
smallestFactor = getSmallestFactor x
getSmallestFactor x
| n `rem` x == 0 = x
| x > limit = n
| otherwise = getSmallestFactor (x+1)
使用这个版本,我看到:
$ time ./factorizePy.py 89273487253497
[3, 723721, 41117819]
real 0m0.236s
user 0m0.171s
sys 0m0.062s
$ time ./factorizeHs 89273487253497
[3,723721,41117819]
real 0m0.190s
user 0m0.000s
sys 0m0.031s
关于python - Haskell 在朴素整数分解中比 Python 慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40622907/