如何在Haskell中優化此代碼

我需要您的幫助來優化。這裏是問題：如何在Haskell中優化此代碼

什麼是最小的（嚴格爲正）自然數是不可能獲得的10倍數3，結合常用算術運算符？

這裏是我的解決方案：

import Ratio 

num x 1 = [x] 
num x n = num'' $ concat $ [ num' a b | i <- [1..n`quot`2], a <- num x i, b <- num x (n-i) ] 
    where num' a b | a==0  = [b] 
        | b==0  = [a] 
        | otherwise = [a+b,abs(a-b),a*b,a/b,b/a] 
     num'' (x:r) = x : num'' (filter (x/=) r) 
     num'' _  = [] 

cint x = map numerator . filter ((1==) . denominator) . num x 

firstNumber x n = take 1 [ i | i <- [1..], i `notElem` (cint x n) ]

但它是如此低效。例如，當我撥打firstNumber 3 7時，需要將近30秒才能看到結果。但是，我還沒有看到firstNumber 3 10的結果，雖然我已經等了很長時間了。我怎樣才能優化它？

來源

2014-06-04 sasas

您是否通過優化編譯了它？另外，你能解釋一下這個問題嗎？「用3次10次不能得到的第一個數字是什麼意思？」具體來說，我不明白「10倍3」是什麼意思。 – bheklilr

提示：你有'num'''（不是一個很好的函數名稱IMO），它基本上確保你的列表中沒有重複。爲什麼不使用'Data.Set'？這是一個更有效的獨特元素無序集合的實現，因爲它在內部被實現爲二叉樹。你可以用'num''= Data.Set.toList節省很多時間。 Data.Set.fromList'，除非'num'''表示接受無限流。由於它看起來像有一個有限的搜索空間，這應該是安全的。 – bheklilr

您將使用3,3,3,3,3,3,3,3,3,3（3的10倍）。以及每個之間的四個操作數（+， - ，*，/）3.考慮所有可能性。例如，當您撥打firstNumber 3 6時，您會獲得1,2,3，... 31但不是32。現在瞭解了嗎？ – sasas

我們所用的發電機組部分答案的方面解決這個問題：num k 1是集合{K}，num 2是一組通過組合num k 1與num k 1，num k 3產生的所有數字將被通過組合產生的集合中的所有號碼的num k 1與num k 2等等。每個步驟使用前面步驟中計算的集合，並應用一個運算符。這是前3個步驟。請注意，每個數字都使用兩個先前生成的數字和一個運算符來計算。

num 3 1 = {3}
num 3 2 = {3-3 = 0，3/3 = 1，3 = 3，3 + 3 = 6，3×3 = 9}
num 3 3 = {3-9 = -6,3-6 = -3,1-3 = -2,0 = 0,1/3 = 1/3,3/6 = 1/2,1 = 1,6/3 = 2，3 = 3，3 + 1 = 4，6 = 6,9 = 9,3 + 9 = 12，3×6 = 18，3 * 9 = 27}

你的基於列表的num功能重新計算以前的步驟有兩個原因。

步驟n重新計算以前的所有步驟。例如，num x 4將計算num x 1,num x 2和num x 3。然後，num x 3將再次計算num x 1和num x 2。
在內循環中有num的遞歸調用。具體來說，你有[... | ... a <- num x i, b <- num x (n-i) ]。這將爲a的每個值重新計算num x (n-i)。您可以通過編寫[... | ... let b_input = num x (n-i), a <- num x i, b <- b_input]將遞歸調用移出內部循環。（編譯器優化可能會自動執行此操作，但您不應該依賴它。）

而不是重新計算以前的結果，您應該保存並重新使用它們。最簡單的方法是在算法進行時保存先前結果的列表。轉換代碼以保存以前的結果是一種更爲通用的技術實例，稱爲備忘錄。

效率低下的另一個來源是num''，它搜索整個列表以刪除二次時間內的重複項。在n * log（n）時間內使用Data.Set模塊中的套件刪除複製凸輪。

總之，在num k n中，請不要遞歸調用num，因爲這樣會做多餘的工作。除了遞歸調用，請保存num k 1,num k 2，... num k (n-1)的結果列表，並將此列表傳遞給num k n。另外，使用Data.Set模塊刪除重複值而不是調用num''。

來源

2014-06-04 23:41:22 Heatsink

如何使用Data.Set模塊刪除重複值而不是調用num''？你能舉個例子嗎？ – sasas

@sasas你可以在http://stackoverflow.com/q/16108714/507803的答案中看到一些示例實現。 – Heatsink

不幸的是，我無法成功。 – sasas

如何在Haskell中優化此代碼

回答

相關問題