如何優化這個哈斯克爾片段

我想創建一個小模塊來做基於小數的計算。一些被存儲爲一個整數mantisse，與由一個int指定精度值：如何優化這個哈斯克爾片段

data APNum = 
    { getMantisse :: Integer 
    , getPrecision :: Int }

例如：

APNum 123 0 -> 123 
APNum 123 1 -> 1.23 
APNum 123 2 -> 12.3 
...

（負精度是不允許的）。

現在，我寫了這個功能，它通過剝離儘可能多的尾隨零的儘可能自動調節精度：

autoPrecision :: APNum -> APNum 
    autoPrecision [email protected](APNum m p) = if p > maxPrecision 
    then autoPrecision $ setPrecision x maxPrecision 
    else autoPrecision' m p where 
    autoPrecision' m p = let (m',r) = m `divMod` 10 in 
     if r /= 0 || p <= 0 then APNum m p else autoPrecision' m' (pred p)

（MaxPrecision和setPrecision是顯而易見的，我認爲）。

問題是，這個片段有一個非常糟糕的表現，特別是n個數字超過10000個數字。有沒有簡單的優化？

來源

2010-08-18 fuz

「前導零」是否指「尾隨零」？（即'APNum 12000 5' - >'APNum 12 2'） – kennytm 2010-08-18 07:26:54

@KennyTM這就是我所假設的，因爲整數不能有前導零 – 2010-08-18 09:18:03

對不起......固定。 – fuz 2010-08-18 10:45:59

您可以使用二分查找找出除m之外的10的最高次冪，而不是嘗試所有連續的值。

import Numeric.Search.Range 
import Data.Maybe 

data APNum = APNum{getMantisse :: Integer, getPrecission :: Int} deriving Show 

setPrecision (APNum m _) x = APNum m x 
maxPrecission = 200000 

findDiv x = pred $ fromJust $ searchFromTo (p x) 0 maxPrecission where 
    p x n = x `mod` 10^n /= 0 

autoPrecision :: APNum -> APNum 
autoPrecision [email protected](APNum m p) 
= if p > maxPrecission then 
    autoPrecision $ setPrecision x maxPrecission else APNum m' p' 
where d = min (findDiv m) p 
     p' = p - d 
     m' = m `div` 10^d

我使用這裏的binary-search包，它提供searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a。這應該會給你一個很大的提速。

來源

2010-08-18 06:24:01

順便說一句...有一些懶惰可以關閉，以使其更快？ – fuz 2010-08-18 10:47:34

這可按預期工作並縮短執行時間。真正的問題是，在執行此操作時，haskell消耗大量空間。我將很快寫出一個完整的程序例子。 – fuz 2010-08-19 04:40:15

也可爲x mod 10 == 0意味着X mod 2 == 0，這是更便宜的測試

來源

2010-08-18 10:31:16

那麼所有的數字都可以被2整除10嗎？再想一想:-) – Landei 2010-08-18 14:07:49

不，但是你可以先分兩次（非常便宜），然後，如果n = 0，mod 2除以5即可。 – fuz 2010-08-19 01:17:04

看起來甚至簡單的字符串操作仍然較快：

maxPrecision = 2000000 

autoPrecision (APNum m p) = 
    let p' = min p maxPrecision 
     (n',ds) = genericDropNWhile (=='0') p' $ reverse $ show m 
    in APNum (read $ reverse ds) n' 
    where 
    genericDropNWhile p n (x:xs) | n > 0 && p x = genericDropNWhile p (n-1) xs 
    genericDropNWhile _ n xs = (n,xs)

測試與此：

main = print $ autoPrecision $ APNum (10^100000) (100000-3)

編輯：哎呀，更快的只有很多零的數字。否則，這種雙重轉換肯定是慢的。

來源

2010-08-18 19:41:21

我不確定展示和閱讀的成本是否值得在這裏。這兩者都必須進行大量的數學運算來轉換字符串。 – 2010-08-18 20:18:41

那麼，在我的機器上，我的「main」函數（見上面）比autoPrecision的其他兩個變體（0.05s分別爲0.84s和4.05s）運行得更快。但是，正如我所指出的，只有當尾數包含很多尾隨零時纔是這種情況。我認爲這是因爲在大型Integer上重複應用'div'非常昂貴，而'show'我認爲在這裏比較便宜（需要檢查'show'實現）。我並不是說應該將show用於這種事情，而是樸素的'div'可能不是這裏最優化的解決方案。 – 2010-08-18 21:58:05

如何優化這個哈斯克爾片段

回答

相關問題