Clojure:将序列拆分为前n个序列和其余序列？

Question

我想将一个序列拆分为前 n 个元素和其余元素。这是使用内置排序和分割的低效实现:

> (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 值较小的特殊情况效率较低，但在一般情况下完全没问题。

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

编辑:更多地考虑这一点，可能值得尝试编写一个实现，将序列强制转换为向量，然后进行就地快速选择将 n 个最佳元素划分到向量的开头。这应该相对容易做到，并且只要精心选择枢轴元素，就可以提供合理的更好性能。

编辑 2:我决定亲自尝试该实现。它在一些简单的测试用例中运行良好，但我不完全确定其中不存在可能在某些边缘情况下触发的逐一错误:

(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 的简单 bool 比较器函数，而不是负数/零/正数类型之一。

编辑3:我再次查看了 transient 的文档，发现我正在利用未定义的行为。实际上，上述版本可能始终按预期工作，但正确的版本仍然应该尊重语言文档。我将保留此答案中的先前版本，因为答案已被接受，但这里的版本按照文档要求使用 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:早期版本的可读性差仍然让我心痒痒，所以我现在将我的实现分成多个函数。