Sortie efficace des nombres

Question

Je souhaite imprimer une liste d'intégrales séparées par des espaces sur stdout. La génération de la liste est rapide, j'ai donc essayé de résoudre ce problème avec la séquence [1..200000].

En C, je peux le mettre en œuvre comme ceci:

#include "stdio.h" 
int main() 
{ 
    int i; 
    for(i = 0; i <= 200000; ++i) 
    printf("%d ", i); 
    return 0; 
} 

La solution la plus rapide dans Haskell je pourrais mettre en œuvre est environ trois fois plus lent:

import Data.List (intercalate) 
main = putStr . intercalate " " . map (show) $ [1..(200000)] 

j'ai essayé des chaînes ordinaires à certains égards, mais avec eux, c'est encore plus lent. Les gros problèmes semblent être la conversion des entiers en chaînes avec show (ou la conversion en ByteStrings).

Des suggestions pour accélérer ce processus sans interfaçage avec C? Cela ne devrait pas devenir compliqué (aussi court et beau que possible, l'utilisation d'autres modules Haskell est très bien).

Answer 1

Première question:

Publiez du code !!!

je suppose que (selon delnan :), que c'est lent parce que le suivant arrive (sauter l'étape 4Si vous ne l'utilisez pas bytestring):

1. Tous les chiffres sont un par un converti. La sortie est une liste.
2. La liste des sorties doivent être parcourus à nouveau parce que vous ajoutez des éléments (les espaces!)
3. La liste doivent être parcourus à nouveau parce que vous concaténer il
4. La liste doit parcourir à nouveau car il est converti en chaîne d'octets (pack)
5. Le tout est imprimé.

Il pourrait être plus rapide avec bytestring, mais vous devriez probablement mettre en œuvre votre propre show, qui travaille avec des chaînes ordinaires. Ensuite, soyez si intelligent et évitez les travées multiples, entrez les espaces une fois la liste créée.

Peut-être comme ceci:

import qualified Data.Bytestring.Lazy.Char8 as B 

showB :: Int -> Bytestring -- Left as an exercise to the reader 

main = B.putStr $ pipeline [0..20000] where 
    pipeline = B.tail . B.concat . map (B.cons' ' ') . map showB 

Ce n'est pas testé, donc le profil !!! Vous voyez, les cartes peuvent être fusionnées, donc la liste sera traversée peut-être deux fois.

Answer 2

Eh bien, vous pouvez réécrire le code un peu:

import Data.List (intercalate) 
main = output 
output = putStr one_string 
one_string = intercalate " " strings 
strings = map show $ [1..2000000] 

Ensuite, vous pouvez le profil à l'aide de "GHC -O2 -Prof -auto-all .hs":

COST CENTRE     MODULE    %time %alloc 

one_string      Main     42.2 55.9 
strings      Main     39.2 43.1 
output       Main     18.6 1.0 

Vous pouvez voir que intercalate prend une bonne moitié de l'exécution. Je ne pense pas que vous puissiez faire avancer le tout plus vite, sans recourir à une supercherie de bas niveau. Si vous passez à une intercalation plus rapide (à partir de Data.ByteString.Lazy.Char8, par exemple), vous devrez utiliser une variante plus lente de la conversion Int -> String.

Answer 3

Voici une approche différente du même problème, qui tente d'exploiter le partage dans les suffixes de chaîne. Il a été environ 1/3ème plus rapide sur ma machine que l'original Haskell, bien qu'encore un peu loin de la version C. Faire des numéros autres que 1-999999 est laissé en exercice:

basic :: [Char] 
basic = ['0'..'9'] 

strip :: String -> String 
strip = (' ' :) . dropWhile (== '0') 

numbers :: Int -> [String] 
numbers 0 = [""] 
numbers n = [x : xs | x <- basic, xs <- rest] 
    where 
    rest = numbers (n - 1) 

main = mapM_ (putStr . strip) (tail $ numbers 6) 

Answer 4

Ce programme fonctionne beaucoup plus rapide si j'utilise GHC-6.10.4 au lieu de GHC-6.12.1. La ligne 6.12 de l'IIRC a introduit des IO Unicode-aware qui, je pense, explique en grande partie le ralentissement.

Mon système:

C (gcc -O2):  0.141s 
HS (ghc-6.10.4 -O2): 0.191s (ave.) 
HS (ghc-6.12.1 -O2): 0.303 (ave.) 

Lors de l'utilisation GHC-6.10 le résultat est assez comparable à C; Je pense que la différence est due à l'utilisation de chaînes par Haskell (et probablement aussi à l'exécution).

Je pense qu'il est possible de contourner la conversion unicode dans l'E/S de ghc-6.12 si vous voulez obtenir de meilleures performances de ce compilateur.

Answer 5

Cette version fait un peu mieux que la vôtre. Je suppose que c'est une façon de l'améliorer.

showWithSpaces  :: (Show a) => [a] -> ShowS 
showWithSpaces []  = showString "" 
showWithSpaces (x:xs) = shows x . showChar ' ' . showWithSpaces xs 

main = putStrLn $ showWithSpaces [1..2000000] $ ""