Por `(mapa digitToInt). show` é tão rápido?

StackOverflow https://stackoverflow.com/questions/4841078

Pergunta

Convertendo Integer não negativo à sua lista de dígitos é comumente feito assim: 

import Data.Char

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

Eu estava tentando encontrar uma maneira mais direta para executar a tarefa, sem envolver a conversão de cadeia, mas eu sou incapaz de chegar a algo mais rápido.

Coisas que eu tenho tentado até agora:

A linha de base: 

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

Got este de uma outra pergunta sobre StackOverflow: 

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

Tentando fazer a minha própria: 

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

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

Este foi inspirado por showInt em Numeric: 

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

Agora, o benchmark. Nota:. Eu estou forçando a avaliação usando filter 

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

Esta é a referência. Agora, para digits2: 

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

Isso é 3,46 vezes mais. 

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

digits3 é 4,89 tempo mais lento. Apenas por diversão, eu tentei usando apenas revDigits3 e evitar o reverse. 

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

Estranhamente, isso é ainda mais lenta, 5,24 vezes mais lento.

E a última: 

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

Esta é 10.43 tempo mais lento.

Eu estava sob a impressão de que só usando a aritmética e contras iria superar qualquer coisa que envolva uma conversão string. Aparentemente, há algo que não consigo entender.

Então, o que o truque? Por que é digits tão rápido?

Eu estou usando GHC 6.12.3.

Foi útil?

Solução

Vendo como eu não podem adicionar comentários ainda, vou fazer um pouco mais de trabalho e apenas analisar todos eles. Estou colocando a análise no topo; no entanto, os dados relevantes é abaixo. (Nota:. Tudo isso é feito em 6.12.3 bem - nenhuma mágica GHC 7 até o momento)

Análise:

Versão 1: show é bom bastante para ints, especialmente aqueles tão curto quanto temos. Fazendo cordas realmente tende a ser decente em GHC; no entanto leitura para cordas e escrever grandes cadeias de arquivos (ou stdout, embora você não iria querer fazer isso) são onde o seu código pode absolutamente rastreamento. Eu suspeito que muitos dos detalhes por trás por que isso é tão rápido são devido a otimizações inteligentes dentro de mostrar para Ints.

Version 2: Este foi o mais lento do grupo quando compilado. Alguns problemas: inverso é rigorosa em seu argumento. O que isto significa é que você não beneficiar de ser capaz de realizar cálculos sobre a primeira parte da lista, enquanto você está computando os próximos elementos; você tem que calcular todos eles, flip-los e, em seguida, fazer seus cálculos (ou seja, ( `mod` 10)) sobre os elementos da lista. Enquanto isto pode parecer pequeno, pode levar a uma maior utilização de memória (note a 5GB de memória heap alocado aqui também) e cálculos mais lentas. (Para encurtar a história:. Não uso reverso)

Version 3: Lembre-se como eu disse, não use inversa? Acontece que, se você tirá-lo, este gotas para 1.79s tempo total de execução - apenas mais lento do que a linha de base. O único problema aqui é que como você ir mais fundo no número, você está construindo até a coluna vertebral da lista na direção errada (essencialmente, você está consing "em" a lista com recursividade, em oposição a consing "sobre" a lista).

Versão 4: Esta é uma implementação muito inteligente. Você se beneficia de várias coisas agradáveis: por um lado, quotRem deve usar o algoritmo de Euclides, que é logarítmica em seu argumento maior. (Talvez seja mais rápido, mas eu não acredito que há algo que é mais do que um fator constante mais rápido do que Euclides.) Além disso, é cons para a lista da última vez discutido, de modo que você não tem que resolver quaisquer thunks lista como você ir - a lista já está inteiramente construída quando você voltar ao redor para analisá-lo. Como você pode ver, os benefícios de desempenho deste.

Este código foi provavelmente o mais lento em GHCi porque muitas das otimizações realizadas com a bandeira O3 no negócio GHC com fazer listas mais rápido, enquanto GHCi não faria nada disso.

Lessons: contras da maneira correta em uma lista, relógio de rigor intermediário que pode retardar cálculos, e fazer algum trabalho braçal em olhar para as estatísticas de grão fino de desempenho do seu código. Também compilar com as O3 bandeiras:. Sempre que você não fizer isso, todas as pessoas que colocar um monte de horas para fazer GHC super-rápido obter grandes olhos ol filhote de cachorro em você

Data:

Eu só tomou todas as quatro funções, enfiou-os em um arquivo .hs, e depois alterados conforme necessário para refletir a função em uso. Além disso, eu cruzei o limite de até 5E6, porque em alguns casos código compilado seria executado em menos de meio segundo sobre 1E6, e isso pode começar a problemas de granularidade causa com as medidas que estamos a fazer.

Opções de compilador: use ghc --faça O3 [arquivo] .hs ter GHC fazer alguma otimização. Vamos despejar estatísticas para erro padrão usando dígitos + RTS -sstderr .

Dumping para -sstderr nos dá saída parecida com esta, no caso de 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

Há três principais estatísticas aqui:

  1. A memória total em uso:. Única 1MB significa esta versão é muito eficiente de espaço
  2. Tempo total:. Meio 1.61s nada agora, mas vamos ver como fica contra as outras implementações
  3. Produtividade: Este é apenas 100% de coleta de menos lixo; já que estamos em 96,3% this meios que não estamos criando um monte de objetos que deixamos em torno de mentir na memória ..

Tudo bem, vamos passar para a versão 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

Tudo bem, então nós estamos vendo um padrão interessante.

  1. A mesma quantidade de memória utilizada. Isto significa que esta é uma implementação muito bom, embora isso poderia significar que temos de teste em entradas de amostra superiores para ver se podemos encontrar uma diferença.
  2. É preciso o dobro do tempo. Nós vamos voltar a alguma especulação a respeito de porque este é mais tarde.
  3. Na verdade, é um pouco mais produtivo, mas dado que GC não é uma enorme parte de qualquer programa deste não nos ajuda nada significativo.

Version 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

Tudo bem, então estamos vendo alguns padrões estranhos.

  1. Ainda estamos na memória total de 1MB em uso. Então, nós não bater em nada memória de ineficiente, o que é bom.
  2. Não estamos completamente em digits1, mas temos batida digits2 muito facilmente.
  3. Muito pouco GC. (Tenha em mente que qualquer coisa acima de 95% a produtividade é muito bom, por isso não estamos realmente lidando com nada muito significativo aqui.)

E, finalmente, a versão 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! Vamos decompô-lo:

  1. Ainda estamos no total de 1MB. Isto é quase certamente uma característica destas implementações, como eles permanecem em 1MB de insumos de 5e5 e 5e7. Um testamento para a preguiça, se você quiser.
  2. Nós cortar cerca de 32% do nosso tempo original, que é bastante impressionante.
  3. Eu suspeito que as percentagens aqui refletem a granularidade em -sstderr está monitorando em vez de qualquer computação em partículas superluminais.

Outras dicas

Respondendo a pergunta "por que rem em vez de mod?" nos comentários. Quando se lida com valores positivos rem x y === mod x y então a única consideração de nota é o desempenho: 

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

Então, qual é o desempenho? A menos que você tenha uma boa razão para não (e ser preguiçoso não é uma razão boa, nem é não saber Criterion), em seguida, usar uma ferramenta boa referência, eu usei Critério: 

$ 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)
        ]

A execução deste rem mostra é mensurável melhor do que mod (compilado com -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
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top