Clojure:将序列拆分为top-n和rest？

Question

我想把序列分解成顶级元素和其他元素。下面是一个使用内置排序和拆分-at的低效实现：

> (defn split-top-n
    [n comp coll]
    (split-at n (sort comp coll)))

> (split-top-n 2 #(- %2 %1) (list 6.2 5.1 88.0 90.1 1.2 16.9))
[(90.1 88.0) (16.9 6.2 5.1 1.2)]

是否有一个高效的Clojure内置的这一点？还是我需要自己写？

Answer 1

标准库中没有这样的功能。您已经编写的简单实现实际上只对n值较小的特殊情况没有效率，但在一般情况下非常好。

只要您不知道当前实现中的这个函数在整个应用程序中确实是一个重要的性能瓶颈，编写一个更复杂的版本可能是浪费精力。

编辑：考虑到这一点，可能值得尝试编写一个将序列强制放入向量中的实现，然后执行就地Quickselect将n最佳元素划分到向量的开头。这应该是相对容易做到的，并可以提供一个合理的更好的性能，只要您的枢轴元素是正确的选择。

编辑2：我决定自己尝试这个实现。对于一些简单的测试用例，它工作得很好，但我不完全确定在某些边缘案例中是否存在可能触发的个别but：

(defn split-top-n
  [n comp coll]
  (let [v (transient (vec coll))]
    (loop [start 0, end (count v)]
      (when (> end n)
        (let [pos (loop [i (inc start), pos start]
                    (if (< i end)
                      (if (comp (v i) (v start))
                        (let [pos* (inc pos)]
                          (assoc! v, i (v pos*), pos* (v i))
                          (recur (inc i) pos*))
                        (recur (inc i) pos))
                      (do
                        (assoc! v, start (v pos), pos (v start))
                        pos)))]
          (if (< pos n)
            (recur (inc pos) end)
            (recur start pos)))))
    (split-at n (persistent! v))))

澄清:这需要为comp提供一个简单的布尔比较器函数，而不是一个负/零/正数类型。

编辑3：我再次查看了瞬变文档，并注意到我正在利用未定义的行为。实际情况可能是，上述版本实际上总是按预期工作，但正确的版本仍应尊重语言文档。我将在这个答案中保留上一个版本，因为它已经接受了答案，但是这里有一个版本，它使用assoc!的返回值作为文档所要求的：

(defn swap-in!
  [v i j]
  (assoc! v, i (v j), j (v i)))

(defn quickpartition!
  [comp v start end]
  (loop [v v, i (inc start), pos start]
    (if (< i end)
      (if (comp (v i) (v start))
        (recur (swap-in! v i (inc pos)) (inc i) (inc pos))
        (recur v (inc i) pos))
      [(swap-in! v start pos) pos])))

(defn split-top-n
  [n comp coll]
  (loop [v (transient (vec coll)), start 0, end (count v)]
    (if (> end n)
      (let [[v* pos] (quickpartition! comp v start end)]
        (if (< pos n)
          (recur v* (inc pos) end)
          (recur v* start pos)))
      (split-at n (persistent! v)))))

编辑4：早期版本的可读性很差，所以我现在已经将实现分成了多个函数。

Answer 2

您可以使用数据结构(如排序集)，该数据结构目前被实现为clojure.lang.PersistentTreeSet.。这样你就可以在得到你的前n个元素之前避免排序(我想说)。

(-> (sorted-set-by >) 
    (conj 90) 
    (conj 10) 
    (conj 1))

#{90 10 1}

现在您可以调用拆分-at函数：

(split-at n previous-sorted-set)

但这取决于您是否需要/是否可以使用排序集。

Answer 3

看起来可能是手指树的一种用途

(require '[clojure.data.finger-tree :as ft])
(def css (apply ft/counted-sorted-set (list 6.2 5.1 88.0 90.1 1.2 16.9)))
(ft/ft-split-at css 3)

[(1.2 5.1 6.2) 16.9 (88.0 90.1)]