高效输出数字

Question

我想将用空格分隔的积分列表打印到标准输出。列表生成速度很快，所以我尝试用序列 [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 模块就可以了）。

Answer 1

好吧，您可以稍微重写一下代码：

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

您可以看到插值占用了一半的运行时间。不过，我认为如果不诉诸一些低级的技巧，你无法让整个事情进展得更快。如果您切换到更快的插入（例如，从 Data.ByteString.Lazy.Char8），您将不得不使用 Int -> 的较慢变体。字符串转换。

Answer 2

如果我使用 ghc-6.10.4 而不是 ghc-6.12.1，这个程序运行得更快。 IIRC 6.12 系列引入了 unicode-aware 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 的 I/O 中的 unicode 转换。

Answer 3

第一个问题：

发布一些代码！

我猜（根据 delnan :)，它很慢，因为发生了以下情况（如果不使用字节串，请跳过步骤 4）：

1. 所有数字都一一转换。输出是一个列表。
2. 必须再次遍历输出列表，因为您添加了元素（空格！）。
3. 必须再次遍历列表，因为您连接了它。
4. 必须遍历列表。 em>再次，因为它被转换为字节串（pack）
5. 整个内容被打印出来。

使用字节串可能会更快，但您可能应该实现自己的 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

这是未经测试的，所以简介！你看， to 映射可以融合，所以列表可能会被遍历两次。

Answer 4

这是解决同一问题的不同方法，尝试利用字符串后缀中的共享。它在我的机器上比原来的 Haskell 快了大约 1/3，尽管不可否认，它与 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)

Answer 5

这个版本比你的好一点。我想这是改进它的一种方法。

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

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