我能否把这个用于评分图分解的程序变得更加高效？

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? 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的工具。但 aside 此外，`vec` 的调用可能就是现在耗费时间的原因。我在原始回答中意思是，如果可能的话，`g6fe` 应该最初就是一个向量。

---

不，`g6fe`是以边的列表形式出现的（来自loom图包）。我以前没有玩过Criterium，但我将尝试一下。

---

越来越奇怪了！Criterium让你的想法感觉稍微（3%）慢一些

   (criterium/quick-bench (tstBisectScore1 rp g6fe))
   
   评估次数：11148，在1858次调用中的6个样本中。
                平均执行时间：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))
   
   评估次数：11262，在1877次调用中的6个样本中。
       平均执行时间：55.667037 µs
      执行时间标准差：1.035787 µs
      下四分位数执行时间：54.642948 µs（2.5%）
      上四分位数执行时间：57.269671 µs（97.5%）
                      使用开销：1.942216 ns

---

正如我所说的，就是那个`vec`。因为你因为它而对包含N个元素的集合进行了两次遍历。我看到你在SO上的问题，其中一个答案建议用`next`替换`rest`，并检查col不为空 - 如果你根本不能创建向量，我想你最好是这样做，而不是使用`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` 集合，从而避免了无谓地序列集合，这可能会对原始代码有所帮助。