我如何使图的二分评分程序更高效？

Question

我的代码大部分时间都在评分二分：确定图中有多少边从一个节点集跨越到另一个节点集。

假设 bisect 是图 nodes 的一半的集合（整数），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。或者，作为替代方案，可以反转 those 向量的元素顺序，用 peek 代替 first，用 pop 代替 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)))
   "Elapsed time: 6103.62275 msecs"

   (time (dotimes [i 100000]
        (hpclj.test/tstBisectScore2 rp g6fe)))
   "Elapsed time: 5732.2645 msecs"

我知道对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个元素两次。我看到了你在SO上的问题，其中一个答案建议用`next`替换`rest`，并检查该集合不为空 - 如果你根本无法创建向量，我认为你应该这样做，而不是使用`vec`。

---

对于重复发布（如果有人误入此页），我为使用https://stackoverflow.com/questions/73847837/can-i-make-this-clojure-code-scoring-a-graph-bisection-more-efficient表示歉意。我已经在那里试验了解决方案，实际上，next 与 rest 的解决方案看起来最好。

---

提醒一下，在1.12.0-alpha1中，`empty?` 已经改变，以利用 `counted` 集合，从而避免不必要地序列化集合，这实际上可能有助于原始代码。