迭代迭代迭代器的最快方法是什么？

Question

假设我想反过来迭代泛型迭代器,而不知道迭代器的内部结构,并且基本上不通过无类型魔法作弊,并假设这可以是任何类型的迭代,它为迭代器提供服务; 我们可以在运行时甚至通过宏优化迭代器的反转吗？

前锋

var a = [1, 2, 3, 4].iterator();
// Actual iteration bellow
for(i in a) {
   trace(i);
}

向后

var a = [1, 2, 3, 4].iterator();
// Actual reverse iteration bellow
var s = [];
for(i in a) {
    s.push(i);    
}
s.reverse();
for(i in s) {
    trace(i);    
}

我认为必须有一种更简单的方法,或者至少是快速的方法.我们无法知道一个大小,因为Iterator类没有携带一个,所以我们不能将推送反转到临时数组.但我们可以删除反向,因为我们知道临时数组的大小.

var a = [1,2,3,4].iterator();
// Actual reverse iteration bellow
var s = [];
for(i in a) {
    s.push(i);    
}
var total = s.length;
var totalMinusOne = total - 1;
for(i in 0...total) {
    trace(s[totalMinusOne - i]);    
}

是否有更多优化可用于消除阵列的可能性？

Answer 1

它让我感到困惑,你必须复制列表,虽然......这是令人讨厌的.我的意思是,如果数据结构是正确的数据格式,那么数据结构肯定是一个数组.将数据复制到数组("[]")的更好的事情(更少的内存碎片和重新分配)可能是链接列表或哈希.

但是如果我们使用数组,那么Array Comprehensions(http://haxe.org/manual/comprehension)就是我们应该使用的,至少在Haxe 3或更好的情况下:

var s = array(for (i in a) i);

理想情况下,至少对于多次访问的大型迭代器,应该缓存s.

要读回数据,你可以做一些不那么罗嗦的事情,但是非常讨厌,比如:

for (i in 1-s.length ... 1) {
    trace(s[-i]);
}

但是这不是很可读,如果你追求速度,那么创建一个全新的迭代器只是为了循环一个数组,无论如何都很笨拙.相反,我更喜欢稍长但更清洁,可能更快,可能更少的内存:

var i = s.length;
while (--i >= 0) {
    trace(s[i]);
}

Answer 2

首先，我同意 Dewi Morgan 复制迭代器生成的输出来反转它，这在某种程度上违背了它的目的（或者至少是它的一些好处）。有时也没关系。

现在，关于技术答案：

根据定义，Haxe 中的基本迭代器只能计算下一个迭代。

关于为什么迭代器默认是单向的，我们可以注意到以下几点：

1. 如果所有迭代器都可以前后运行，那么迭代器类将需要更多时间来编写。
2. 并非所有迭代器都在集合或数字序列上运行。

例如 1：在标准输入上运行的迭代器。

例如 2：在抛物线或更复杂的球轨迹上运行的迭代器。

例如 3：略有不同，但请考虑在非常大的单链表（例如 class List）上运行迭代器的性能问题。一些迭代器可以在迭代过程中被中断（例如 Lambda.has() 和 Lambda.indexOf() 一旦有匹配就返回，因此您通常不想将迭代的内容视为集合，但是更多地作为一个可中断的系列或逐步迭代的过程）。

虽然这并不意味着如果需要的话就不应该定义双向迭代器（我从未在 Haxe 中这样做过，但这似乎并非不可能），但绝对拥有双向迭代器并不是那么自然，并且强制迭代器像这样会使编码变得复杂。

一个中间且更灵活的解决方案是简单地ReverseXxIter在您需要的地方使用，例如ReverseIntIter， 或Array.reverseIter()（使用自定义 ArrayExt 类）。所以留给每个程序员写自己的答案，我认为这是一个很好的平衡；虽然一开始需要更多的时间和挫折（每个人可能都有同样的问题），但你最终会更好地了解这门语言，最终会给你带来好处。