6

我想要一个 clojure 数据结构：

  • 从前面弹出
  • 向后推
  • 让我将索引与值关联（即(assoc q 0 1)会将前面的值设置为 1）

Clojure 中是否有类似的东西（不幸的是 PersistentQueue 不符合 Nr.3），还是我应该在向量之上构建它？

4

4 回答 4

1

标准 Clojure 中没有一种数据结构可以有效地满足这些要求。

Clojure-Dev 邮件列表上有一些关于使用 RRB 树作为向量的讨论，这将是一个很好的数据结构：

不知道这已经发展到什么程度了——但如果你对这种数据结构感兴趣，那么绝对值得一看。

于 2012-10-26T06:16:45.553 回答
1

如果您不需要数据结构的持久性，您可以java.util.LinkedList在 Clojure 程序中使用。

例子：

;;; Creation
user> (import 'java.util.LinkedList)
java.util.LinkedList
user> (def linked-list (LinkedList. [:a :b :c :d :e]))
#'user/linked-list

;;; Pop from the front
user> (.pop ^LinkedList linked-list)
:a
user> linked-list
#<LinkedList [:b, :c, :d, :e]>

;;; Push to the rear, but costly
user> (.addLast ^LinkedList linked-list :x)
nil
user> linked-list
#<LinkedList [:b, :c, :d, :e, :x]>

;;; Assoc (cf. (assoc linked-list 0 :y)
user> (.add ^LinkedList linked-list 0 :y)
nil
user> linked-list
#<LinkedList [:y, :b, :c, :d, :x]>
于 2012-10-28T02:04:28.087 回答
0

您可以使用sorted-map，但您必须自己实现索引部分。

例如，要推送一个值 v，您可以将它与通过递增映射中的最后一个键生成的键相关联。要弹出，您可以解开地图中的第一个键。

于 2012-10-26T06:28:32.790 回答
0

听起来你想要一个像 python 的双端队列一样的双端队列，除了你可能更喜欢 c++ 的索引访问性能特征，std::deque<T>它的文档有点迟钝。

Java 附带了您可以使用的java.util.Deque实现，就像@tnoda 对 java.util.LinkedList 的建议一样。

如果您自己滚动，那么对于非持久集合的实现非常简单，并且至少对我来说似乎相当直观，至少可以针对 clojure 的哈希图和向量底层的“散列数组树”实现，或者如果详细信息最初直接针对向量惹恼你。

于 2012-11-08T01:47:06.477 回答