string - 遍历字节串

Question

我正在阅读some random blog有人尝试在 Haskell 中执行简单的字符串处理操作，但得到的代码相当慢。他的代码存在一些问题(最后，向下一页的方式):

1. 一次性读入整个文件。
2. 他用的是比较贵的isSpace然后将生成的程序与仅考虑简单空格和换行符的 C 代码进行比较。
3. 他使用的方式scanl看起来对管道非常不友好，在不需要时使用计算字符作为每个步骤的输入。

我认为最自然的方法是使用惰性 ByteString s(正如他早期的一些尝试所做的那样)并废弃 scanl支持zipWith' ，压缩字符串并将字符串移动一位:zipWith f s (cons ' ' s)

问题

压缩一个懒惰的ByteString其自身的移位版本不会利用两个字符串之间的关系。它对 block 结尾和字符串结尾执行许多不必要的检查。我确信我可以编写一个专门的函数来遍历 ByteString带有两个字符的“窗口”，我确信一个比我更好的程序员可以编写一个利用 block 表示细节的程序，但我更愿意找到一种更易于访问的方法。有什么想法吗？

编辑添加:另一种方法可能是使用 foldr产生 ByteString构建器，遵循相同的通用方法，但使用(希望未装箱的)元组来避免数据依赖；我不确定我是否完全理解这些构建器或他们的效率。

Answer 1

我将使用以下导入。

import Data.Char 
import Data.List           
import qualified Data.Text.Lazy as T                      

import Criterion.Main
import Test.QuickCheck

与博客文章中的引用实现相比，我设法获得了惊人的速度:

capitalize :: T.Text -> T.Text
capitalize = T.tail . T.scanl (\a b -> if isSpace a then toUpper b else b) ' '

使用mapAccumL要快得多。这是 String 和 Text 版本。

{-# INLINE f #-}
f a b = (b, if isSpace a then toUpper b else b)

string :: String -> String
string = snd . mapAccumL f ' '

text :: T.Text -> T.Text
text = snd . T.mapAccumL f ' '

首先，让我们确保优化有效

λ. quickCheck $ \xs -> 
    capitalize (T.pack xs) == text (T.pack xs)
+++ OK, passed 100 tests.

现在查看 criterion 的一些基准测试结果，在 Lorem Ipsum 的 3.2 M 文件上运行每个函数。这是我们的引用速度。

benchmarking reference
collecting 100 samples, 1 iterations each, in estimated 56.19690 s
mean: 126.4616 ms, lb 126.0039 ms, ub 128.6617 ms, ci 0.950
std dev: 4.432843 ms, lb 224.7290 us, ub 10.55986 ms, ci 0.950

String 仅比优化引用 Text 版本和使用 Text 的 mapAccumL 版本慢 30% 左右速度几乎是原来的两倍!

benchmarking string
collecting 100 samples, 1 iterations each, in estimated 16.45751 s
mean: 165.1451 ms, lb 165.0927 ms, ub 165.2112 ms, ci 0.950
std dev: 301.0338 us, lb 250.2601 us, ub 370.2991 us, ci 0.950

benchmarking text
collecting 100 samples, 1 iterations each, in estimated 16.88929 s
mean: 67.67978 ms, lb 67.65432 ms, ub 67.72081 ms, ci 0.950
std dev: 162.8791 us, lb 114.9346 us, ub 246.0348 us, ci 0.950

但是还有更容易获得的 yield 。 Data.Char.isSpace 以其性能问题而闻名，因此让我们尝试一下快速的 Data.Attoparsec.Char8.isSpace。我们的 quickcheck 测试无法通过，但性能非常好。

benchmarking string/atto
collecting 100 samples, 1 iterations each, in estimated 12.91881 s
mean: 129.2176 ms, lb 129.1328 ms, ub 129.4941 ms, ci 0.950
std dev: 705.3433 us, lb 238.2757 us, ub 1.568524 ms, ci 0.950

benchmarking text/atto
collecting 100 samples, 1 iterations each, in estimated 15.76300 s
mean: 38.63183 ms, lb 38.62850 ms, ub 38.63730 ms, ci 0.950
std dev: 21.41514 us, lb 15.27777 us, ub 33.98801 us, ci 0.950

我们现在的速度比原始引用快 3 倍。作为比较，非常快的 python 代码(只是调用 C)，

print open('lorem.txt').read().title()

在30ms内翻阅文本文件。