我能否使评分图二分的程序更高效？

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? x) 只是 (not (seq x))，而 seq 可能会很贵。如果您确定 edge2check 总是，例如，一个向量，那么您可以用 (zero? (count edge2check)) 替换那个 (empty? edge2check)。或者更低级别的 (.isEmpty ^java.util.List edge2check)。但鉴于您在它上调用 rest，它在 recur 之后就不再是向量了，所以您必须用 subvec 替换 rest。或者，另外一种方法是反转向量中元素的顺序，并相应地使用 peek 和 pop 替代 first 和 rest。

与 contains? 类似 - 如果您始终确定 bisect 是一个持久集，则可以用 (.contains ^clojure.lang.IPersistentSet bisect x) 替换 (contains? bisect x)。

Comments

非常感谢 @Eugene，这些建议非常出色。我已经实现了您提出的 peek/pop 和 IPersistentSet 思路。

   (defn tstBisectScore2
     ([bisect edges]
      (tstBisectScore2 bisect 0 (vec edges)))
   
     ([bisect nx edge2check]
      (if (zero? (count edge2check))
        nx
   
        (let [[n1 n2] (peek edge2check)
              inb1 (.contains ^clojure.lang.IPersistentSet bisect n1)
              inb2 (.contains ^clojure.lang.IPersistentSet bisect n2)]
        (if (or (and inb1 inb2)
                  (and (not inb1) (not inb2)))
            (recur bisect nx (pop edge2check))
            (recur bisect (inc nx) (pop edge2check))))
   
        )))

但是新旧版本的计时结果显示只略有改善（6%）？

   (time (dotimes [i 100000]
           (hpclj.test/tstBisectScore1 rp g6fe)))
   "经过时间：6103.62275 毫秒"

   (time (dotimes [i 100000]
        (hpclj.test/tstBisectScore2 rp g6fe)))
   "经过时间：5732.2645 毫秒"

我知道 Clojure 的计时有一些难点（启动？），所以这个简单的实验可能不足够。不管怎样再次感谢。

---

对于基准测试，最好使用 Criterium 这样的工具。不过，除了这个之外，调用 `vec` 恐怕是目前耗费时间的部分。我在原始回答中提到的是，如果可能的话，`g6fe` 应该一开始就是一个向量。

---

不，`g6fe` 是作为边的列表（来自loom图库）。我之前没有玩过Criterium，但会尝试一下。

---

越来越好奇了！Criterium让你的一些想法看起来慢了一点（3%）

   (criterium/quick-bench (tstBisectScore1 rp g6fe))
   
   评估次数：6个样本中的1858次调用，共11148次。
                平均执行时间：54.087476微秒
      执行时间标准偏差：387.196475纳秒
      执行时间下四分位数：53.651538微秒（2.5%）
      执行时间上四分位数：54.485682微秒（97.5%）
                      开销：1.942216纳秒
   
   (criterium/quick-bench (tstBisectScore2 rp g6fe))
   
   评估次数：6个样本中的1877次调用，共11262次。
                平均执行时间：55.667037微秒
      执行时间标准偏差：1.035787微秒
      执行时间下四分位数：54.642948微秒（2.5%）
      执行时间上四分位数：57.269671微秒（97.5%）
                      开销：1.942216纳秒

---

正如我所说的，就是那个`vec`。因为你因为它的原因要遍历N个元素不止一次。我看到了你在SO上的问题，其中一个答案建议用`next`替换`rest`，然后检查集合是否不是nil - 如果你根本无法创建向量，我认为你应该做相反的事情而不是使用`vec`。

---

对不起跨发帖（[https://stackoverflow.com/questions/73847837/can-i-make-this-clojure-code-scoring-a-graph-bisection-more-efficient](https://stackoverflow.com/questions/73847837/can-i-make-this-clojure-code-scoring-a-graph-bisection-more-efficient)，以防有人偶然看到），我在那里尝试了那个解决方案，的确，next vs rest的方案似乎是最好的。

---

注意，`empty?` 在 1.12.0-alpha1 中已更改，可利用 `counted` 集合，从而避免无谓地系列化集合，这实际上可能有助于原始代码。