高效輸出數字

我想打印一個積分列表，用空格分隔到stdout。列表生成速度很快，所以我試圖用序列[1..200000]來解決這個問題。高效輸出數字

在C，我可以這樣實現：

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

在Haskell我可以實現最快的解決方案約3倍慢：

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

我想在某些方面字節串，但與他們相比，它變得更慢。大問題似乎是用show（或轉換爲ByteStrings）將整數轉換爲字符串。

任何建議如何加快這一點，而無需連接到C？它不應該變得複雜（儘可能簡短和美觀，使用其他Haskell模塊也可以）。

來源

2010-11-26 Christian

一如既往，分析>>>>>猜測。 – delnan 2010-11-26 13:47:45

您是否檢查過每次寫入元素的速度？寫入控制檯通常很慢，所以這可能會更糟糕，但它可能值得一試。您可以嘗試構建一定數量的元素而不是一個巨大的字符串，但是您可能需要使用append（++）或Hughes列表（DList）來執行此操作，這會添加額外的工作。這就是爲什麼我猜測寫每個元素仍然有競爭力。 – 2010-11-26 16:17:51

我試過一次寫了一個數字的版本（就像我認爲的一樣），但速度較慢。 – 2010-11-26 16:24:58

第一個問題：

Post some code !!!

我猜（根據delnan :)，這是因爲以下情況的速度慢（跳過步驟4如果你不使用的字節字符串）：

所有的數字都是一個接一個轉換。輸出是一個列表。
的產出清單已經再次因爲你添加元素走過（空格！）
名單已經因爲你Concat的它
名單必須再次經過再次穿越，因爲它被轉換爲字節串（pack）
整件事打印出來。

使用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

這是未經測試，所以輪廓！你看，地圖可以融合，所以列表將被遍歷兩次。

來源

2010-11-26 14:25:37 fuz

嗯，你可以重寫代碼位：

COST CENTRE     MODULE    %time %alloc 

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

您可以：

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

然後，你可以使用「GHC -02 -prof - 自動所有雜項文件」簡介它請參閱intercalate佔用運行時的一半。儘管如此，我並不認爲你可以讓整個事情變得更快，但不會訴諸一些低級別的詭計。如果切換到更快插入（例如，來自Data.ByteString.Lazy.Char8），則必須使用Int - > String轉換的較慢變體。

來源

2010-11-26 15:09:53 ADEpt

下面是針對同一問題的另一種方法，即嘗試利用字符串後綴中的共享。它在我的機器上運行速度比原來的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)

來源

2010-11-26 16:33:10

這個程序運行得更快，如果我用GHC-6.10.4代替GHC-6.12.1。 IIRC 6.12系列引入了unicode意識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的結果是相當媲美℃;我認爲這種差異是由於Haskell使用字符串（也可能是運行時開銷）造成的。

我認爲如果你想從編譯器中獲得更好的性能，可以繞過ghc-6.12的I/O中的unicode轉換。

來源

2010-11-26 17:23:22

這個版本比你的更好一些。我想這是改善它的一種方法。

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

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

來源

2010-11-27 22:59:35 edon

高效輸出數字

回答

相關問題