haskell长度运行时间O（1）或O（n）

我正在做一个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中。

此外，有没有更好或更有效的写我的代码？

来源

2017-10-12 King Kira

但这不是一个字符串。 –

ArrayList.size（）如何呢？关键是复杂性，而不是具体类型。 – cHao

在编译器优化了这段代码之后，第一个“因素”表达式的评估似乎甚至不涉及构建一个列表。请记住懒惰评估是如何工作的 - 你不是“构建一个列表，然后计算其大小” - 你正在计算列表元素*，因为它们正在被生成*。 –

从理论的角度来看，我们无法知道是否length是θ（N），我们知道这是O（n）的，但它在技术上是可能的，哈斯克尔实现它称为名单更快。

由于Haskell编译器可以自由地以任何方式实现列表。但不过它并不重要，因为在那种情况下生成名单中的第一位将采取θ（n）。即使编译器使用更专用的数据结构

注意，Haskell是懒惰的，所以你的列表理解不会导致一个完整的清单，但更多的功能可以懒洋洋地生成一个列表。

最后，如果我们急于评估列表理解，那么它将再次需要O（n）首先生成列表。因此，即使获得长度非常快，然后生成该列表将需要O（n）作为下限。因此无论length的效率如何，该算法仍将与输入成线性比例。

你自己的实现再次使用O（n）（老实说不是很安全）。不过，你可以很容易地加速比数字的分解，以O（开方N）：

factors :: Int -> Int 
factors x = go 1 
    where 
    go :: Int -> Int 
    go i | i2 > x = 0 
     | i2 == x = 1 
     | mod x i == 0 = 2 + go (i+1) 
     | otherwise = go (i + 1) 
     where i2 = i*i

在这里，我们从1枚举的sqrt（N）。每当我们找到一个因子a时，我们知道有一个co- -factor b = x/a。只要a不等于sqrt（x），我们知道这些是不同的。如果a等于sqrt（x），我们知道a等于b，因此我们将其视为一个。

这就是说，确实有更快的方法来做到这一点。这是一个有很多研究的话题，已经产生了更高效的算法。我并不是说上述速度最快，但它在时间复杂性方面肯定是一个巨大的改进。

来源

2017-10-12 18:09:50

“从理论的角度来看，我们无法知道长度是否为O（n），因为Haskell编译器可以自由地实现列表，无论他们想要什么方式。” 我不认为这取决于编译器。 ['基地的长度]（http://hackage.haskell.org/package/base-4.10.0.0/docs/src/Data.Foldable.html#length）是O（n）。很难想象一个编译器可以优化到一定的时间。 –

@JeffBurka：我同意这不太可能，但要注意（a）'base'是'length'的一个实现;和（b）afaik Haskell报告并没有谈到如何实现某些数据结构和/或优化它们。我绝对同意赔率不太可能。尽管如此，它并不重要，因为构建列表已经具有* O（n）*时间复杂度。 –

@Greg：那是不正确的。例如，“x/2”通常更大。问题是，如果我们看到'2'是一个因素，我们可以同时计算'2'和'x/2'。我们不需要调查大于'sqrt（x）'的可能因素，因为一旦我们到达'sqrt（x）'，我们就知道这些是什么。 –

用列表理解建立列表已经花费了O(n)。因此，在使用长度函数时，没有太多开销，在最坏的情况下应该具有复杂度O(n)。

来源

2017-10-12 18:16:42 mschmidt

此外，有没有更好或更有效的编写我的代码？

整数因式分解是最着名的问题之一。当然，有很多算法提出了这个问题，即使我没有足够的专家来推荐（CS.SE即将发布，并且如果需要的话，可以提供帮助）。这些建议都不是多项式时间，但这并不能阻止它们比平凡的方法更快。即使没有看文献，也可以找到一些简单的优化。

原始代码扫描整个列表[1..x]，但这不是必需的。我们可以在sqrt x停止，因为在那之后不再有除数。
更：之后我们发现一个除数m，我们可以划分x通过m（多次越好），以及与此新号码递归。例如。如果x = 1000在我们尝试m=2之后，我们计算1000 -> 500 -> 250 -> 125，然后在125中找到新的除数（大于2）。请注意这是如何使数字变得更小。

我将离开实现在Haskell这个策略作为一个练习:-P

来源

2017-10-12 18:27:29 chi

威廉·Onsem有一个奇怪的线索，我认为不是易守难攻的参数（在一些“理论”意义上我们可以由于编译器可以自由地优化代码和数据结构，因此不知道length的复杂性）。撇开这是否正确或是埋没的矛盾，我不认为这是解决这类问题的非常有成效的方法。

可以实际上推断的length（和许多其他功能）的复杂性只是看的[a]定义：

Prelude> :info [] 
data [] a = [] | a : [a] -- Defined in ‘GHC.Types’

列表进行电感定义;你可以从该定义中看到（几乎是就是常规haskell），顶层的列表是构造函数[]或:。显然length必须在此结构上递减n次，因此必须是O（n）。

能够以这种方式至少直观地推理非常重要，特别是关于无处不在的列表。例如快速什么是(!!)的复杂性？

如果您想深入了解在懒惰情况下对时间复杂性的正式推理，那么您需要选择由Okasaki提供的“纯功能数据结构”。

来源

2017-10-12 20:46:23 jberryman

haskell长度运行时间O（1）或O（n）

回答

相关问题