Especially when you're re-calculating the count on each iteration :) Inefficient and incorrect. Double whammy. While not as efficient as while(--), the fix get's the point across:
for (int i=0,j=this.MyControl.TabPages.Count; i < j; i++) {
this.MyControl.TabPages.Remove(this.MyControl.TabPages[i]);
}
The problem is that .Count decrements every time you .Remove(). Either change [i] to [0] in your code, or initialize i with .Count-1 and decrement in the loop.
For the record, the second way is typically better: It is usually more (sometimes much more) efficient to remove from the end of a list/array than to remove from the beginning.
I'm genuinely curious -- why? The last time I coded my own linked-list, it was doubly-linked, so deleting either the head or the tail was exactly the same.
Its heavily implementation dependent, but for many implementations of lists and arrays shift is slower than pop. Shift tends to require moving the entire array around, while pop does not. It's rarely the case with doubly-linked lists, or with perl arrays (they do something special, keep the starting offset recorded or something)
For you case deleting from either end ought to be fine, but you've made the other implicit tradeoff because merely accessing items in the middle of a linked list will be slow. In the case of something like a JavaScript array, removing from the front is 80% slower than removing from the end:
It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).
Yikes. That's quite a difference in performance ... what I still don't understand though is, why? I've done a little bit of searching and I can't find anything so far on how JS arrays are implemented. Since JS arrays are objects and inherently support things like out-of-order indexes, non-integer indexes and that kind of thing, maybe we can assume it's some kind of hash map? A tree would make sense too, for faster accesses, and if a pop() on the tree meant removing the root node (and rebalancing the tree), then I suppose that would make sense, too.
But, honestly, for the majority of stuff in Javascript, I'd be surprised if some kind of hybrid hash-map / ordered skip list weren't being used instead. Ordered skip lists can be about as fast as a binary tree, without the costs associated with rebalancing, and a lot less complexity. You'd have some tradeoffs in memory usage depending on how you want to tune your skip list, but given the absurd memory requirements for modern software, that doesn't seem to be a consideration amongst programmers anymore.
So ... I accept that removing items from the head of a list in these higher-level languages is (a lot) more expensive. But I still don't get why.
JS arrays are implemented in a variety of ways in different JS engines, but at least V8 and Spidermonkey have a "fast case" where there's an actual C array (single contiguous chunk of memory) and fall back on a slower representation in the rare cases (large holes in the array, non-integer indices, etc).
So in the common case, you are in fact looking at a big memcpy every time you remove an object from the front, unless you do some magic with keeping track of a nonzero offset in your C array. V8 does that magic in some cases but not others, as far as I can tell.
Thanks! That explains a lot. I'm actually really surprised that they're implemented that way (pleasantly surprised) -- I didn't think even "high performance" code was generally done like that anymore.
Most of the time it is simply because a shift operation has to re-address each element in the array (if it is implemented like a ho-hum, classic array) and a pop operation does not have to do this.
I think the assumption was that even arrays indexed by integers are stored as JS Objects, which are basically a hashmap style structure, and so they wouldn't be implemented like a ho-hum, classic array. I'm not sure if that assumption is right, but if it is, there would be no need to re-address each element.
If you don't re-address each element, how do you map the value at index 1 to index 0?
One way is to leave the indexes intact and keep an offset around, so you may map the nth logical index to the nth physical one. (Add 1 on a shift, subtract 1 on an unshift.)
Linked lists aren't used very often in languages that have easy (memory managed, or resizable) access to arrays, unless the specific characteristics of linked lists are desired. Arrays are faster for almost all operations for most collection lengths that come up in human-provided data (i.e. less than 10, almost certainly less than 100 - and in this case, tab pages, very probably only 3 or 4). And on the flipside, if the idiom of the language is to prefer arrays over linked lists, it naturally follows that you tend to want to clear such collections from the end rather than the start.
In terms of performance, another consideration may be important here: invalidation and redrawing of the UI. Controls like tab pages may update the UI for every modification of the tab collection (unless updates have been suspended). Removing from the end will look slightly more pleasant than removal from the start in this case.
So after you delete the last element, how do you get the new before-tail pointer?
If you recalculate it right there, you've actually done nothing in terms of the algorithmic complexity. If you defer it either until it's needed or until you next enumerate the list, then you get to O(1) in the case of individual removes at the end (as long as they're interspersed with other operations), but you're still O(n^2) for removing the entire list starting at the tail.
Sigh. You're right. It's amazing how many linked lists I've implemented, and how often I still can screw it up. A singly-linked list with a head and tail pointer allows O(1) tail insertion, but still has O(n) tail deletion.
For a list there's not likely to be a difference. For an array you have to shift all the elements after the one you're removing down by one place; if you're removing from the start of the list you have to adjust every item in the list, but if you're removing from end you don't have to adjust any items.
Won't this.MyControl.TabPages[i] be invalid once i becomes greater than what this.MyControl.TabPages.Count now is? Since the "always remove element 0" code from the article works, I expect your code won't work because when you remove an element form the list, all subsequent elements now have an index one less than before, so after j/2 elements, you'll overrun the list.
Although your point on efficiency stands (at least with data structures that have to reshuffle contents on deletion), the type of loop that you use has nothing to do with the order that you delete the elements. You could easily do something like:
while (MyControl.TabPages.Count > 0) {
MyControl.TabPages.RemoveAt(MyControl.TabPages.Count-1);
}
For loop are nothing more than while loops with:
(1) an assignment (int i = MyControl.TabPages.Count in this case)
(2) an extra command (i-- in this case) added to the end
Sure. Though if we're talking about efficiency, I would imagine that counting backwards would be slightly faster than getting the current count each time. Though in reality this depends on way too many factors - I imagine TabPages would be stored in cache and getting the count is just as fast as counting backwards. Micro-optimization and all that.
Regarding for vs while, I find the choice is important only in the intent they emphasize: while puts emphasis on the condition, whereas for puts the emphasis on the iteration. I think in this case the condition (that the list is not empty) is deserves more emphasis than the iteration through the elements of said list - hence why I find the while version to be more readable. YMMV and all that :)
Exactly. For example in JavaScript doing a something.length would result in re-counting the number of elements, while doing the loop in this style would efficiently store the count in a variable that is fast to access and manipulate. I suppose if you want to be a real optimization junky you'd also use --i instead of i--.
