我能使评分图二分法的这个程序更加高效吗？

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 总是，例如，一个向量，那么你可以将那个 (empty? edge2check) 替换为 (zero? (count edge2check))。或者更低层次的 (.isEmpty ^java.util.List edge2check)。但是考虑到你调用 rest 之上的它，它在 recur 之后就不再是向量了，所以你应该使用 subvec 而不是 rest。或者，你还可以反过来将这些向量中的元素顺序颠倒，并使用 peek 和 pop 分别代替 first 和 rest。

与contains?类似——如果你始终确信bisect是一个持久集，你可以将(contains? bisect x)替换为(.contains ^clojure.lang.IPersistentSet 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 µs
       执行时间标准差：387.196475 ns
      下四分位数执行时间：53.651538 µs ( 2.5%)
      上四分位数执行时间：54.485682 µs (97.5%)
                      开销：1.942216 ns
   
   (criterium/quick-bench (tstBisectScore2 rp g6fe))
   
   评估次数：在6个样本中的1877次调用中共有11262次。
       平均执行时间：55.667037 µs
      执行时间标准差：1.035787 µs
      下四分位数执行时间：54.642948 µs ( 2.5%)
      上四分位数执行时间：57.269671 µs (97.5%)
                      开销：1.942216 ns

---

正如我说的，就是那个 `vec`。由于它，你要遍历集合中的 N 个元素两次，而不是一次。我见过你在 Stack Overflow 上的问题，其中一个答案建议将 `rest` 替换为 `next`，然后检查集合是否为空 - 如果你根本无法创建向量，我认为你应该做这件事，而不是使用 `vec`。

---

抱歉重复发帖，以防有人偶然看到（[链接](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` 集合，因此这样可以避免无谓地序列集合，这实际上可能有助于原始代码。