平整和收集切片的效率 [英] Efficiency of flattening and collecting slices

问题描述

如果在Iterator<Item=&[T]> where T: Copy上使用标准的.flatten().collect::<Box<[T]>>()，请执行以下操作:

• 执行一次分配；和
• 使用memcpy将每个项目复制到目标位置

还是效率较低?

解决方案

Box<[T]>没有实现FromIterator<&T>，因此，我假设您的实际内部迭代器是产生拥有的T s的东西.

FromIterator<T>表示Box<[T]> 转发至 Vec<T>，其中使用size_hint() 为lower + 1个项目保留空间，并随着空间的增长而重新分配(必要时移动元素).所以问题是，Flatten<I>返回的size_hint是什么?

针对Flatten<I>的Iterator::size_hint的实现文档保证可以在O(1)中摊销push ).

这不是人为限制；这是Flatten工作方式的基础.预计算展平迭代器大小的唯一方法是用尽外部迭代器并将所有内部size_hint加起来.这是一个坏主意，因为它并不总是起作用(内部迭代器可能不会返回有用的size_hint s)，还因为您还必须找到一种方法来用尽外部迭代器之后保持内部迭代器的状态.没有通用迭代器适配器可以接受的解决方案.

如果您对特定的迭代器有所了解，从而可以知道最终的大小，则可以通过调用Vec::with_capacity并使用 解决方案

Box<[T]> does not implement FromIterator<&T>, so I'll assume your actual inner iterator is something that yields owned Ts.

FromIterator<T> for Box<[T]> forwards to Vec<T>, which uses size_hint() to reserve space for lower + 1 items, and reallocates as it grows beyond that (moving elements as necessary). So the question is, what does Flatten<I> return for size_hint?

The implementation of Iterator::size_hint for Flatten<I> forwards to the internal struct FlattenCompat<I>, which is a little complicated because it supports double-ended iteration, but ultimately returns (0, None) if the outer iterator has not been advanced or exhausted.

So the answer to your question is: it does something less efficient. Namely, (unless you have already called next or next_back on the iterator at least once) it creates an empty Vec<T> and grows it progressively according to whatever growth strategy Vec uses (which is unspecified, but guaranteed by the documentation to result in O(1) amortized push).

This isn't an artificial limitation; it is fundamental to the way Flatten works. The only way you could pre-calculate the size of the flattened iterator is by exhausting the outer iterator and adding up all the inner size_hints. This is a bad idea both because it doesn't always work (the inner iterators may not return useful size_hints) and because you also have to find a way to keep the inner iterators around after exhausting the outer one; there's no solution that would be acceptable for a general purpose iterator adapter.

If you know something about your particular iterator that enables you to know what the final size should be, you can reserve the allocation yourself by calling Vec::with_capacity and use Extend to fill it from the flattened iterator, rather than using collect.

这篇关于平整和收集切片的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！