我能否使这个图分割评分的例程更高效？

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

我知道测量 Clojure 有细节问题（启动时间？），因此这可能是一个不充分的简单实验。无论如何，再次感谢。

---

对于基准测试，最好使用像 Criterium 这样的工具。但是除了这个，调用 `vec` 可能是现在所耗费时间的原因。我在最初的回答中所说的是，如果可能的话，`g6fe` 应该一开始就是向量。

---

不，这是一个 `g6fe` 边缘列表（来自 loom 图包）。我之前没有玩过 Criterium，但我将要尝试。

---

越来越奇了！Criterium 使你的想法看起来稍慢（3%）。

   (criterium/quick-bench (tstBisectScore1 rp g6fe))
   
   评估次数：6 次样本中的 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 次样本中的 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` 的做法是不对的。

---

对于跨贴，我为此道歉（如果有人偶然看到这个链接），我已在那里对解决方案进行了实验，并且确实发现下一个与剩余部分解决方案似乎最好。

---

请注意，从1.12.0-alpha1开始，“empty?”发生了变化，以利用“counted”收集来避免无谓地对收集进行序列化，这实际上可能有助于原始代码。