遍历ByteStrings

Question

我在阅读一些随机博客时，有人试图在Haskell中执行一个简单的字符串处理操作，并得到相当慢的代码。一些问题与他的(最后，下页的方式)代码：

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

我认为，最自然的方法是使用懒惰的ByteString(就像他以前的一些尝试那样)，并放弃scanl以支持zipWith'，将字符串拉链的字符串移到一个字符串上：zipWith f s (cons ' ' s)。

问题所在

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

编辑以添加:另一种方法可能是使用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的3.2M文件上运行每个函数。这是我们的参考速度。

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版本慢30%左右，而使用Text的mapAccumL版本的速度几乎是Text的两倍！

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

但还有更容易获得的好处。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

我们现在讨论的3x比最初的引用要快。作为比较，非常快速的python代码(它只是调用C)，

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

在30ms中翻阅文本文件。

Answer 2

懒惰的I/O可能是一个问题，但它是处理这个小任务的最简单的方法。

import Data.Text.Lazy (toTitle)
import Data.Text.Lazy.IO (readFile, putStr)
import Prelude hiding (readFile, putStr)

main = readFile "file" >>= putStr . toTitle

它实际上会花时间做Unicode (分字和标题大写)正确，但这可能是你想要的。如果您想避免延迟I/O，管道-文本包应该产生一些不太大的东西。

如果你真的想把所有的东西都当作ASCII，假设所有的单词都以字母开头，我仍然认为懒惰的I/O在这里是一个胜利，但它更复杂一些。

import Data.Bits (.&.)
import Data.ByteString.Lazy (ByteString, cons', putStrLn, readFile, uncons)
import Data.ByteString.Lazy.Char8 (lines, unlines, unwords, words)
import Data.Word (Word8)
import Prelude hiding (putStrLn, readFile, lines, unlines, unwords, words)

capitalize :: ByteString -> ByteString
capitalize word = case uncons word of
  Just (h, t) -> cons' (h .|. complement 32) t
  Nothing     -> word

main = readFile "file"
   >>= putStrLn . unlines
                . map (unwords . map capitalize . words)
                . lines

同样，避免懒惰的I/O就像使用管道-字节串一样简单。

还有一条关于这个帖子这里的红线，他们似乎从Builder抽象中获得了很好的性能，还有一种更好的上大写方式。构建器抽象可能比我的字节串黑客更快，因为在编写输出数据之前，它会更好地对输出数据进行块处理。