使用迭代器加速处理多个集合中的 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 是否是 {{counted?}}

- 如果是：使用 {{MultiIterator}}
- 如果不是：像当前实现那样转发给 {{map}}

对此有何看法？或者这可能会破坏什么吗？

Answer 1

_评论者：alexmiller_

迭代器应该默认被当作危险和不安全的对象 - 它们是可变的、有状态的、（可能是）非线程安全的对象。因此，它们的的使用应谨慎审查，特别是你不希望它们 a) 泄出到局部作用域之外（因此应主动遍历和释放）或 b)以触发纯函数执行的方式使用，这样它们会在以后重新执行。

在这种情况下，你正主动创建一个具体的集合（不是惰性序列），所以第一个问题已解决。但是，第二个问题有点难理解。我认为这可能没问题，但我需要更多时间考虑。

注意，into 使用 transduce，它使用 CollReduce，这将执行 Iterable colls 上的 iterReduce，所以你可能可以通过简单使用转换器形式获得相同的效果


(into [] (map f) c1)


除了这个表单仅接受单个coll之外，还存在支持多coll的transducer（见TransformerIterator/createMulti），但目前在apis中没有很好地体现。但似乎直接利用它比上面的建议要好得多。


（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都是Iterable，这是不合理的假设。例如：(mapv identity "abc")。因此，这仍然需要一些关于回退和性能测试的工作。

Answer 2

评论者：aralo

亚历克斯：我实际上就是用了这个实现，但发现它的速度比手动跟踪迭代器慢得多。我猜这是因为TransformIterator的 {{step}} 函数中的 {{xf.applyTo}}。在{{createMulti}} 中创建它时，我们已经知道{{source.size()}}。所以这个实现可能通过直接调用正确的arity可以变得更加智能。
但是，我没有进行基准测试。所以现在只是一个猜测。

Answer 3

评论者：alexmiller

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

Answer 4

评论者：aralo

我实际上对此进行了更多的思考。我同意这里的正确步骤是可以利用transducer，以及提供更好的多集合支持。

所以，我建议改变战略为

1. 让{{into}}和{{transduce}}与多个集合一起工作
2. 丢弃{{MultiIterator}}。我们可以在TransformIterator内进行这种操作来获得更好的性能，然后避免在apply中创建新序列和扩展此新创建的序列这两个不必要的步骤。

尽管这样做会让TransformIterator更加复杂。

在此之后，我们可以让许多transducer有在多个序列上工作的选项（包括keep、filter、map-indexed、take、drop等等），并以高效的方式使用它们与{{into}}和{{transduce}}。

如果你同意，我可以将标题改为反映新范围。

Answer 5

评论者：alexmiller

您正在从“增强现有函数的性能”转向做API设计，这需要考虑很多更大的问题。我认为我们不太可能扩展为多集合领域，我也不认为有很多可以作为原生多集合的转换器。因此，我认为您不应扩大此票目的范围，否则我会拒绝它。

Answer 6

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