Эффективный вывод чисел

Question

Я хочу напечатать список интегралов, разделенных пробелами в stdout. Генерация списка выполняется быстро, поэтому я попытался решить эту проблему с помощью последовательности [1..200000].

В C, я могу реализовать это следующим образом:

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

Самое быстрое решение в Haskell я мог бы реализовать примерно в три раза медленнее:

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

Я попытался байтовых строк в некоторых отношениях, но с ними он стал еще медленнее. Большие проблемы, похоже, являются преобразованием целых чисел в строки с показом (или преобразованием в ByteStrings).

Любые предложения, как ускорить это, не взаимодействуя с C? Он не должен становиться сложным (как можно короче и красивее, с использованием других модулей Haskell).

Answer 1

Первый вопрос:

Опубликовать код!

Я думаю (по delnan :), что это медленно, потому что происходит следующее (пропустите шаг 4Если вы не используете байтовой строки):

1. Все числа по одному конвертированы. Вывод - это список.
2. Перечень выходов должны быть пройдена снова, потому что вы добавляете элементы (пространства!)
3. Список должны быть пройдена снова, потому что вы Concat его
4. Список должен быть пройден снова, потому что он преобразован в байты (pack)
5. Все это распечатывается.

Это может быть быстрее с помощью bytestring, но вы, вероятно, должны реализовать свой собственный show, который работает с байтовыми телами. Затем, будьте настолько умными и избегайте многократного прохождения, введите пробелы после создания списка.

Может быть, как это:

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 

Это проверялось, поэтому профиль !!! Вы видите, карты могут быть сплавлены, поэтому список будет пройден, может быть, два раза.

Answer 2

Ну, вы могли бы переписать код немного:

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

Тогда можно профилировать его с помощью "GHC -O2 -prof -Автоматически все .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 

Вы можете см., что интеркаляция занимает хорошую половину времени выполнения. Я не думаю, что вы могли бы все ускорить, не прибегая к какому-то низкоуровневому обману. Если вы переключитесь на более быструю интеркаляцию (например, из Data.ByteString.Lazy.Char8), вам придется использовать более медленный вариант преобразования Int -> String.

Answer 3

Вот другой подход к той же проблеме, который пытается использовать совместное использование в строковых суффиксах. На моей машине это было примерно на 1/3 быстрее, чем у оригинального Haskell, хотя, по общему признанию, все еще был выход из версии C. кроме 1 до 999999 Doing номера осталось как упражнение:

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

Эта программа работает намного быстрее, если я использую GHC-6.10.4 вместо GHC-6.12.1. IIRC, линия 6.12, представила унифицированный IO-код, который, как мне кажется, объясняет большую часть замедления.

Моя система:

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

При использовании GHC-6.10 результат довольно сопоставимы с C; Я думаю, что разница в том, что использование Haskell в строках (и, возможно, слишком быстрое время исполнения).

Я думаю, что можно обойти преобразование юникода в ввода/вывода ghc-6.12, если вы хотите получить лучшую производительность от этого компилятора.

Answer 5

Эта версия немного лучше, чем ваша. Я думаю, это один из способов улучшить его.

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

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