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）

回答

相關問題