如何尽可能有效地将一个元素追加到列表中

Question

CLOJURE 代表勇敢和真实 的第 4 章有一个练习：创建一个 append 函数，将新条目附加到列表中。

最有效的方法是什么？

根据我对数据类型的一般理解，如果 conj 将元素添加到列表中，那就意味着一致地附加到列表要么是愚蠢的，要么选择使用列表类型是愚蠢的。

无论如何，我写的解决方案是这样的

(defn append
  [lst item]
  (into '() (conj (into '() lst) item)))

嗯，这实际上与我相信的相同

(defn append
  [lst item]
  (reverse (conj (reverse lst) item)))

，所以可能成本很高，因为我将列表反转了两次？

我能想到的另一种解决方案是

(defn append
  [lst item]
  (apply list (conj (apply vector lst) item)))

但它们似乎都遍历了值序列两次，所以我不明白为什么任何一个应该比另一个更好。

是否有完成任务的正确方法？

Answer 1

conj 在列表的开头而不是末尾添加新项目是有原因的。因为你必须遍历列表才能在其末尾添加一些内容。这不是很有效。这是因为链表的性质。这就是为什么在 Lisp 中你将新项目cons放入列表中，并在最后反转它。这样，您在构建列表时只需遍历该列表一次。

在 Clojure 中，如果要在末尾添加到列表，不使用列表而是使用向量类型更为惯用。在向量上，conj 将向右添加到末尾。

但假设您想要遍历一个列表一次并添加到末尾。

实际上是这样的：

(defn my-append [lst item] (concat lst (list item)))

(my-append '(1 2 3) 4)
;; (1 2 3 4)

但正如我所说，如果你想在末尾重复添加，不要使用列表，而是使用向量和 conj 到末尾。

;; more idiomatic clojure in thisst to add something at its end. This is not very efficient. And it is because of the nature of a linked list. Tha case

(def v [1 2 3])

(conj v 4) ;; [1 2 3 4] ;; unbeatable in efficience, because no traversal!

;; and convert to a list
;; e.g.
(def l (conj v 4))
(seq l)    ;; (1 2 3 4)

Answer 2

为了避免双重遍历，您可以使用经典的递归方法。像这样：

(defn append [lst item]
  (loop [res [] lst lst]
    (if (seq lst)
      (recur (conj res (first lst))
             (rest lst))
      (seq (conj res item)))))

所以，它只是从头开始重建列表。
为了使其在 clojure 中的性能更好，您可以通过瞬态集合对其进行优化：

(defn append' [lst item]
  (loop [res (transient []) lst lst]
    (if (seq lst)
      (recur (conj! res (first lst))
             (rest lst))
      (seq (persistent! (conj! res item))))))

但是，是的，正如另一个答案所建议的那样，您应该为每个特定任务仔细选择正确的数据结构，因此在实践中您会想要使用向量。

从 concat 变体开始，它是免费的（因为它是惰性的），但它有一个已知的陷阱，即应用大量堆叠惰性函数时出现堆栈溢出：

user> (defn append-concat [lst item]
        (concat lst [item]))

user> (reduce append-concat () (range 1000000))
;; Error printing return value (StackOverflowError) at clojure.lang.LazySeq/sval (LazySeq.java:42).