haskellの長さランタイムO（1）またはO（n）

Question

私はHaskellの割り当てに取り組んでいました。私はコードを高速化する方法を考えていました。 たとえば、以下のmyファクタ関数は、整数の除数の数を求めます。

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の長さの関数（1）は、JavaでString.lengthです（）のようなCでSTRLENようなO（n）は（）またはOである場合、私は思っていました。

また、自分のコードを書く方が効率的か、効率的ですか？

Answer 1

理論的な観点から、我々はlengthがθ（n）がであるかどうかを知ることができない、我々はそれがO（n）のであることを知っているが、Haskellはより速く、既知のリストのためにそれを実装することを技術的に可能です。

Haskellコンパイラは、自由に任意の方法でリストを実装できます。しかし、それにもかかわらず、は、とは関係ありません。この場合は、を生成するので、最初はθ（n）となります。コンパイラはそれ以上の専用データ構造を使用している場合でも

注意、Haskellはので、あなたのリストの内包は完全なリストにはなりませんが、より多くの機能ではなまけリストを生成することができることを、怠惰です。

最後に、リストの理解度を熱心に評価すると、まずリストを最初に生成するにはO（n）が必要です。したがって、長さを得ることが非常に速かったとしても、リストを生成するには、下限としてO（n）が必要です。したがって、lengthの効率がどのようなものであっても、アルゴリズムは入力に対して線形にスケーリングされます。

独自の実装では、O（n）を再度使用します（正直に言うとあまり安全ではありません）。それにもかかわらず、あなたは簡単にO（SQRT 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 

ここでは、（n）はSQRTに1から列挙する。係数aが見つかるたびに、co -factor b = x/aがあることがわかります。 aがsqrt（x）と等しくない限り、それらは異なることがわかります。 aがsqrt（x）に等しい場合、aはbと等しく、従ってこれを1と数えます。

言われていることは間違いなく速い方法があるということです。これは、より効率的なアルゴリズムをもたらした多くの研究の話題です。私は上記が最速であることを示唆しているわけではありませんが、それは間違いなく時間の複雑さの面で大きな改善です。

Answer 2

リストの理解度を持つリストを構築するには、すでにO(n)が必要です。したがって、最悪の場合、複雑さがあるべきである長さ関数O(n)を使用する場合、オーバーヘッドはあまりありません。

Answer 3

さらに、私のコードを書く方が効率的か、効率的ですか？

整数分解は、最も有名な問題の1つです。私が推薦をするのに十分な専門家でなくても（CS.SEはすぐそばにあり、必要に応じて助けてくれるかもしれませんが）、確かにそのためのアルゴリズムがたくさん提案されています。そのような提案のどれも多項式時間ではありませんが、これは些細なアプローチよりも速くなることを止めるものではありません。

文献を見ることなく、いくつかの簡単な最適化を見つけることができます。

• 元のコードはリスト全体をスキャンします[1..x]しかし、これは必要ありません。私たちはsqrt xで止めることができました。それ以降、除数はなくなりました。

• さらに：私たちは除数mを見つけた後、私たちはm（できるだけ多くの回数）によってxを分割し、この新しい番号で再帰性があります。例えば。 x = 1000m=2を試した後、1000 -> 500 -> 250 -> 125を計算し、125に新しい除数（2より大きい）を見つけます。これがどのようにして数字をはるかに小さくしたかに注意してください

私は運動:-P

Answer 4

ウィレム・ヴァン・Onsemは奇妙につながり、私は簡単に防御ない引数（いくつかの「理論」の意味で私たちができることを考えるとHaskellでこの戦略を実行残しますコンパイラはコードとデータ構造を自由に最適化できるので、lengthの複雑さを知ることはできません）。それが正しかったのか埋葬された矛盾なのかを除いて、私はそれがこの種の問題に近づくには非常に有益な方法だとは思わない。

あなたは実際にちょうど[a]の定義を見て、lengthの複雑さ（および他の多くの機能）を推測することができます。

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

リストは、誘導定義されています。 （ほぼちょうど普通のhaskellです）そのトップレベルでは、リストがコンストラクタ[]または:のいずれかであることがわかります。明らかにlengthはこの構造上でn回繰り返す必要があり、したがってO（n）でなければならない。

このように少なくとも直感的には、特にユビキタスなリストについては、理にかなっていることが非常に重要です。例えば素早く何が(!!)の複雑さですか？

怠惰の中で時間の複雑さを正式に推論するには、岡崎が「純粋に機能的なデータ構造」を取り上げる必要があります。