Verimli Haskell aşağıdaki işlevi, çok sayıda (n > 108) çözmek için nasıl kurtulduğuna sevindim

f(n) = max(n, f(n/2)   f(n/3)   f(n/4))

Haskell içinde memoization örnekleri fibonacci çözmek gördüm bilgisayar dahil olan sayılar (tembel) tüm fibonacci sayıları gerekli n kadar. Ama verilen bir n için, bu durumda, biz sadece gerekir çok az Ara sonuçları hesaplamak için.

Teşekkürler

Bu çok verimli bir şekilde alt-lineer zaman içinde bir dizin bir yapı yaparak yapabiliriz.

Ama önce

{-# LANGUAGE BangPatterns #-}

import Data.Function (fix)

F tanımlayalım, ama açık özyineleme 'kendisi doğrudan aramak yerine kullanmak.

f :: (Int -> Int) -> Int -> Int
f mf 0 = 0
f mf n = max n $ mf (div n 2)  
                 mf (div n 3)  
                 mf (div n 4)

fix f kullanarak unmemoized f alabilirsiniz

Bu f ne anlama geliyor bu test çağırarak f küçük değerler için izin verir, örneğin: fix f 123 = 144

Tanımlayarak bugünkü ileri matematik.

f_list :: [Int]
f_list = map (f faster_f) [0..]

faster_f :: Int -> Int
faster_f n = f_list !! n

Bu passably iyi bir performans sergiliyor ve almaya gidiyordu ne değiştirirO(n^3)Ara sonuçları memoizes bir zaman.

Ama yine de mf memoized cevap bulmak için dizin sadece doğrusal zaman alır. Bu sonuçlar gibi anlamına gelir:

*Main Data.List> faster_f 123801
248604

tolere edilebilir, ama sonuç çok daha iyi bir ölçek yok. Daha iyisini yapabiliriz!

İlk olarak, sonsuz bir ağaç tanımlayalım:

data Tree a = Tree (Tree a) a (Tree a)
instance Functor Tree where
    fmap f (Tree l m r) = Tree (fmap f l) (f m) (fmap f r)

Ve sonra dizin n ile bir düğüm bulabilmemiz içine dizin için bir yol tanımlamak ederizO(log n)zaman yerine:

index :: Tree a -> Int -> a
index (Tree _ m _) 0 = m
index (Tree l _ r) n = case (n - 1) `divMod` 2 of
    (q,0) -> index l q
    (q,1) -> index r q

... ve bir ağaç doğal sayılar tam etrafındakiler endeksleri ile keman gerek yok: kullanışlı bulabiliriz

nats :: Tree Int
nats = go 0 1
    where
        go !n !s = Tree (go l s') n (go r s')
            where
                l = n   s
                r = l   s
                s' = s * 2

Dizin yapalım bir liste halinde bir ağaç dönüştürebilirsiniz:

toList :: Tree a -> [a]
toList as = map (index as) [0..]

Çok toList nats [0..] veren doğrulayarak kontrol edebilirsiniz

Şimdi

f_tree :: Tree Int
f_tree = fmap (f fastest_f) nats

fastest_f :: Int -> Int
fastest_f = index f_tree

gibi liste üzerinde çalışıyor, ama doğrusal zaman her düğüm bulmak yerine, logaritmik zaman onu takip edebilir.

Sonuç oldukça hızlı

*Main> fastest_f 12380192300
67652175206

*Main> fastest_f 12793129379123
120695231674999

Aslında geçmesi ve Integer yukarıda Int değiştirin ve gülünç büyük cevaplar neredeyse anında almak çok daha hızlı

*Main> fastest_f' 1230891823091823018203123
93721573993600178112200489

*Main> fastest_f' 12308918230918230182031231231293810923
11097012733777002208302545289166620866358