Perché `(mappa digitToInt). show` è così veloce?

https://stackoverflow.com/questions/4841078

27-10-2019
|

Domanda

La conversione Integer non negativo alla sua lista di cifre viene comunemente fatto in questo modo:

import Data.Char

digits :: Integer -> [Int]
digits = (map digitToInt) . show

I stava cercando di trovare un modo più diretto per eseguire l'operazione, senza coinvolgere una conversione stringa, ma io sono in grado di venire con qualcosa di più veloce.

cose che ho cercato finora:

La linea di base:

digits :: Int -> [Int]
digits = (map digitToInt) . show

Si è questo uno da un'altra domanda su StackOverflow:

digits2 :: Int -> [Int]
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10)

Il tentativo di rotolare il mio:

digits3 :: Int -> [Int]
digits3 = reverse . revDigits3

revDigits3 :: Int -> [Int]
revDigits3 n = case divMod n 10 of
               (0, digit) -> [digit]
               (rest, digit) -> digit:(revDigits3 rest)

Questo è stato ispirato da showInt in Numeric:

digits4 n0 = go n0 [] where
    go n cs
        | n < 10    =  n:cs
        | otherwise =  go q (r:cs)
        where
        (q,r) = n `quotRem` 10

Ora il punto di riferimento. Nota:. Sto forzando la valutazione utilizzando filter

λ>:set +s
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000]
2400000
(1.58 secs, 771212628 bytes)

Questo è il riferimento. Ora, per digits2:

λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000]
2400000
(5.47 secs, 1256170448 bytes)

Questo è il 3.46 volte più a lungo.

λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000]
2400000
(7.74 secs, 1365486528 bytes)

digits3 è 4.89 il tempo più lento. Solo per divertimento, ho provato utilizzando solo revDigits3 ed evitare il reverse.

λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000]
2400000
(8.28 secs, 1277538760 bytes)

Stranamente, questo è ancora più lento, 5.24 volte più lento.

E l'ultimo:

λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000]
2400000
(16.48 secs, 1779445968 bytes)

Questa è 10.43 il tempo più lento.

Ho avuto l'impressione che solo con l'aritmetica e contro avrebbe sovraperformare qualsiasi cosa che coinvolge una conversione stringa. A quanto pare, c'è qualcosa che non può afferrare.

Così che cosa il trucco? Perché digits così veloce?

sto usando GHC 6.12.3.

Soluzione

Visto che non posso aggiungere ancora commenti, farò un po 'di più il lavoro e basta analizzare tutti loro. Sto mettendo l'analisi in alto; tuttavia, i dati in questione è al di sotto. (Nota:. Tutto questo è fatto in 6.12.3, come pure - ancora nessuna magia GHC 7)

Analisi:

Versione 1: show è abbastanza buona per interi, in particolare quelli più breve che abbiamo. Fare le stringhe in realtà tende ad essere decente in GHC; tuttavia la lettura e la scrittura di stringhe stringhe di grandi dimensioni di file (o stdout, anche se non si vorrebbe farlo) sono dove il codice può assolutamente crawl. Ho il sospetto che molti dei dettagli dietro il motivo per cui questo è così veloce sono dovute alle ottimizzazioni intelligenti all'interno di spettacolo per Ints.

Versione 2: Questo è stato il più lento del gruppo durante la compilazione. Alcuni problemi: inverso è severo nel suo argomento. Ciò significa che non si beneficiare di essere in grado di eseguire calcoli sulla prima parte della lista, mentre si sta calcolando gli elementi successivi; si deve calcolare tutti, li capovolgere, e poi fare i vostri calcoli (vale a dire ( `mod` 10)) sugli elementi della lista. Anche se questo può sembrare piccolo, può portare ad una maggiore utilizzo della memoria (si noti la 5GB di memoria heap allocata anche qui) e calcoli più lenti. (Lunga storia breve:. Non utilizzare inverso)

Versione 3: ricordo come ho appena detto non uso contrario? Risulta, se si tira fuori, questa scende a 1.79s tempo totale di esecuzione - a malapena più lento rispetto alla linea di base. L'unico problema è che, come si va più in profondità il numero, si sta costruendo la spina dorsale della lista nella direzione sbagliata (in sostanza, si sta consing "in" della lista con la ricorsione, al contrario di consing "su" l'elenco).

Versione 4: Questa è un'implementazione molto intelligente. Approfittate di diverse cose belle: per uno, quotRem dovrebbe usare l'algoritmo di Euclide, che è logaritmica nel suo argomento più grande. (Forse è più veloce, ma non credo che ci sia qualcosa che è più di un fattore costante più veloce di Euclide.) Inoltre, è cons sulla lista come discusso l'ultima volta, in modo che non c'è bisogno di risolvere eventuali thunk lista, come si andare - l'elenco è già interamente costruita quando si torna in giro per analizzarlo. Come si può vedere, i benefici delle prestazioni da questo.

Questo codice è stato probabilmente il più lento in GHCi perché un sacco di ottimizzazioni eseguita con la bandiera -O3 in GHC accordo con fare le liste più veloce, mentre GHCi non farebbe nulla di tutto ciò.

Lezioni: contro il modo in cui a destra in una lista, orologio per severità intermedia che può rallentare calcoli, e fare un po 'noia a guardare le statistiche a grana fine delle prestazioni del codice. compilazione Anche con le bandiere -O3:. ogni volta che non lo fai, tutte quelle persone che hanno messo un sacco di ore a fare GHC super-veloce ottenere grandi occhi ol' cucciolo a voi

Dati:

Ho appena preso tutte le quattro funzioni, li bloccato in un unico file .hs, e poi cambiato, se necessario, in modo da riflettere la funzione in uso. Inoltre, ho sbattuto il limite fino a 5e6, perché in alcuni casi codice compilato avrebbe eseguito in meno di mezzo secondo il 1E6, e questo può iniziare a problemi di granularità causa con le misure che stiamo facendo.

opzioni del compilatore: l'uso GHC --make -O3 [nome del file] .hs per avere GHC fare qualche ottimizzazione. Ci scarichiamo le statistiche di un errore standard utilizzando cifre + RTS -sstderr .

ci Dumping a -sstderr dà in uscita che assomiglia a questo, nel caso di digits1:

digits1 +RTS -sstderr
12000000
   2,885,827,628 bytes allocated in the heap
         446,080 bytes copied during GC
           3,224 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  5504 collections,     0 parallel,  0.06s,  0.03s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.61s  (  1.66s elapsed)
  GC    time    0.06s  (  0.03s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    1.67s  (  1.69s elapsed)

  %GC time       3.7%  (1.5% elapsed)

  Alloc rate    1,795,998,050 bytes per MUT second

  Productivity  96.3% of total user, 95.2% of total elapsed

Ci sono tre statistiche chiave qui:

di memoria totale in uso:. Solo 1 MB significa che questa versione è molto efficiente dello spazio
Tempo totale:. Mezzi 1.61s nulla ora, ma staremo a vedere come appare contro le altre implementazioni
Produttività: Questo è solo al 100% meno spazzatura raccolta; visto che siamo al 96,3% This significa che non stiamo creando un sacco di oggetti che lasciamo in giro in memoria ..

Va bene, passiamo alla versione 2.

digits2 +RTS -sstderr
12000000
   5,512,869,824 bytes allocated in the heap
       1,312,416 bytes copied during GC
           3,336 bytes maximum residency (1 sample(s))
          13,048 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 10515 collections,     0 parallel,  0.06s,  0.04s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    3.20s  (  3.25s elapsed)
  GC    time    0.06s  (  0.04s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    3.26s  (  3.29s elapsed)

  %GC time       1.9%  (1.2% elapsed)

  Alloc rate    1,723,838,984 bytes per MUT second

  Productivity  98.1% of total user, 97.1% of total elapsed

Bene, quindi stiamo vedendo un modello interessante.

stessa quantità di memoria utilizzata. Ciò significa che questa è un'implementazione abbastanza buona, anche se potrebbe significare che abbiamo bisogno di testare sugli ingressi di campionamento più alte per vedere se siamo in grado di trovare una differenza.
Ci vuole il doppio del tempo. Torneremo ad alcune speculazioni sul motivo per cui questo è più avanti.
In realtà è un po 'più produttivo, ma dato che GC non è una parte enorme di entrambi i programmi questo non ci aiuta nulla di significativo.

Versione 3:

digits3 +RTS -sstderr
12000000
   3,231,154,752 bytes allocated in the heap
         832,724 bytes copied during GC
           3,292 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  6163 collections,     0 parallel,  0.02s,  0.02s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    2.09s  (  2.08s elapsed)
  GC    time    0.02s  (  0.02s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    2.11s  (  2.10s elapsed)

  %GC time       0.7%  (1.0% elapsed)

  Alloc rate    1,545,701,615 bytes per MUT second

  Productivity  99.3% of total user, 99.3% of total elapsed

Bene, quindi stiamo vedendo alcuni modelli strani.

Siamo ancora a 1 MB di memoria totale in uso. Quindi non abbiamo nulla colpito memoria inefficiente, che è buono.
Non siamo del tutto a digits1, ma abbiamo battito digits2 abbastanza facilmente.
Molto poco GC. (Tenete a mente che tutto ciò che oltre il 95% la produttività è molto buono, quindi non siamo in realtà si tratta di qualcosa di troppo importante qui.)

E, infine, la versione 4:

digits4 +RTS -sstderr
12000000
   1,347,856,636 bytes allocated in the heap
         270,692 bytes copied during GC
           3,180 bytes maximum residency (1 sample(s))
          12,100 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  2570 collections,     0 parallel,  0.00s,  0.01s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    1.09s  (  1.08s elapsed)
  GC    time    0.00s  (  0.01s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    1.09s  (  1.09s elapsed)

  %GC time       0.0%  (0.8% elapsed)

  Alloc rate    1,234,293,036 bytes per MUT second

  Productivity 100.0% of total user, 100.5% of total elapsed

Wowza! pausa di che lascia a desiderare:

Siamo ancora a 1MB totale. Questo è quasi certamente una caratteristica di queste implementazioni, che rimangono a 1MB sugli ingressi di 5e5 e 5e7. Un testamento alla pigrizia, se si vuole.
Abbiamo tagliato fuori circa il 32% del nostro tempo originale, che è abbastanza impressionante.
Ho il sospetto che le percentuali qui riflettono la granularità in -sstderr Monitoring piuttosto che qualsiasi calcolo sulle particelle superluminali.

Altri suggerimenti

Rispondere alla domanda "perché rem invece di mod?" nei commenti. Quando si tratta di valori positivi rem x y === mod x y così l'unica considerazione di nota è la prestazione:

> import Test.QuickCheck
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y)

Allora, qual è la performance? Se non avete una buona ragione per non farlo (e di essere pigro non è una buona ragione, né non sapere Criterio), quindi utilizzare uno strumento buon punto di riferimento, ho usato Criterio:

$ cat useRem.hs 
import Criterion
import Criterion.Main

list :: [Integer]
list = [1..10000]

main = defaultMain
        [ bench "mod" (nf (map (`mod` 7)) list)
        , bench "rem" (nf (map (`rem` 7)) list)
        ]

L'esecuzione di questo show rem è misurabile migliore di mod (compilato con -O2):

$ ./useRem 
...
benchmarking mod
...
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950

benchmarking rem
...
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow