加速Data.Array行提取和过滤

Question

我的应用程序中有一个非常简单的功能,它可以完成大量工作并占用最多的计算时间:

f :: Int -> Array (Int,Int) Int -> [Int]
f x arr = [v | v <- range (l,u), vv <- [g!(x,v)], vv /= 0]
          where ((_,l), (_,u)) = bounds arr

这样做是:x从数组中的索引处提取一行arr并返回包含元素的所有列索引\= 0.因此,例如,给定以下带边界的矩阵((0,0),(2,2)):

arr =  [[0, 0, 5], 
        [4, 0, 3],
        [0, 3, 1]]   -- for simplicity in [[a]] notation

预期的产出是

f 0 arr == [2] 
f 1 arr == [0,2]
f 2 arr == [1,2]

我如何加速f和分析f(列表构造,数组访问等)实际占用大部分计算时间的更多细节？

谢谢!

Answer 1

f x arr = [v | v <- range (l,u), vv <- [g!(x,v)], vv /= 0]

我想g是一个错字，应该是arr。编译器可能能够优化前者和后者，而
不是range (l,u)use ，但更惯用（也许编译器也无法优化前者）。不要创建无意义的单元素列表，可以使用直接测试，[l .. u][l .. u]

f x arr = [v | v <- [l .. u], arr!(x,v) /= 0]

编译器可能再次能够将前者重写为后者，但是a）后者更清晰，并且b）不存在编译器不能的风险。

要找出时间花在哪里，您可以插入成本中心注释，

f x arr = [v | v <- {-# SCC "Range" #-} [l .. u], {-# SCC "ZeroTest" #-} (arr!(x,v) /= 0)]

但是这样的注释会禁用许多优化（为分析而编译总是会这样做），因此从分析中获得的图片可能会有所偏差，并且与优化程序中实际发生的情况不同。