Haskell Stil / Effizienz

Question

So arbeitete ich auf eine Art und Weise Primzahlen zu träge zu generieren, und ich kam mit diesen drei Definitionen, der alle Arbeiten in äquivalenter Weise - nur, ob jede neue Integer-Überprüfung hat einen Faktor unter allen vorangegangenen Primzahlen:

primes1 :: [Integer]
primes1 = mkPrimes id [2..]
  where mkPrimes f (x:xs) = 
          if f (const True) x 
          then 
            let g h y = y `mod` x > 0 && h y in
            x : mkPrimes (f . g) xs
          else
            mkPrimes f xs

primes2 :: [Integer]
primes2 = mkPrimes id (const True) [2..]
  where mkPrimes f f_ (x:xs) = 
          if f_ x 
          then 
            let g h y = y `mod` x > 0 && h y in
            x : mkPrimes (f . g) ( f $ g $ const True) xs
          else
            mkPrimes f f_ xs

primes3 :: [Integer]
primes3 = mkPrimes [] [2..]
  where mkPrimes ps (x:xs) = 
          if all (\p -> x `mod` p > 0) ps
          then 
            x : mkPrimes (ps ++ [x]) xs
          else
            mkPrimes ps xs

So scheint es mir primes2 sollte ein wenig schneller als primes1 sein, da es vermeidet Neuberechnen f_ = f (const True) für jede ganze Zahl (die I denken erfordert die Arbeit an der Ordnung der Nummer wir haben bisher), gefunden und aktualisiert sie nur von Primzahlen, wenn wir eine neue Primzahl begegnen.

Sind gerade von unwissenschaftlich Tests (Lauf take 1000 in GHCI) scheint es, wie primes3 läuft schneller als primes2.

Sollte nehme ich eine Lehre daraus, und gehe davon aus, dass, wenn ich eine Funktion als eine Operation darstellen kann auf einem Array, dass ich es in der letzteren Art und Weise für Effizienz umsetzen muß, oder gibt es etwas geht sonst hier?

Answer 1

Was ist das zweite Argument für die f für erforderlich ist? Meiner Meinung nach sind diese beiden Alternativen besser lesbar, und nicht wesentlich die Leistung auswirken ...

...
            let g y = f y && y `mod` x > 0 in
            x : mkPrimes g xs
...

import Control.Arrow  -- instance Monad (-> r)
import Control.Monad  -- liftM2
(.&&.) = liftM2 (&&)
...
            let g y = y `mod` x > 0 in
            x : mkPrimes (f .&&. g) xs
...

---

Wie auch immer, zurück zur Frage. Manchmal mit Funktionen wie Datenstrukturen die beste Darstellung für eine bestimmte Aufgabe ist, und manchmal nicht. „Best“ im Hinblick auf die Einfachheit der Codierung und „beste“ in Bezug auf die Leistung sind nicht immer das Gleiche. Die „Funktionen wie Datenstrukturen“ Technik ist wichtig, um Runtime-Kompilierung , aber wie die Seite warnt,

  

Runtime Compilation kann man manchmal erhebliche Effizienzgewinne gewinnen, aber kann man oft gewinnen fast nichts auf Kosten der Ihre erhöhten Stress und verringert die Produktivität.

In Ihrem Fall ist es wahrscheinlich, dass der Aufwand für jedes f :: Integer -> ... -> Bool Konstruktion ist deutlich höher als der Aufwand für jeden ps :: [Integer] konstruiert, mit wenig oder gar keinen Unterschied, wenn f ... x gegen all ... ps aufrufen.

---

Zyklen herauszupressen des Unendlichen prime Sieb, loszuwerden, die Anrufe mod! Integer-Multiplikation, Division und Modul sind viel langsamer als ganze Zahl Addition und Subtraktion. Auf meinem Rechner dieser Implementierung Uhren bei 40% schneller bei der Berechnung der ersten 1000 Primzahlen (GHC 6.10.3 -O2).

import qualified Data.Map as M
primes' :: [Integer]
primes' = mkPrimes 2 M.empty
  where
    mkPrimes n m = case (M.null m, M.findMin m) of
        (False, (n', skips)) | n == n' ->
            mkPrimes (succ n) (addSkips n (M.deleteMin m) skips)
        _ -> n : mkPrimes (succ n) (addSkip n m n)
    addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m
    addSkips = foldl' . addSkip

In Aktion (ein wenig JSON-Ish-Syntax)

   mkPrimes 2 {}
=> 2 : mkPrimes 3 {4: [2]}
=> 2 : 3 : mkPrimes 4 {4: [2], 6: [3]}
=> 2 : 3 : mkPrimes 5 {6: [2, 3]}
=> 2 : 3 : 5 : mkPrimes 6 {6: [2, 3], 10: [5]}
=> 2 : 3 : 5 : mkPrimes 7 {8: [2], 9: [3], 10: [5]}
=> 2 : 3 : 5 : 7 : mkPrimes 8 {8: [2], 9: [3], 10: [5], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 9 {9: [3], 10: [2, 5], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 10 {10: [2, 5], 12: [3], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 11 {12: [2, 3], 14: [7], 15: [5]}
...

die Karte verfolgt Zukunft Multiples, nichts mit, sondern zusätzlich.

Answer 2

Beachten Sie, dass primes3 kann durch Änderung ps++[x] zu (x:ps) effizienter gemacht werden. Der Lauf (++) ist linear in der Länge seines linken Arguments, aber konstant in der Länge des rechten Arguments.