algorithm - 列表处理的 Haskell 优化因惰性评估而受阻

Question

我正在尝试提高以下代码的效率。我想计算给定点之前出现的所有符号(作为使用 Burrows-Wheeler 变换进行模式匹配的一部分)。我计算符号的方式有些重叠。然而，当我尝试实现看起来应该是更高效的代码时，结果却效率较低，我认为应该归咎于懒惰的评估和我对它的理解不足。

我第一次尝试计数函数是这样的:

count :: Ord a => [a] -> a -> Int -> Int
count list sym pos = length . filter (== sym) . take pos $ list

然后在匹配函数本身的主体中:

matching str refCol pattern = match 0 (n - 1) (reverse pattern)
  where n = length str
        refFstOcc sym = length $ takeWhile (/= sym) refCol
        match top bottom [] = bottom - top + 1
        match top bottom (sym : syms) =
          let topCt = count str sym top
              bottomCt = count str sym (bottom + 1)
              middleCt = bottomCt - topCt
              refCt = refFstOcc sym
          in if middleCt > 0
               then match (refCt + topCt) (refCt + bottomCt - 1) syms
               else 0

(为简洁起见进行了精简 - 我正在通过 map 记住 refCol 中符号的首次出现，以及其他一些细节)。

编辑:示例使用:

matching "AT$TCTAGT" "$AACGTTTT" "TCG"

应该是 1(假设我没有输错任何东西)。

现在，我将 top 指针和 bottom 指针之间的所有内容重新计算两次，当我计算一百万个字符的 DNA 字符串时只有 4字符的可能选择(分析告诉我这也是最大的瓶颈，我 48% 的时间用于 bottomCt，大约 38% 的时间用于 topCt)。作为引用，当计算一百万个字符串并尝试匹配 50 个模式(每个模式都在 1 到 1000 个字符之间)时，程序运行大约需要 8.5 到 9.5 秒。

但是，如果我尝试实现以下功能:

countBetween :: Ord a => [a] -> a -> Int -> Int -> (Int, Int)
countBetween list sym top bottom =
  let (topList, bottomList) = splitAt top list
      midList = take (bottom - top) bottomList
      getSyms = length . filter (== sym)
  in (getSyms topList, getSyms midList)

(通过更改匹配函数进行补偿)，程序运行时间为 18 到 22 秒。

我也试过传入一个 Map，它可以跟踪以前的调用，但它也需要大约 20 秒才能运行并耗尽内存。

同样，我缩短了 length 。将 (== sym) 过滤到 fold，但同样 - foldr 需要 20 秒，foldl 需要 14-15 秒。

那么通过重写代码来优化此代码的正确 Haskell 方法是什么？ (具体来说，我正在寻找不涉及预计算的东西 - 我可能不会非常重用字符串 - 这解释了为什么会发生这种情况)。

编辑:更清楚地说，我正在寻找的是以下内容:

a) 为什么这种行为会发生在 Haskell 中？惰性求值如何发挥作用，编译器为重写 count 和 countBetween 函数进行了哪些优化，可能还涉及哪些其他因素？

b) 什么是简单的代码重写来解决这个问题，这样我就不会多次遍历列表？我正在寻找专门解决该问题的东西，而不是回避它的解决方案。如果最终答案是，count 是编写代码的最有效方式，那为什么呢？

Answer 1

我不确定惰性计算与代码的性能有多大关系。我认为主要问题是使用字符串——它是一个链表——而不是性能更高的字符串类型。

请注意，在您的 countBetween 函数中调用:

  let (topList, bottomList) = splitAt top list

会重新创建topList对应的linked link 意思更多分配。

比较 splitAt 与使用 take n/drop n 的标准基准可以在这里找到:http://lpaste.net/174526 . splitAt 版本是大约慢了 3 倍，当然还有更多的分配。

即使您不想“预先计算”计数，您也可以改进只需切换到 ByteString 或 Text 即可。

定义:

countSyms :: Char -> ByteString -> Int -> Int -> Int
countSyms sym str lo hi =
  length [ i | i <- [lo..hi], BS.index str i == sym ]

然后:

countBetween :: ByteString -> Char -> Int -> Int -> (Int,Int)
countBetween str sym top bottom = (a,b)
  where a = countSyms sym str 0 (top-1)
        b = countSyms sym str top (bottom-1)

此外，不要在大列表上使用 reverse - 它会重新分配整个列表。只需反向索引到 ByteString/Text。

内存计数可能有帮助也可能没有帮助。这完全取决于它是如何完成的。