使用迭代器加速多个集合上的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_

迭代器应该默认被视为危险和不安全的对象 - 它们是可变的、有状态的，（可能）非线程安全的对象。因此，它们的使用应该仔细检查，尤其是你不想它们推出局部上下文（因此它们应该被迫切遍历和释放）或以触发不纯函数执行的方式使用，这样它们就会在以后重新执行。序列缓存它们的实现（并且线程安全），这使得它们速度较慢，但可以避免这个问题。

在这种情况下，你正在迫切地生成一个具体的集合（而不是懒惰的序列），所以第一个问题已经解决。但是，第二个要困难一些。我认为这可能是可以的，但我需要更多思考。

请注意，into使用transduce，它使用CollReduce，将在可迭代的colls上执行iterReduce，所以你可能可以通过简单地使用转换器形式得到相同的效果


(into [] (map f) c1)


但是，这个形式只接受单个coll。转换器存在支持多coll（请参阅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都是可迭代的，这并不总是一个有效的假设。例如：(mapv identity "abc")。因此，还需要在回退和性能测试方面进行一些工作。

Answer 2

由 aralo 评论

Alex: 我实际上确实使用了这个精确的实现，但发现它比手动跟踪迭代器慢得多。我的猜测是因为 {{xf.applyTo}} 在 {{TransformIterator}} 的 {{step}} 函数中。在 {{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报告)