我正在做一个Haskell任务,我在想办法让我的代码更快。 例如,我的因子函数下面查找某个整数的除数。haskell长度运行时间O(1)或O(n)
factors :: Int -> Int
factors x = length [n | n <- [1..x], mod x n == 0]
但是,我想我可以通过避免使用“长度”来使我的代码更快。
factors :: Int -> Int
factors x = go 1
where
go :: Int -> Int
go i
| i == x = 1
| mod x i == 0 = 1 + go (i + 1)
| otherwise = go (i + 1)
我想知道如果Haskell的长度函数为O(n)等的strlen()的C或O(1)像string.length减()在Java中。
此外,有没有更好或更有效的写我的代码?
但这不是一个字符串。 –
ArrayList.size()如何呢?关键是复杂性,而不是具体类型。 – cHao
在编译器优化了这段代码之后,第一个“因素”表达式的评估似乎甚至不涉及构建一个列表。请记住懒惰评估是如何工作的 - 你不是“构建一个列表,然后计算其大小” - 你正在计算列表元素*,因为它们正在被生成*。 –