News for hackers. Stuff that matters.
Re:What's wrong with this code, really? by brlewis on Friday September 16, 2011 @09:24AM (#3004327)
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.
Re:What's wrong with this code, really? by simonsarris on Friday September 16, 2011 @09:29AM (#3004340)
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.
Re:What's wrong with this code, really? by aphyr on Friday September 16, 2011 @11:34AM (#3004848)
True for arrays. Very wrong for singly-linked lists, as in lisp, haskell, erlang, etc.
Re:What's wrong with this code, really? by thaumaturgy on Friday September 16, 2011 @10:12AM (#3004488)
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.
Re:What's wrong with this code, really? by simonsarris on Friday September 16, 2011 @10:28AM (#3004533)
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:

http://jsperf.com/popvsshift

Same deal with Python lists. From the Python spec:

http://docs.python.org/tutorial/datastructures.html#using-li...

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

Re:What's wrong with this code, really? by thaumaturgy on Friday September 16, 2011 @10:53AM (#3004638)
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.

Re:What's wrong with this code, really? by bzbarsky on Friday September 16, 2011 @06:45PM (#3006617)
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.

Re:What's wrong with this code, really? by thaumaturgy on Friday September 16, 2011 @07:12PM (#3006684)
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.
Re:What's wrong with this code, really? by simonsarris on Friday September 16, 2011 @11:10AM (#3004734)
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.
Re:What's wrong with this code, really? by sanderjd on Friday September 16, 2011 @01:23PM (#3005362)
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.
Re:What's wrong with this code, really? by seabee on Friday September 16, 2011 @02:00PM (#3005531)
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.)

But if you wanted this behaviour, there are more efficient ways: http://en.wikipedia.org/wiki/Circular_buffer

Re:What's wrong with this code, really? by barrkel on Friday September 16, 2011 @10:55AM (#3004654)
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.

Re:What's wrong with this code, really? by icebraining on Friday September 16, 2011 @10:34AM (#3004564)
And for singly linked lists, deleting the last would be O(n), while the first would be O(1) (just change the head to point to the next node).

Parent has a point for arrays/arraylists, though, you need to copy everything after the element.

Re:What's wrong with this code, really? by scott_s on Friday September 16, 2011 @05:33PM (#3006408)
Singly linked lists can still maintain a tail and before-tail pointer, maintaining O(1) tail operations.
Re:What's wrong with this code, really? by jbri on Friday September 16, 2011 @06:12PM (#3006534)
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.

Re:What's wrong with this code, really? by scott_s on Friday September 16, 2011 @08:12PM (#3006807)
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.
Re:What's wrong with this code, really? by vilya on Friday September 16, 2011 @10:30AM (#3004541)
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.