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

Question

我在Haskell开始,并且对如何获得我通常用C或Python编写的简单代码的匹配性能感兴趣.考虑以下问题.

给你一长串1和0的长串n.我们希望为每个长度子串输出m该窗口中1的数量.也就是说,输出具有n-m+1不同的可能值0,m包括在内.

在C中,这与在时间上成比例n并且使用与m比特成比例的额外空间(在存储输入所需的空间之上)非常简单.你只计算第一个长度窗口中的1的数量,m然后保持两个指针,一个指向窗口的开始,一个指向结束,并根据是否指向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. 我们的第一个窗口有sum1个.O(1)
3. 直到我们用完原始字符串:O(n)
   1. "滑动"窗口.O(1)
      • sum如果我们'1'通过滑动O(1)获得a ,则加1
      • sum如果我们'1'通过滑动O(1)丢失a ,则减去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)