有没有更好的方法在Clojure中将元素插入已排序列表的代码？

Question

我正在完成第7个练习，位于https://iloveponies.github.io/120-hour-epic-sax-marathon/one-function-to-rule-them-all.html。我有一个解决方案，但由于期望的输出是列表，所以我不得不在一些输出中添加“reverse”。这似乎有点繁琐。

以下是我的代码：

(defn insert [sorted-seq n]
  (loop [output ()
         my-seq sorted-seq]
    (cond 
     (nil? (first my-seq)) 
       (conj output n)
     (nil? (first (rest my-seq))) 
       (reverse (conj output (first my-seq) n))
     :else
      (if (> (first (rest my-seq)) n (first my-seq))
        (reverse (apply conj output (first my-seq) n (rest my-seq)))
        (recur (conj output (first my-seq)) (rest my-seq))))))

(insert [] 2)      ;=> (2)
(insert [1 3 4] 2) ;=> (1 2 3 4)
(insert [1] 2)     ;=> (1 2)

有没有更好的方法编写这个代码以提高效率，而不需要反转输出？此外，前两个条件似乎很笨拙。是否有更好的方法呢？

- jbrown

Answer 1

@A.Webb的解决方案是你需要的，但我把这个留给未来的访问者。

我认为你稍微把问题复杂化了一点。

总的思路是：

1. 找到需要插入元素的位置。
2. 在那个位置把序列分成两半。
3. 连接第一个结果序列、元素和第二个结果序列。

你可以使用split-with结合1和2，这个函数可以根据谓词把序列分成两部分，一部分满足谓词，另一部分不满足。

因此，在Clojure中，可以这样写：

(defn insert [coll n]
   (let [[l r] (split-with #(< % n) coll)]
       (concat l [n] r))

- soulcheck

---

我猜比较应该是与n而不是3相比较？ - Alex

@soulcheck 我们还没有涉及到split-with，但我会去了解一下。看起来很方便。谢谢。 - jbrown

@jbrown 如果这不是一个递归练习的话，那可能就是你要使用的东西。 - soulcheck

如果这不是一项练习，你根本不会使用排序列表：它们对于此任务来说是一个糟糕的数据结构。排序集、作为多重集合使用的排序映射、堆或其他一些东西都是更好的选择。 - amalloy

Answer 2

我认为这个练习的重点是要使用递归，而不一定要产生最符合惯用方法的代码。通过使用一个向右执行conj操作的数据结构，如向量，可以避免反转。

(defn insert [sorted-seq n]
  (loop [s sorted-seq, a []]
    (cond 
      (empty? s)       (conj a n)
      (< (first s) n)  (recur (rest s) (conj a (first s)))
      :else            (apply conj a n s))))

- A. Webb

---

是的，你说得对。我匆匆浏览了其他问题，没有注意到递归部分。 - soulcheck

我使用了一个向量，但注意到输出结果是一个列表。我不知道可能的原因 - 也许有一个我应该使用的函数。或者说根本没有原因...但还是谢谢。我的代码里有太多条件了，你的更简洁。 - jbrown

Answer 3

如果你准备好使用适当的递归，那么你可以很简单地使用列表来完成这个任务：

(defn insert [ss n]
  (if (empty? ss)
    (list n)
    (let [[x & xs] ss]
      (if (< n x)
        (cons n ss)
        (cons x (insert xs n))))))

• 如果你想让它在长序列上工作而不会导致堆栈溢出，可以将主体包装在lazy-seq中。
• 它仍然比A. Webb的解决方案慢得多。

- Thumbnail