我可以让这个 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.core$contains_QMARK_. （first并且rest只花费一小部分时间。）（见附件。

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

Answer 1

首先我想说的是，你的个人资料扩展得不够深入。empty?一般来说，这不是一个昂贵的函数。它占用您所有时间的原因几乎可以肯定是因为您的函数的输入是一个惰性序列，并且empty?是可怜的傻瓜，其工作是首先查看其元素。empty?因此，实际上，您应该考虑生成输入序列的所有时间。您可以通过分析(tstBisectScore bisect (doall edges))并与您现有的(tstBisectScore bisect edges).

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

尽管如此，仍有许多地方需要改进。假设我们已经确定生成输入参数的效率尽可能高，并且我们需要更快的速度。

• 当急切地迭代某些内容时，请使用next而不是rest. 要点rest是它有点懒，并且总是返回一个非零序列，而不是查看是否有下一个元素。如果您知道无论如何都需要下一个元素，请使用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，然后您的归约阶段只是对列表求和。因此，我们将使用转换器，而不是使用惰性序列来做到这一点，并避免分配中间序列：

(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。