2

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

4

5 回答 5

4

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

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 转换变体。

于 2010-11-26T15:09:53.573 回答
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 转换。

于 2010-11-26T17:23:22.813 回答
1

第一个问题：

贴一些代码！！！

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

  1. 所有的数字都是一一转换的。输出是一个列表。
  2. 必须再次遍历输出列表，因为您添加了元素（空格！）
  3. 该列表必须再次遍历，因为您将它连接起来
  4. 该列表必须再次遍历，因为它被转换为字节串 ( 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 地图可以融合，所以列表可能会被遍历两次。

于 2010-11-26T14:25:37.697 回答
0

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

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

main = putStrLn $ showWithSpaces [1..2000000] $ ""
于 2010-11-27T22:59:35.923 回答
0

这是解决同一问题的另一种方法，它试图利用字符串后缀中的共享。在我的机器上，它比原来的 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)
于 2010-11-26T16:33:10.977 回答