我能使这个用于评估图二分的惯例更高效吗？

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? 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个元素的集合两次，所以它使你的 idea 看起来略微（3%）更慢。我看到了你在 Stack Overflow 上的问题，其中一个答案建议将 `rest` 替换为 `next`，然后检查集合是否为 nil - 我认为如果你根本不能创建向量的话，你应该这么做，而不是使用 `vec`。

---

抱歉，我进行了交叉发帖（如果有人偶然看到了这个链接），我就在那里尝试了解决方案，并且确实 next vs rest 的解决方案看起来最佳。

---

注意：`empty?` 在 1.12.0-alpha1 中已更改，以利用 `counted` colls 并从而避免无需序列化 coll，这实际上可能有助于原始代码。