优化haskell代码

Question

我编写了下面的Haskell代码,它采用三元组(x,y,z)和三元组列表[(Int,Int,Int)]并查看列表中是否存在三元组(a,b,c) x == a和y == b如果是这种情况我只需要更新c = c + z,如果列表中没有这样的三元组,我只需在列表中添加三元组.

-- insertEdge :: (Int,Int,Int) -> [(Int, Int, Int)] -> [(Int, Int, Int)]

insertEdge (x,y,z) cs = 

if (length [(a,b,c) | (a,b,c) <- cs, a /= x || b /= y]) == (length cs) 

 then ((x,y,z):cs)) 

   else [if (a == x && b == y) then (a,b,c+1) else (a,b,c) | (a,b,c) <- cs]

在对我的代码进行分析后,看起来这个功能占用了65%的执行时间.

如何重新编写代码以提高效率？

Answer 1

其他答案是正确的,所以我想提供一些unasked-for建议:如何使用Data.Map(Int,Int)Int而不是list？

然后你的功能变成了 insertWith (+) (a,b) c mymap

Answer 2

跳出来的第一件事是条件:length检查整个列表,所以在最坏的情况下(更新最后一个元素),你的函数遍历列表三次:一次为过滤列表的长度,一次为长度cs,并且一旦找到要更新的元素.

但是,即使摆脱了额外的遍历,使用函数编写的最佳方法通常也需要遍历大部分列表.从函数的名称和花费了多少时间,我猜你是在反复调用它来构建数据结构？如果是这样,您应该强烈考虑使用更有效的表示.

例如,一个快速简单的改进是使用Data.Map,2元组中三元组的前两个元素作为键,第三元素作为值.这样您就可以避免进行如此多的线性时间查找/冗余遍历.

根据经验,Haskell中的列表只是一个合适的数据结构,当你所做的只是在列表中顺序走几次(理想情况下,只是一次)或从列表的头部添加/删除(即,使用它像堆栈一样).如果您正在搜索,过滤,更新中间的元素,或者 - 最糟糕的是 - 按位置编制索引,使用列表只会以泪流满面.

这是一个简单的例子,如果有帮助:

import qualified Data.Map as M

incEdge :: M.Map (Int, Int) Int -> ((Int, Int), Int) -> M.Map (Int, Int) Int
incEdge cs (k,v) = M.alter f k cs
    where f (Just n) = Just $ n + v
          f Nothing  = Just v

该alter函数只是插入/更新/删除所有滚动到一个.如果密钥不存在,则将密钥插入到映射中,如果密钥存在,则将值汇总.要逐步构建结构,您可以执行类似的操作foldl incEdge M.empty edgeList.测试一下,对于几千个随机边缘,带有列表的版本需要几秒钟,而Data.Map版本几乎是即时的.