forward-iteration vs reverse-iteration

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

John A Grandy - 25 May 2008 01:30 GMT

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 ?

Reply to this Message

Peter Duniho - 25 May 2008 01:43 GMT

> [...]
> 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

Reply to this Message

Arne Vajhøj - 25 May 2008 03:15 GMT

> Is there a performance difference between forward iteration and reverse
> iteration through a List<string> ?
[quoted text clipped - 13 lines]
> 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

Reply to this Message

Doug Forster - 25 May 2008 21:32 GMT

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

Reply to this Message

Ben Voigt [C++ MVP] - 28 May 2008 23:13 GMT

> 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

Reply to this Message

forward-iteration vs reverse-iteration

Free Magazines