Как оптимизировать этот фрагмент haskell

Question

Я пытаюсь создать небольшой модуль для выполнения вычислений на основе десятичных чисел. Ряд хранится в виде целого числа 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 x@(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 цифрами. Существуют ли какие-либо простые оптимизации?

Answer 1

Вы можете использовать бинарный поиск, чтобы найти максимальную мощность 10, которая делит m, вместо того чтобы пытаться использовать все последовательные значения.

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 x@(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. Это должно дать вам большое ускорение.

Answer 2

также х mod 10 == 0 влечет х mod 2 == 0, и что дешевле, чтобы проверить на

Answer 3

Похоже, даже простой строковой операции еще быстрее:

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) 

EDIT: Упс, быстрее только для чисел с большим количеством нулей. В противном случае это двойное преобразование определенно медленнее.