algorithm - 在 Haskell 中具有良好性能的简单循环

Question

我刚开始学习 Haskell，我对如何为通常用 C 或 Python 编写的简单代码获得匹配的性能感兴趣。考虑以下问题。

给你一长串 1 和 0 的长度 n。对于长度为 m 的每个子串，我们要输出该窗口中 1 的数量。即输出在 0 和 m 之间有 n-m+1 个不同的可能值。

在 C 中，这非常简单，时间与 n 成比例，并且使用额外空间(在存储输入所需的空间之上)与 m 位成比例.您只需计算长度为 m 的第一个窗口中 1 的数量，然后维护两个指针，一个指向窗口的开头，一个指向窗口的结尾，并根据是否指向一个指针来递增或递减1 和其他指向 0 或相反。

是否有可能在 Haskell 中以纯函数的方式获得相同的理论性能？

一些糟糕的代码:

chunkBits m = helper
  where helper [] = []
        helper xs = sum (take m xs) : helper (drop m xs)

main = print $ chunkBits 5 [0,1,1,0,1,0,0,1,0,1,0,1,1,1,0,0,0,1]

Answer 1

C代码

这是您描述的 C 代码:

int sliding_window(const char * const str, const int n, const int m, int * result){
  const char * back  = str;
  const char * front = str + m;
  int sum = 0;
  int i;

  for(i = 0; i < m; ++i){
     sum += str[i] == '1';
  }

  *result++ = sum;

  for(; i < n; ++i){
    sum += *front++ == '1';
    sum -= *back++  == '1';
    *result++ = sum;
  }
  return n - m + 1;
}

算法

上面的代码显然是 O(n)，因为我们有 n 次迭代。但让我们退后一步，看看底层算法:

1. 对前 m 个元素求和。将其保留为 sum。 O(m)
2. 我们的第一个窗口有 sum 1。 O(1)
3. 直到我们用完原始字符串:O(n)
   1. “滑动”窗口。 O(1)
      • 如果我们通过滑动 O(1) 获得 '1'，则将 1 添加到 sum
      • 如果我们通过滑动 O(1) 丢失了一个 '1'，则从 sum 中减去 1
   2. 将 sum 推到结果上。 O(1)

因为 n > m(否则没有窗口)，O(n) 成立。

塑造一个 Haskell 变体

这基本上是一个左扫描 (scanl)，它提供了一种获取 (2.1.) 中差异列表的方法。所以我们所需要的只是一种以某种方式滑动的方法:

slide :: Int -> [Char] -> [Int]
slide m xs = zipWith f xs (drop m xs)
  where
    f '1' '0' = -1  -- we lose a one
    f '0' '1' =  1  -- we gain a one
    f  _   _  =  0  -- nothing :/

那是 O(n)，其中 n 是我们列表的长度。

slidingWindow :: Int -> [Char] -> [Int]
slidingWindow m xs = scanl (+) start (slide m xs)
 where
   start = length (filter (== '1') (take m xs))

那是 O(n)，与 C 中相同，因为两者使用相同的算法。

注意事项

在现实生活中的应用程序中，您总是会使用 Text 或 ByteString 而不是 String，因为后者是 的列表>Char 开销很大。由于你只使用了'1'和'0'的字符串，你可以使用ByteString:

import           Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as BS
import           Data.List (scanl')

slide :: Int -> ByteString -> [Int]
slide m xs = BS.zipWith f xs (BS.drop m xs)
  where
    f '1' '0' = -1
    f '0' '1' =  1
    f  _   _  =  0

slidingWindow :: Int -> ByteString -> [Int]
slidingWindow m xs = scanl' (+) start (slide m xs)
 where
   start = BS.count '1' (BS.take m xs)