时间戳

首页 > 解决方案 > ghci 超级慢吗？

haskell - ghci 超级慢吗？

问题描述

以下用于查找低于给定限制的所有完美数字的 Haskell 程序在我的计算机上的 ghci 中执行大约 5-10 秒，n=10000：

 perf :: Int -> Bool 

 perf n = sum [d | d<-[1..div n 2], mod n d==0] == n 

 perfects :: Int -> [Int]

 perfects l = [n | n<-[1..l], perf n ]

为什么执行如此缓慢？

标签： haskell

解决方案

你用来检查一个项目是否是一个完美数字的算法需要线性时间，这意味着你perfects需要二次时间。

您可以通过仅枚举并包括平方根来改进检查项目是否为完美数字的算法。如果我们找到 的除数i，n我们也知道它n/i也是一个除数。因此，我们可以将其实现为：

perf :: Int -> Bool 
perf n = sum [ withco l | l <- ls, mod n l == 0 ] == n - 1
    where ls = takeWhile ((n >=) . (^2)) [ 2 .. ]
          withco i
              | i*i == n = i
              | otherwise = i + div n i

推荐阅读