我能否使这个用于评估图分裂的例程更高效？

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毫秒"

i 知道 clojure 的计时有一些细节（启动时间？），所以这个简单的实验可能不够充分。无论如何再次感谢。

---

对于基准测试，最好使用像Criterium这样的工具。但除了这一点，`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个元素的集合，而不是一次，因此取消了数据结构“rest”。我曾看到你在Stack Overflow上的问题，其中一种回答建议用“next”替换“rest”，并检查集合不为空-如果一开始就不能创建向量，我想你应该做的是替换`vec`。

---

对于重复帖子表示歉意（如果在其他地方看到这个链接请小心），我在那里尝试了解决方案，实际上“与剩余的解决方案相比”似乎最好。

---

注意，`empty?` 在 1.12.0-alpha1 中已更改，利用 `counted` 集合来避免不必要地对集合进行序列化，所以这实际上可能有助于原始代码。