performance - 我可以使此 Clojure 代码(计算图形二分法)更高效吗？

Question

我的代码大部分时间都在对二分法进行评分:确定有多少条边从一组节点交叉到另一组节点。

假设 bisect 是图的一半节点(整数)的集合，而 edges 是(有向)边的列表 [ [n1 n2] ...] 其中 n1,n2 也是节点。

(defn tstBisectScore
  "number of edges crossing bisect"
  ([bisect edges]
   (tstBisectScore bisect 0 edges))

  ([bisect nx edge2check]
   (if (empty? edge2check)
     nx

     (let [[n1 n2] (first edge2check)
           inb1 (contains? bisect n1)
           inb2 (contains? bisect n2)]
       (if (or (and inb1 inb2)
               (and (not inb1) (not inb2)))
         (recur bisect nx (rest edge2check))
         (recur bisect (inc nx) (rest edge2check))))

     )))

我通过对该代码的执行进行抽样(使用 VisualVM)获得的唯一线索显示大部分时间花在 clojure.core$empty_QMARK_ 上，其余大部分时间花在 clojure 上。核心 $contains_QMARK_。 (first 和 rest 只占用一小部分时间。)(参见附件 。

关于如何收紧代码有什么建议吗？

Answer 1

首先，我要说的是，您的个人资料扩展得不够深入。 empty? 通常不是一个昂贵的函数。它占用您所有时间的原因几乎可以肯定是因为您函数的输入是一个惰性序列，而 empty? 是一个可怜的 sap，它的工作是首先查看其元素。所以一直在 empty? 中的时间可能实际上是您应该考虑生成输入序列的任何内容的时间。您可以通过分析 (tstBisectScore bisect (doall edges)) 并与您现有的 (tstBisectScore bisect edges) 配置文件进行比较来确认这一点。

假设我的假设是正确的，那么您实际工作量的近 80% 可能是生成二等分，而不是对它们进行评分。因此，我们在此函数中所做的任何事情最多可以使我们获得 20% 的加速，即使我们将整个事情替换为 (map (constantly 0) edges)。

不过，还有许多地方需要改进。假设我们已经确定生成输入参数的效率已达到我们所能达到的最高效率，并且我们需要更快的速度。

• 急切地迭代某些东西时，使用 next 而不是 rest。 rest 的要点是它有点懒，并且总是返回一个非 nil 序列，而不是查看是否有下一个元素。如果您知道无论如何都需要下一个元素，请使用 next 一次获取这两个信息位。
• 一般来说，empty? 不是测试序列的有效方法。 (defn empty? [x] (not (seq x))) 显然是一个浪费的not。如果您关心效率，请改为编写 (seq x)，并反转您的 if 分支。更好的是，如果您知道 x 是 next 调用的结果，那么它永远不会是空序列:只有 nil，或非空序列。所以只写 (if x ...)。
• >

  (or (and inb1 inb2)
      (and (not inb1) (not inb2)))
  

  是编写(= inb1 inb2)的一种非常昂贵的方式。

所以对于初学者来说，你可以这样写

(defn tstBisectScore
  ([bisect edges] (tstBisectScore bisect 0 (seq edges)))
  ([bisect nx edges]
   (if edges
     (recur bisect (let [[n1 n2] (first edges)
                         inb1 (contains? bisect n1)
                         inb2 (contains? bisect n2)]
                     (if (= inb1 inb2) nx (inc nx)))
            (next edges))
     nx)))

请注意，我还重新安排了一些内容，将 if 和 let 放在 recur 中，而不是重复另一个recur 的参数。这不是一个非常流行的样式，并且与效率无关。在这里，它有一个教学目的:将您的注意力吸引到您错过的这个函数的基本结构上。您的整个函数具有结构(if xs (recur (f acc x) (next xs)))。这正是 reduce 已经做到的!

我可以写出使用 reduce 的翻译，但首先我还要指出你还有一个隐藏在其中的 map 步骤，将一些元素映射到1 和一些到 0，然后你的 reduce 阶段只是对列表求和。因此，我们不使用惰性序列来做到这一点，而是使用转换器，并避免分配中间序列:

(defn tstBisectScore [bisect edges] 
  (transduce (map (fn [[n1 n2]]
                    (if (= (contains? bisect n1)
                           (contains? bisect n2)
                       0, 1)))
             + 0 edges))

这样代码会少很多，因为您让现有的抽象为您完成工作，而且它应该更有效率，因为 (a) 这些抽象不会犯您犯的局部错误，并且 (b) 它们还处理分块序列更有效，这是一个相当大的提升，在使用 map、range 和 filter 等基本工具时经常出现。