使用迭代器加速对多个集合的mapv处理

Question

mapv对于多个集合当前的处理方式是：


(into [] (map f c1 c2 c3))


我提议修改为：


(let [it1 (clojure.lang.RT/iter c1)
      it2 (clojure.lang.RT/iter c2)]
     (loop [out (transient [])]
       (if (and (.hasNext it1) (.hasNext it2))
        (recur (conj! out (f (.next it1) (.next it2))))
        (persistent! out))))


这可以提高5倍的速度。

对于可变参数，我们可以检查colls是否是可计数的

- 如果是：使用^[3](#)MultiIterator
- 如果不是：将其转发到^[4](#)map，如当前实现那样。

对此有何看法？或者这会破坏某些东西吗？

Answer 1

_由 alexmiller 评论：

迭代器应该默认视为危险和不安全 - 它们是可变的、有状态的、（可能）非线程安全的对象。因此，它们的使用应仔细审查，特别是你不希望它们 a) 从局部上下文中泄露出去（因此它们应该被尽快遍历和释放）或 b) 被用于触发不纯函数执行的某种方式，从而使它们稍后重新执行。序列缓存它们的实现（并且是线程安全的），这使得它们更快，但在避免这种问题方面更加安全。

在这种情况下，你正在生成一个具体的集合（而不是懒序列），因此第一个问题已得到解决。但是，第二个问题稍难理解。我认为这可能没问题，但我还需要考虑这个问题。

请注意，into使用了transduce，它使用了CollReduce，它将在可迭代的colls上执行iterReduce，因此您只需通过使用transducer形式即可达到相同的效果


(into [] (map f) c1)


除了这个表单只接收单个集合外，对于转换器存在多集合支持（请参阅TransformerIterator/createMulti），但在当前API中并不明显。然而，直接利用它似乎比上面提到的建议要好得多。


(defn mapv2 [f & cs]
  (let [iters (map #(.iterator %) cs)
        t (clojure.lang.TransformerIterator/createMulti (map f) iters)]
    (loop [out (transient [])]
      (if (.hasNext t)
        (recur (conj! out (.next t)))
        (persistent! out)))))


请注意，这假设所有的cs都是可迭代的，这并不一定成立。例如：(mapv identity "abc")。所以这仍然需要在回退和性能测试上做一些工作。

Answer 2

评论者：aralo

Alex：我实际上确实使用了这个实现，但发现它的速度比手动跟踪迭代器慢得多。我的猜测是，这可能是由于在{{TransformIterator}}的{{step}}函数中存在{{xf.applyTo}}。我们已经在{{createMulti}}中知道{{source.size()}}。因此，这个实现可能可以通过直接调用正确的arity来变得更聪明。
尽管如此，我没有基准测试任何内容。所以现在只是一个猜测。

Answer 3

评论者：alexmiller

这似乎是一个合理的猜测，并且是可以在TransformIterator中优化的。

Answer 4

评论者：aralo

我实际上考虑了这个问题的更多方面。我同意在这里应该充分利用转换器，并为其提供更好的多集合支持。

因此，我建议改变计划如下：

1. 让{{into}}和{{transduce}}能够处理多个集合
2. 放弃{{MultiIterator}}。我们可以通过在{{TransformIterator}}中直接执行来获得更好的性能，从而避免在"在MultiIterator中构建序列"之后"在apply中展开刚刚创建的序列"的步骤。

不过，这会使TransformIterator变得更为复杂。

之后，我们可以给许多转换器提供在多个序列上工作（保留、过滤、按索引映射、获取、丢弃等）的选项，并有效地使用它们与{{into}}和{{transduce}}。

如果您同意，我可以更改标题以反映新的范围。

Answer 5

评论者：alexmiller

您将从“增强现有函数的性能”转移到进行API设计，这需要考虑很多更大的因素。我认为我们不太可能扩展到多集合领域，也不认为有多许多适于作为原生动态集合的转换器。因此，我认为您不应该扩展这个问题的范围，否则我将拒绝它。

Answer 6

参考： https://clojure.atlassian.net/browse/CLJ-2280（由aralo报告）