我能否使这个用于评分图二分算法的例程更加高效？

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) essentially means (not (seq x)), and calling seq may be costly. If you are certain that edge2check is always, for instance, a vector, then you would replace that (empty? edge2check) with (zero? (count edge2check)). Or, at a lower level, (.isEmpty ^java.util.List edge2check). But given that you call rest on it, it ceases to be a vector after recur, so you would have to use subvec instead of rest. Alternatively, you could invert the order of the elements in that vector and use peek and pop instead of first and rest, respectively.

类似于 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次的11148次。
               执行时间平均值：54.087476微秒
      执行时间标准差：387.196475纳秒
      执行时间最小四分位数：53.651538微秒（2.5%）
      执行时间最大四分位数：54.485682微秒（97.5%）
                       开销：1.942216纳秒
   
   (criterium/quick-bench (tstBisectScore2 rp g6fe))
   
   评估次数：在6个样本中为1877次的11262次。
               执行时间平均值：55.667037微秒
      执行时间标准差：1.035787微秒
      执行时间最小四分位数：54.642948微秒（2.5%）
      执行时间最大四分位数：57.269671微秒（97.5%）
                       开销：1.942216纳秒

---

正如我说的，是那个`vec`。因为你因为`vec`而遍历了N个元素的集合，而不是一次。我在SO你的问题上看到，其中有一个答案建议用`next`代替`rest`，然后检查那个coll是否不是空的——我想这就是你该做的，而不是使用`vec`，如果你一开始根本不能创建一个向量的话。

---

很抱歉这种跨贴文章（如果有人不小心看到的话），我已经在其他地方尝试了解决方案，实际上最近的对比余数解决方案似乎是最好的。

---

请注意，`empty?` 在 1.12.0-alpha1 中已经更改，以便利用 `counted` 集合，因此可以避免无谓地推出集合，这实际上可能有助于原始代码。