News for hackers. Stuff that matters.
Re:What's wrong with this code, really? by shabble on Friday September 16, 2011 @08:53AM (#3004225)
The other nice thing about running it in reverse is that the .count method (assuming it's a method and not a property), needs only to be accessed in the initial condition setup.

If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.

c.f. https://secure.wikimedia.org/wikipedia/en/wiki/Schlemiel_the...

Re:What's wrong with this code, really? by icebraining on Friday September 16, 2011 @10:44AM (#3004606)
> If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.

I'd expect any decent linked list implementation to keep an integer with the current size. Java certainly does: http://www.docjar.com/html/api/java/util/LinkedList.java.htm...

Re:What's wrong with this code, really? by masklinn on Friday September 16, 2011 @09:33AM (#3004367)
> If you're accessing the size of, say, a linked list, you end up sneaking an O(n^2) runtime because it has to re-count the size of the list every iteration to check for termination.

You're still going to run in O(n^2) if you remove from the back (as you'd do if you run in reverse).

Linked list are far more efficient if you build in reverse but remove in iteration order (just replace your head pointer with head.next)

Re:What's wrong with this code, really? by jbri on Friday September 16, 2011 @09:15AM (#3004294)
Though you have to be careful with that, because the obvious code for removing from a collection in reverse:

  for(i = list.size; i >= 0; i--)
    list.removeAt(i);
Is itself a schlemiel algorithm on any singly-linked list...
Re:What's wrong with this code, really? by kzrdude on Friday September 16, 2011 @11:12AM (#3004749)
You're removing i+1 elements here :)
Re:What's wrong with this code, really? by Confusion on Saturday September 17, 2011 @03:19AM (#3007476)
That really depends on the implementation of the linked list. I don't think it would actually behave O(n^2) in most implementations.
Re:What's wrong with this code, really? by willfarrell on Friday September 16, 2011 @11:43AM (#3004890)
for(i = list.size; i--;) list.removeAt(i);