Qual è il modo più veloce per scorrere attraverso un Iterator al contrario

Question

Diciamo che mi piacerebbe ripetere un iteratore generico al contrario, senza conoscere l'interno dell'iteratore e in sostanza non barare tramite la magia non tipizzata e supponendo che questo potrebbe essere qualsiasi tipo di iterabile, che serve un iteratore; possiamo ottimizzare il contrario di un iteratore in fase di esecuzione o anche tramite macro?

Attaccanti

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

indietro

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

presumo che ci deve essere un modo più semplice, o almeno modo veloce di fare questo. Non possiamo conoscere una dimensione perché la classe Iterator non ne contiene una, quindi non possiamo invertire la spinta sulla matrice temporanea. Ma possiamo rimuovere il retro perché conosciamo la dimensione della matrice temporanea.

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). Alcuni iteratori possono essere interrotti nel mezzo dell'iterazione (Lambda.has() e Lambda.indexOf() per esempio restituiscono non appena c'è una corrispondenza, quindi normalmente non vuoi pensare a cosa viene ripetuto come una raccolta ma più come una serie interrompibile o processo iterato passo dopo passo).

Mentre questo non significa che non si dovrebbero definire iteratori a due vie se ne avete bisogno (non l'ho mai fatto in Haxe ma non sembra impossibile), nell'assoluto avendo due vie gli iteratori non sono così naturali, e far sì che gli iteratori siano così sarebbe complicato codificarne uno.

Una soluzione intermedia e più flessibile è semplicemente avere ReverseXxIter dove è necessario, ad esempio ReverseIntIter o Array.reverseIter() (con l'utilizzo di una classe ArrayExt personalizzata). Quindi è lasciato ad ogni programmatore di scrivere le proprie risposte, penso che sia un buon equilibrio; mentre ci vuole più tempo e frustrazione all'inizio (tutti probabilmente hanno lo stesso tipo di domande), si finisce per conoscere meglio la lingua e alla fine ci sono solo benefici per te.