能否使图二分评分例程更高效？

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 之后，它停止成为向量，所以您将需要使用 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)))
   "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次。
                执行时间平均值：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次。
                执行时间平均值：55.667037 µs
       执行时间标准差：1.035787 µs
      执行时间下四分位数：54.642948 µs（2.5%）
      执行时间上四分位数：57.269671 µs（97.5%）
                      开销使用：1.942216 ns

---

正如我所说，那就是`vec`。由于它，你在一个包含N个元素的集合上不是一次而是两次进行遍历。我看到你在SO上的问题，其中一个回答建议用`next`替换`rest`，然后检查该集合不是nil - 如果最初根本无法创建向量，我认为你应该这样做，而不是使用`vec`。

---

抱歉重复发布(https://stackoverflow.com/questions/73847837/can-i-make-this-clojure-code-scoring-a-graph-bisection-more-efficient 供人偶然发现)我已经在那里尝试了解决方案，确实认为下一个与剩余的解决方案最好。

---

只是提醒一下，`empty?` 在 1.12.0-alpha1 中已更改，以利用 `counted` 集合，从而避免不必要的 seq 'ing 集合，因此这可能实际上有助于原始代码。