Эффективный вывод чисел - PullRequest
Новая
       14

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

2 голосов
/ 26 ноября 2010

Я хочу напечатать список интегралов, разделенных пробелами, в стандартный вывод.Генерация списка быстрая, поэтому я попытался решить эту проблему с помощью последовательности [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 в некотором роде, но с ними он стал еще медленнее.Кажется, что большие проблемы заключаются в преобразовании целых чисел в строки с помощью show (или преобразовании в ByteStrings).

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

Ответы [ 5 ]

4 голосов
/ 26 ноября 2010

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

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

Затем вы можете профилировать его, используя "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

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

2 голосов
/ 26 ноября 2010

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

Моя система: 

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, если вы хотите получить более высокую производительность от этого компилятора.

1 голос
/ 26 ноября 2010

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

Опубликовать некоторый код !!!

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

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

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

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

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

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

0 голосов
/ 28 ноября 2010

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

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

main = putStrLn $ showWithSpaces [1..2000000] $ ""
0 голосов
/ 26 ноября 2010

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

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)
...