4

我想将一个序列分成前 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？还是我需要自己写？

4

3 回答 3

5

标准库中没有这样的功能。您已经编写的简单实现实际上仅对于 的小值的特殊情况效率低下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而不是负/零/正数类型之一。

编辑 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：早期版本的可读性差仍然让我很恼火，所以我现在将我的实现拆分为多个函数。

于 2013-09-11T12:50:20.600 回答
2

您可以使用诸如 sorted-set 之类的数据结构，它目前实现为clojure.lang.PersistentTreeSet。这样，您可以避免在获得前 n 个元素之前进行排序（我会说）。

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

#{90 10 1}

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

(split-at n previous-sorted-set)

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

于 2013-09-11T12:06:12.517 回答
0

看起来可能用于手指树

(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)]
于 2013-09-12T04:17:16.577 回答