forward-iteration vs reverse-iteration

[John A Grandy]

Is there a performance difference between forward iteration and reverse
iteration through a List<string?

for ( i = 0; i < myList.Count; i++ )
{
// do work, such as forward iterate through a subset of myList ...
}

vs

for ( j = myList.Count - 1 ; j >= 0; j-- )
{
// do work, such as reverse iterate through a subset of myList ...
}
In other words, is there a performance advantage to pre-sorting a list so
that forward iteration may be used in implementing an algorithm ?

[Peter Duniho]

On Sat, 24 May 2008 17:30:00 -0700, John A Grandy
<johnagrandy@ g-mail-dot-comwrote:

[...]
In other words, is there a performance advantage to pre-sorting a list
so that forward iteration may be used in implementing an algorithm ?

Highly unlikely.

There's a theoretical issue with respect to caching and paging, but as in
previous answers: until you have demonstrated through particular
performance measurements that there's an _actual_ performance problem, it
doesn't make sense to rework your algorithms based on some presumed
performance difference.

http://www.google.com/search?q=premature+optimization

Pete

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

John A Grandy wrote:

Is there a performance difference between forward iteration and reverse
iteration through a List<string?

for ( i = 0; i < myList.Count; i++ )
{
// do work, such as forward iterate through a subset of myList ...
}

vs

for ( j = myList.Count - 1 ; j >= 0; j-- )
{
// do work, such as reverse iterate through a subset of myList ...
}
In other words, is there a performance advantage to pre-sorting a list
so that forward iteration may be used in implementing an algorithm ?

Stuff like that was very relevant when coding in C about
20-30 years ago.

Today is a completely waste of time.

Most likely your gains from that kind of optimization will
be so small that you can not even measure them in your app.

Even if there were some gains then spending 10 USD extra
on a few hundrded MHz extra would be much more cost efficient
than you spending time on it.

Oh - and even though one way is faster on your CPU with your
version of .NET, then there are absolutely no guarantee that
it will be the case on other.

If it is a hobby like old World War I biplanes, then start
measuring the times yourself.

If it is actual work, then focus on writing readable code
with a healthy architecture and create some value that way.

Arne

[Doug Forster]

Just to actually answer your question: Yes there could be(however small). If
you iterate backwards then the target end value is calculated only once at
the start, otherwise it will be evaluated each time. Neither can I see any
readability issue either way. Reverse iteration is a common technique if you
need to delete items as you go.

Cheers
Doug Forster

[Ben Voigt [C++ MVP]]

Doug Forster wrote:

Just to actually answer your question: Yes there could be(however
small). If you iterate backwards then the target end value is
calculated only once at the start, otherwise it will be evaluated
each time. Neither can I see any readability issue either way.
Reverse iteration is a common technique if you need to delete items
as you go.

But "copy-with-exclusions" is faster than reverse iterating delete if the
number of items removed averages at least two (for uniformly distributed
items), and then the direction of traversal once again doesn't matter.

>
Cheers
Doug Forster