logo标签列表

Clojure中在向向量前添加元素的惯用方式是什么？

vectorclojureappendprepend
61

在列表前面添加元素非常简单：

user=> (conj '(:bar :baz) :foo)
(:foo :bar :baz)

向向量追加元素很容易：

user=> (conj [:bar :baz] :foo) 
[:bar :baz :foo]

如何在保持向量不变的情况下，用惯用方式在向量前面添加元素并返回一个新的向量？以下方法将返回一个序列而非向量：

user=> (cons :foo [:bar :baz])     
(:foo :bar :baz)

这很丑陋（在我看来）：

user=> (apply vector (cons :foo [:bar :baz])) 
[:foo :bar :baz]

注意：我基本上只想要一个可以追加和前置的数据结构。向大型列表追加应该会导致很大的性能惩罚，所以我考虑使用向量。

我不得不指出最后一个“丑陋”的例子可以简化成稍微不那么丑陋的形式：(apply vector :foo [:bar :baz])（只需去掉 cons）。但我同意，除了 (vector ...) 解决方案之外，基本上只有 concat。如果有一种漂亮的语法来展开参数而不是使用 apply（就像 ~@ 但不仅限于宏），那该多好啊... 叹气 - chbrown
5个回答
80

向量并不适合用于前置操作。您只能进行O(n)的前置操作：

user=> (into [:foo] [:bar :baz])
[:foo :bar :baz]

你需要的可能是 finger tree。

2
rrb-vectors 可以在 O(log n) 的时间内进行连接（因此可以进行前置操作）。请参见 https://github.com/clojure/core.rrb-vector。 - optevo
2
我也推荐使用rrb-vectors。我在这篇文章中发现了它，然后在Clojure邮件列表上挖掘后，我找到了另外两个库，它们应该替换data.finger-tree并添加ClojureScript支持。rrb-vector是由Michał Marczyk维护的一个贡献项目，他是Clojure社区中备受尊敬的贡献者。并不是其他库的作者不好，只是作为一个Clojure新手，我不认识他们。 - Rafał Cieślak
Clojure的向量(Vector)在时间复杂度上进行前置(prepend)操作并不会有任何实质性的问题，我已经在Go中实现了这个功能，代码在这里：https://github.com/d11wtq/persistent/tree/feature/prepend。解决方案是：1）记住一个“起始偏移量”（默认=0），并在所有树操作中使用它。2）当进行前置操作时，如果“起始偏移量”= 0，则分配一个新的根节点，将旧的根节点放置在其中间，并将“起始偏移量”更新为此位置。3）在所有其他情况下，前置操作只需要减少“起始偏移量”，然后在索引0处执行常规的关联操作。 - d11wtq
该设计中关于内存浪费的问题被消除了，因为只有在节点需要存储数据时才会进行惰性初始化。通过增加“起始偏移量”并在第零个元素上执行空关联来实现shift(从左侧弹出)操作。必须注意删除索引小于“起始偏移量”的节点路径。 - d11wtq
1
我还没有探索过它，但我怀疑使用这种数据结构操作可以在O(log32(n))的时间内完成split和concat，实际上相当于O(1)。 - d11wtq
18

我知道这个问题很老了，但没有人提到过差异列表。既然你只是想要可以前后追加的东西，那么差异列表听起来可能会有所帮助。虽然它们在Clojure中似乎并不流行，但它们非常容易实现，比Finger Trees复杂得多，所以我刚刚制作了一个小型的差异列表库（甚至已经测试了）。 这些列表在O（1）时间内（前缀或后缀）连接起来。将差异列表转换回列表应该花费O（n），如果您正在进行大量连接，则这是一个不错的权衡。如果您不需要进行大量连接，那么就使用列表吧？

以下是此小型库中的函数：

dl：差异列表实际上是一个函数，它将自己的内容与参数连接起来并返回结果列表。每次生成差异列表时，都会创建一个像数据结构一样的小函数。

dlempty：由于差异列表只是将其内容连接到参数中，因此空差异列表与标识函数相同。

undl：由于差异列表的功能，您可以通过使用nil调用它来将差异列表转换为正常列表，因此这个函数并不是真正需要的；它只是为了方便。

dlcons：将一个项目添加到列表的前面 - 不是完全必要的，但是连接是足够常见的操作，并且它只需要一行代码（就像这里的所有函数一样）。

dlappend：连接两个差异列表。我认为它的定义是最有趣的-来看看吧！：）

现在，这就是那个小型库--5个一行的函数，为您提供O（1）的追加/前缀数据结构。还不错吧？啊，λ演算的美妙之处...

(defn dl
  "Return a difference list for a list"
  [l]
  (fn [x] (concat l x)))

; Return an empty difference list
(def dlempty identity)

(defn undl
  "Return a list for a difference list (just call the difference list with nil)"
  [aDl]
  (aDl nil))

(defn dlcons
  "Cons an item onto a difference list"
  [item aDl]
  (fn [x] (cons item (aDl x))))

(defn dlappend
  "Append two difference lists"
  [dl1 dl2]
  (fn [x] (dl1 (dl2 x))))

你可以通过以下方式查看它的作用：

(undl (dlappend (dl '(1 2 3)) (dl '(4 5 6))))

它返回：

(1 2 3 4 5 6)

这也会返回相同的结果：

((dl '(1 2 3)) '(4 5 6))

玩转差异列表吧！

更新

以下是一些可能更难理解但我认为更好的定义：

(defn dl [& elements] (fn [x] (concat elements x)))
(defn dl-un [l] (l nil))
(defn dl-concat [& lists] (fn [x] ((apply comp lists) x)))

这使您能够像这样说：

(dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))

返回的是哪一个

(1 2 3 4)
5
如果您不害怕准引用，这个解决方案实际上相当优雅（对于某些“优雅”的定义）：
> `[~:foo ~@[:bar :baz]]

[:foo :bar :baz]

我实际上在真实的代码中偶尔使用这个，因为声明式语法使其相当易读（在我看来）。

确实! 我非常羡慕ES6的扩展语法，但我没有意识到我们可以用准引号(quasi-quoting)来实现其中的一些功能：(let [x [1 2]] `[0 ~@x]) => [0 1 2] - onetom
3
作为用户optevo在指数树答案下评论中提到的，您可以使用clojure/core.rrb-vector库，该库实现了RRB-trees：

RRB-Trees基于Clojure的PersistentVectors构建，添加了对数时间的连接和切片。除了缺少vector-of函数外，ClojureScript支持相同的API。

我决定将此发布为单独的答案，因为我认为这个库值得这样做。它支持ClojureScript，并由Michał Marczyk维护，在Clojure社区中以他实现各种数据结构的工作而闻名。
1
我建议使用Tupelo Library内置的便利功能。例如：
(append [1 2] 3  )   ;=> [1 2 3  ]
(append [1 2] 3 4)   ;=> [1 2 3 4]

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

相比之下，使用原始的Clojure很容易犯错：

; Add to the end
(concat [1 2] 3)    ;=> IllegalArgumentException
(cons   [1 2] 3)    ;=> IllegalArgumentException
(conj   [1 2] 3)    ;=> [1 2 3]
(conj   [1 2] 3 4)  ;=> [1 2 3 4]

; Add to the beginning
(conj     1 [2 3] ) ;=> ClassCastException
(concat   1 [2 3] ) ;=> IllegalArgumentException
(cons     1 [2 3] ) ;=> (1 2 3)
(cons   1 2 [3 4] ) ;=> ArityException
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接