6 ms·

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

by shabble 15y ago

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_Painter%27s_algorithm https://secure.wikimedia.org/wikipedia/en/wiki/Schlemiel_the...

jbri 15y ago
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...
- kzrdude 15y ago
  You're removing i+1 elements here :)
- willfarrell 15y ago
  for(i = list.size; i--;) list.removeAt(i);
- Confusion 15y ago
  That really depends on the implementation of the linked list. I don't think it would actually behave O(n^2) in most implementations.
masklinn 15y ago
> 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)
icebraining 15y ago
> 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.html http://www.docjar.com/html/api/java/util/LinkedList.java.htm...

by shabble 15y ago

jbri 15y ago

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

kzrdude 15y ago
You're removing i+1 elements here :)
willfarrell 15y ago
for(i = list.size; i--;) list.removeAt(i);
Confusion 15y ago
That really depends on the implementation of the linked list. I don't think it would actually behave O(n^2) in most implementations.

masklinn 15y ago

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

icebraining 15y ago

> 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.html http://www.docjar.com/html/api/java/util/LinkedList.java.htm...