반전에서 반복자를 반복하는 가장 빠른 방법은 무엇입니까

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

Is there any more optimisations that could be used to remove the possibility of the array?

Answer 1

It bugs me that you have to duplicate the list, though... that's nasty. I mean, the data structure would ALREADY be an array, if that was the right data format for it. A better thing (less memory fragmentation and reallocation) than an Array (the "[]") to copy it into might be a linked List or a Hash.

But if we're using arrays, then Array Comprehensions (http://haxe.org/manual/comprehension) are what we should be using, at least in Haxe 3 or better:

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

Ideally, at least for large iterators that are accessed multiple times, s should be cached.

To read the data back out, you could instead do something a little less wordy, but quite nasty, like:

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

But that's not very readable and if you're after speed, then creating a whole new iterator just to loop over an array is clunky anyhow. Instead I'd prefer the slightly longer, but cleaner, probably-faster, and probably-less-memory:

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

Answer 2

First of all I agree with Dewi Morgan duplicating the output generated by an iterator to reverse it, somewhat defeats its purpose (or at least some of its benefits). Sometimes it's okay though.

Now, about a technical answer:

By definition a basic iterator in Haxe can only compute the next iteration.

On the why iterators are one-sided by default, here's what we can notice:

1. if all if iterators could run backwards and forwards, the Iterator classes would take more time to write.
2. not all iterators run on collections or series of numbers.

E.g. 1: an iterator running on the standard input.

E.g. 2: an iterator running on a parabolic or more complicated trajectory for a ball.

E.g. 3: slightly different but think about the performance problems running an iterator on a very large single-linked list (eg the class List). 일부 반복자는 반복이 진행되는 동안 (예 : Lambda.has() 및 Lambda.indexOf()) 중단 될 수 있습니다. 예를 들어 일치가 발생하는 즉시 반환 할 수 있으므로 일반적으로 반복으로 반복되는 것을 생각하지 않으려 고하지만 인터럽트 가능한 시리즈 또는 프로세스를 단계별로 반복). 이 동안

당신이 그들을 필요로하는 경우는 절대 가진 두 가지 방법으로, (나는 Haxe에서 해본 적이 없다하지만 불가능하지 않는 것) 두 가지 방법 반복자를 정의해서는 안 의미하지 않는다 반복자는 자연스럽지 않고 반복자를 그렇게 강요하면 코딩을 복잡하게 만들 것입니다.

중간보다 유연한 솔루션은 단순히 (사용자 정의 ArrayExt 클래스를 사용하여) 예를 ReverseIntIter에 대한 당신이 필요로하는 ReverseXxIter, 또는 Array.reverseIter()하는 것입니다. 따라서 모든 프로그래머가 스스로 답변을 작성해야하기 때문에 좋은 균형이라고 생각합니다. 처음에는 더 많은 시간과 좌절감을 갖지만 (모두 비슷한 종류의 질문을했을지 모릅니다.) 언어가 더 잘 이해되고 궁극적으로는 유익합니다.