optimization - 如何消除字符串遍历和列表理解中的成本中心

Question

我正在使用 Haskell 从生物信息学领域实现一个主题查找算法。除了说它是分支定界中值字符串搜索之外，我不会详细介绍该算法。我曾计划通过实现并发方法(以及后来的 STM 方法)来使我的实现更有趣，以便获得多核加速但在使用以下标志编译之后

$ ghc -prof -auto-all -O2 -fllvm -threaded -rtsopts --make main 

并打印配置文件我看到了一些有趣的东西(也许很明显):

COST CENTRE      entries  %time %alloc  
hammingDistance  34677951  47.6   14.7  
motifs           4835446   43.8   71.1  

很明显，无需接近多核编程就可以获得显着的加速(尽管这已经完成，我只需要找到一些好的测试数据并为此整理出标准)。

无论如何，这两个功能都是纯功能性的，绝不是并发的。他们也在做一些非常简单的事情，所以我很惊讶他们花了这么多时间。这是他们的代码:

data NukeTide = A | T | C | G deriving (Read, Show, Eq, Ord, Enum)

type Motif = [NukeTide] 

hammingDistance :: Motif -> Motif -> Int
hammingDistance [] [] = 0
hammingDistance xs [] = 0 -- optimistic
hammingDistance [] ys = 0 -- optimistic
hammingDistance (x:xs) (y:ys) = case (x == y) of
    True  -> hammingDistance xs ys
    False -> 1 + hammingDistance xs ys

motifs :: Int -> [a] -> [[a]]
motifs n nukeTides = [ take n $ drop k nukeTides | k <- [0..length nukeTides - n] ]

请注意，在 hammingDistance 的两个参数中，我实际上可以假设 xs 将是 x 长并且 ys 将小于或等于它，如果这为改进提供了空间。

如您所见，hammingDistance 计算两个基序(核苷酸列表)之间的汉明距离。主题函数接受一个数字和一个列表，并返回该长度的所有子字符串，例如:

> motifs 3 "hello world"
["hel","ell","llo","lo ","o w"," wo","wor","orl","rld"]

由于所涉及的算法过程非常简单，我想不出进一步优化它的方法。然而，我确实有两个关于我应该去哪里的猜测:

HammingDistance:我使用的数据类型(NukeTides 和 [])很慢/很笨拙。这只是一个猜测，因为我不熟悉他们的实现，但我认为定义我自己的数据类型，虽然更易读，但可能涉及比我想要的更多的开销。模式匹配对我来说也是陌生的，我不知道这是微不足道的还是昂贵的。

主题:如果我没看错的话，70% 的内存分配是由主题完成的，我认为有时必须进行垃圾收集。再次使用通用列表可能会减慢我或列表理解的速度，因为我非常不清楚这样做的成本。

有人对这里的常规程序有什么建议吗？如果数据类型是问题所在，那么数组会是正确的答案吗？ (我听说它们是装在盒子里的)

谢谢您的帮助。

编辑:我突然想到，如果我描述调用这两个函数的方式可能会很有用:

totalDistance :: Motif -> Int
totalDistance motif = sum $ map (minimum . map (hammingDistance motif) . motifs l) dna

此函数是另一个函数的结果，并在树中的节点周围传递。在树中的每个节点上，对核苷酸(长度 <= n，即如果 == n 则它是叶节点)进行评估，使用 totalDistance 对节点进行评分。从那时起，它就是典型的分支定界算法。

编辑:约翰要求我打印出我所做的改变，这实际上消除了图案的成本:

scoreFunction :: DNA -> Int -> (Motif -> Int)
scoreFunction dna l = totalDistance
    where
        -- The sum of the minimum hamming distance in each line of dna
        -- is given by totalDistance motif
        totalDistance motif = sum $ map (minimum . map (hammingDistance motif)) possibleMotifs
        possibleMotifs = map (motifs l) dna -- Previously this was computed in the line above

我在原始帖子中没有说清楚，但 scoreFunction 只调用一次，结果在树遍历/分支中传递并绑定(bind)并用于评估节点。回想起来，在每一步重新计算图案并不是我做过的最聪明的事情之一。

Answer 1

您对 motifs 的定义看起来它做的遍历比必要的多得多，因为 drop 的每个应用程序必须从头开始遍历列表。我会使用 Data.List.tails 来实现它反而:

motifs2 :: Int -> [a] -> [[a]]
motifs2 n nukeTides = map (take n) $ take count $ tails nukeTides
  where count = length nukeTides - n + 1

GHCi 中的快速比较显示了差异(使用 sum . map length 强制评估):

*Main> let xs = concat (replicate 10000 [A, T, C, G])
(0.06 secs, 17914912 bytes)
*Main> sum . map length $ motifs 5 xs
199980
(3.47 secs, 56561208 bytes)
*Main> sum . map length $ motifs2 5 xs
199980
(0.15 secs, 47978952 bytes)