7

假设我想反向迭代一个通用迭代器，而不知道迭代器的内部结构，并且基本上不通过无类型魔法作弊，并假设这可以是任何类型的迭代器，它服务于迭代器；我们可以在运行时甚至通过宏优化迭代器的逆向吗？

前锋

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 类不携带大小，因此我们无法反转对 temp 数组的推送。但是我们可以删除相反的内容，因为我们确实知道临时数组的大小。

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]);    
}

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

4

3 回答 3

5

让我感到困扰的是，您必须复制该列表，但是……这很讨厌。我的意思是，数据结构已经是一个数组，如果那是它的正确数据格式的话。比 Array（“[]”）复制它更好的东西（更少的内存碎片和重新分配）可能是链表或哈希。

但是如果我们使用数组，那么我们应该使用数组理解（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]);
}
于 2014-03-06T01:17:33.093 回答
3

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

现在，关于一个技术答案：

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

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

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

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

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

例如 3：略有不同，但考虑在非常大的单链表（例如 class List）上运行迭代器的性能问题。一些迭代器可以在迭代过程中被中断（例如 Lambda.has() 和 Lambda.indexOf() 一旦有匹配就返回，所以你通常不想把迭代的东西想成一个集合但是更像是一个可中断的系列或逐步迭代的过程）。

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

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

于 2014-09-06T17:48:47.817 回答
0

补充Dewi Morganfor(let i = a.length; --i >= 0;) i;的帖子，如果您想简化while() 方法，可以使用。如果您真的需要索引值，我认为for(let i=a.length, k=keys(a); --i in k;) a[k[i]]; 是保持性能的最佳选择。还有一个for(let i of keys(a).reverse()) a[i];写得更干净，但它的迭代率增加了 1n 使用.reduce()

于 2021-12-31T14:51:35.340 回答