使用迭代器加速对多个集合的 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，它会对可迭代集合 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}}。在创建时，我们已经知道 {{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](https://clojure.atlassian.net/browse/CLJ-2280)（由aralo报告）