Iva*_*rov 8 haskell bytestring
我一直在努力从Haskell的acm.timus.ru 解决问题1330.基本上,归结为:1)从stdin读取长度为N(N <10 ^ 4)的数组A和M对整数(M <10 ^ 5); 2)对于每个(从,到)对,打印子阵列A [from..to]到stdout的总和.
由于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毫秒并没有削减它.那么为什么我的第一个解决方案如此可笑呢？即使按照真实世界Haskell的分析提示,我仍然无法理解这一点(我只能想到大部分时间花在了readIntPair函数上,这没有多大帮助).
如果你想对自己做一些测试,我有一个Python输入生成器(gen_test.py)和一个预先生成的输入文件(input.txt),以防你没有安装Python.两个解决方案之间有一个diff(slow_fast_diff.txt).
BytestringIO涉及将数据读入打包缓冲区,就像您在C中所习惯 String的那样,另一方面,链接的字符列表不仅使IO复杂化,而且对于处理这可能意味着更高的内存使用,处理,缓存,也许是分支和GC.
短语的另一种方式:ByteString快速出于同样的原因unsigned char *
是快速的C.
正如其他人所说,这不是那么ByteString快,而是String非常非常慢.
A ByteString每个字符存储一个字节,加上一些簿记开销.一个String商店像每个字符的12个字节(取决于您是在32位或64位模式下运行).它还将每个字符存储在非连续内存中,因此每个字符必须单独分配给它,由垃圾收集器单独扫描,最后再单独解除分配.这意味着缓存局部性差,分配器时间很多,垃圾收集时间也很多.简而言之,这是非常低效的.
基本上,ByteStringC做什么,Java做什么,C++做什么,C#做什么,VB做什么,以及其他所有编程语言用字符串做什么.我所知道的其他语言没有像Haskell那样低效的默认字符串类型.(甚至Frege,这是一种Haskell方言,使用更有效的字符串类型.)
我应该指出ByteString.Char8只处理Latin-1字符.它根本不能处理随机的Unicode字符.对于像这样的编程挑战来说,这可能不是问题,但对于"真实系统"来说可能就是这样.ByteString并不真正处理异国情调的字符或不同的字符编码或任何东西; 它只是假设你想要纯ASCII.这曾经是一个安全的假设; 今天,不是那么多.