8

我一直在尝试从 Haskell 的 acm.timus.ru解决问题 1330 。基本上，它归结为： 1) 从标准输入中读取一个长度为 N (N < 10^4) 和 M 对整数 (M < 10^5) 的数组 A；2) 对于每个 (from, to) 对，将子数组 A[from..to] 的总和打印到标准输出。

由于 SO 不允许我在此问题中发布超过 2 个 URL，因此我将参考下面我的Github 存储库中的文件。

我想出了两个解决方案，它们共享大部分代码。第一个（1330_slow.hs）使用 Prelude 函数（getLine/read/words）并且有点慢：

$ ./bench.sh slow_hs
slow_hs
    Time inside the program: 2.18
MD5 (output.slow_hs.txt) = 89bcf8fd69a7fce953595d329c8f033a

另一个解决方案 (1330.hs) 抛弃了这些函数，用它们的 Data.ByteString.Char8 等效项 (B.getLine/B.readInt/B.words) 替换它们，并且表现得很好：

$ ./bench.sh hs
hs
    Time inside the program: 0.27
MD5 (output.hs.txt) = 89bcf8fd69a7fce953595d329c8f033a

这个问题的时间限制是 500 毫秒，所以虽然 270 毫秒已经足够快（并且可以与我在其他语言中的解决方案相媲美，例如 C++ 和 Go），但 2180 毫秒并没有减少它。那么为什么我的第一个解决方案如此缓慢呢？即使按照 Real World Haskell 的分析技巧，我仍然无法理解这一点（我所能弄清楚的是大部分时间都花在了 readIntPair 函数上，这并没有太大帮助）。

如果你想自己做一些测试，我有一个 Python 输入生成器 (gen_test.py) 和一个预生成的输入文件 (input.txt)，以防你没有安装 Python。以及两种解决方案之间的差异（slow_fast_diff.txt）。

4

2 回答 2

8

对比 ByteString 和 String（即为什么 String 慢？）

BytestringIO 涉及将数据读取到打包缓冲区中，就像您在 C 中可能习惯的那样。 String另一方面，是字符的链接列表，这不仅使 IO 复杂化，而且对于处理这可能意味着更高的内存、处理、缓存、也许分支和GC。

为什么 ByteString 快？

另一种表达方式：ByteString由于相同的原因unsigned char * 而快速在C.

于 2013-01-27T04:54:55.490 回答
8

正如其他人所说，这不是ByteString很快，而是String非常非常慢。

AByteString每个字符存储一个字节，加上一些记账开销。AString每个字符存储大约 12 个字节（取决于您是在 32 位还是 64 位模式下运行）。它还将每个字符存储在非连续内存中，因此每个字符必须单独分配空间，由垃圾收集器单独扫描，并最终再次单独释放。这意味着糟糕的缓存局部性、大量的分配器时间和大量的垃圾收集时间。简而言之，它非常低效。

基本上，ByteStringC 做什么，Java 做什么，C++ 做什么，C# 做什么，VB 做什么，以及几乎所有其他编程语言对字符串做什么。我所知道的其他语言都没有像 Haskell 那样低效的默认字符串类型。（即使是 Haskell 方言的 Frege 也使用了更高效的字符串类型。）

我应该指出ByteString.Char8只处理 Latin-1 字符。它根本无法处理随机的 Unicode 字符。对于像这样的编程挑战来说，这可能不是问题，但对于“真实系统”来说，这很可能是一个问题。ByteString并没有真正处理外来字符或不同的字符编码或任何东西；它只是假设您想要纯 ASCII。这曾经是一个安全的假设；今天，没有那么多。

于 2013-01-27T09:49:02.960 回答