clojure中的每个集合都被认为是"可排序的",但实际上只有list和cons是seqs:
user> (seq? {:a 1 :b 2})
false
user> (seq? [1 2 3])
false
所有其他seq函数首先将集合转换为序列,然后再对其进行操作
user> (class (rest {:a 1 :b 2}))
clojure.lang.PersistentArrayMap$Seq
我不能做这样的事情:
user> (:b (rest {:a 1 :b 2}))
nil
user> (:b (filter #(-> % val (= 1)) {:a 1 :b 1 :c 2}))
nil
并且必须强制返回到具体的数据类型。在我看来,这是一个糟糕的设计,但很可能我还不明白。
那么,为什么clojure集合不直接实现ISeq接口,并且所有seq函数都不返回与输入对象属于同一类的对象呢?
这已经在Clojure谷歌小组中讨论过了;例如,请参阅今年2月的线程映射语义。我将在添加几个新观点的同时,重新使用我在下面的帖子中提出的一些观点。
在我继续解释为什么我认为"单独seq"设计是正确的之前,我想指出的是,对于那些你真的希望输出与输入相似而不明确的情况,一个自然的解决方案是以contrib库algorg.generic的函数fmap
的形式存在的
概述
我认为,关键的观察结果是,像map
、filter
等序列操作在概念上分为三个独立的关注点:
-
对其输入进行迭代的某种方式;
-
将函数应用于所述输入的每个元素;
-
从而产生输出。
显然2。如果我们能处理1,这是没有问题的。和3。让我们来看看这些。
迭代
对于1.,请考虑对集合进行迭代的最简单、最具性能的方法通常不涉及分配与集合相同抽象类型的中间结果。将函数映射到向量上的分块seq可能比将函数映射在seq上更具性能,从而为每次对next
的调用产生"视图向量"(使用subvec
);然而,后者是我们在Clojure风格向量上为next
所能做的最好的性能(即使在存在RRB树的情况下,当我们需要适当的子向量/向量切片操作来实现有趣的算法时,RRB树也很好,但如果我们用它们来实现next
,遍历会变得非常慢)。
在Clojure中,专门的seq类型维护遍历状态和额外的功能,如(1)用于排序映射和集的节点堆栈(除了更好的性能外,这比使用dissoc
/disj
的遍历具有更好的big-O复杂性!),(2)用于将叶数组封装在向量块中的当前索引+逻辑,(3)用于哈希映射的遍历"延续"。通过这样的对象遍历集合比通过subvec
/dissoc
/disj
的任何尝试都要快
然而,假设我们愿意接受在向量上映射函数时的性能打击。好吧,让我们现在尝试过滤:
(->> some-vector (map f) (filter p?))
这里有一个问题——没有很好的方法从向量中删除元素。(同样,RRB树在理论上可能有帮助,但在实践中,为过滤操作生成"实向量"所涉及的所有RRB切片和级联都会完全破坏性能。)
这里有一个类似的问题。考虑这个管道:
(->> some-sorted-set (filter p?) (map f) (take n))
在这里,我们从懒惰中受益(或者更确切地说,从尽早停止过滤和映射的能力中受益;这里有一点涉及减少,见下文)。显然,take
可以用map
重新排序,但不能用filter
重新排序。
关键是,如果filter
可以隐式转换为seq,那么map
也可以;并且可以对其他序列函数进行类似的自变量。一旦我们为所有或几乎所有对象进行了论证,就可以清楚地看出,seq
返回专门的seq
对象也是有意义的。
顺便说一句,在集合上过滤或映射函数而不产生类似的集合是非常有用的。例如,我们通常只关心将转换管道产生的序列减少到某个值的结果,或者只关心在每个元素调用函数产生副作用的结果。对于这些场景,维护输入类型没有任何好处,性能也会损失很多。
产生输出
如上所述,我们并不总是希望产生与输入相同类型的输出。然而,当我们这样做的时候,通常最好的方法是将一个seq倒在一个空的输出集合中。
事实上,绝对没有办法对地图和集合做得更好。根本原因是,对于基数大于1的集合,无法预测将函数映射到集合上的输出的基数,因为函数可以"粘合在一起"(为任意输入产生相同的输出)。
此外,对于排序的映射和集合,不能保证输入集合的比较器能够处理任意函数的输出。
因此,如果在许多情况下,比如说,map
比单独处理seq
和into
要好得多,并且考虑到seq
和into
是如何自己生成有用的原语的,Clojure会选择公开有用的原语并让用户编写它们。这允许我们map
和into
从一个集合生成一个集合,同时当生成一个集(或另一个集合类型,视情况而定)没有值时,我们可以自由地而不是进入into
阶段。
并非所有都是seq;或者,考虑减速器
映射、筛选等时使用集合类型本身的一些问题不适用于使用还原器时。
reducers和seqs之间的关键区别在于,clojure.core.reducers/map
和friends生成的中间对象只生成"描述符"对象,这些对象维护在reducers实际被缩减的情况下需要执行哪些计算的信息。因此,可以合并计算的各个阶段。
这使我们可以做类似的事情
(require '[clojure.core.reducers :as r])
(->> some-set (r/map f) (r/filter p?) (into #{}))
当然,我们仍然需要明确我们的(into #{})
,但这只是一种说法"减速器管道到此为止;请以集合的形式产生结果"。我们也可以要求不同的集合类型(可能是结果的向量;请注意,在集合上映射f
很可能会产生重复的结果,在某些情况下我们可能希望保留它们)或标量值((reduce + 0)
)。
摘要
要点如下:
迭代集合的最快方法通常不涉及产生类似于输入的中间结果;
CCD_ 32采用最快的迭代方式;
通过映射或过滤来转换集合的最佳方法包括使用
seq
风格的操作,因为我们希望在累积输出时快速迭代;因此CCD_ 34形成了一个大的基元;
map
和filter
在处理seqs的选择中,根据场景的不同,可以避免没有好处的性能惩罚,从懒惰中受益等,但仍然可以使用into
生成收集结果;因此,它们也是伟大的原始人。
其中一些要点可能不适用于静态类型语言,但Clojure当然是动态的。此外,当我们确实想要一个与输入类型匹配的返回时,我们只是被迫明确它,这本身可能被视为一件好事。
序列是一个逻辑列表抽象。它们提供了对(稳定的)有序值序列的访问。它们被实现为集合上的视图(具体接口与逻辑接口匹配的列表除外)。序列(视图)是一个单独的数据结构,它引用集合以提供逻辑抽象。
序列函数(map、filter等)取一个"seqable"的东西(可以产生序列的东西),对它调用seq来产生序列,然后对该序列进行操作,返回一个新的序列。这取决于你是否需要或如何将该序列重新收集回一个具体的集合。虽然向量和列表是有序的,但集合和映射不是有序的,因此这些数据结构上的序列必须计算并保持集合之外的顺序。
mapv、filterv、reduce-kv等专用函数允许您在知道希望操作在末尾而不是序列返回集合时保持"在集合中"。
user=> (seq (array-map :a 1 :b 2))
([:a 1] [:b 2])
user=> (seq (array-map :b 2 :a 1))
([:b 2] [:a 1])
要求映射的rest
是没有意义的,因为它不是一个顺序结构。一套也是如此。
那么向量呢?它们是按顺序排列的,所以我们可以潜在地映射到一个向量上,实际上有这样一个函数:mapv
。
你可能会问:为什么这不是隐含的?如果我将一个向量传递给map
,为什么它不返回一个向量?
首先,这意味着要为向量等有序结构破例,而Clojure并不擅长破例。
但更重要的是,你会失去seqs最有用的特性之一:懒惰。将seq函数(如map
和filter
)链接在一起是一种非常常见的操作,如果没有惰性,这将大大降低性能,并且占用更多内存。
集合类遵循工厂模式,即不是实现ISeq
,而是实现Sequable
,即可以从集合创建ISeq
,但集合本身不是ISeq
。
现在,即使这些集合直接实现了ISeq
,我也不确定这将如何解决具有返回原始对象的通用序列函数的问题,因为这根本没有意义,因为这些通用函数应该在ISeq
上工作,他们不知道是哪个对象给了他们这个ISeq
java中的示例:
interface ISeq {
....
}
class A implements ISeq {
}
class B implements ISeq {
}
static class Helpers {
/*
Filter can only work with ISeq, that's what makes it general purpose.
There is no way it could return A or B objects.
*/
public static ISeq filter(ISeq coll, ...) { }
...
}