arrays - 加速 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)使用 [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)]

但是这样的注释会禁用许多优化(编译分析总是如此)，因此您从分析中获得的图片可能会倾斜，并且与优化程序中实际发生的情况不同。