Hacker News Reader

Comment by praptak | Hacker News Reader

Deleting from a container while you are iterating over it should always raise red flags.

Depends on what you want to accomplish and what your container and iterators support. If your Iterator offers a delete method, I think it's a very elegant and clear way to filter a container.

  for (Iterator it = container.iterator(); it.hasNext(); )
    if (!predicate(it.next())(
      it.remove();

It's more ugly and error prone if you've got to juggle an index, though.

Even with plain C, you can just iterate backwards:

    for (i = ctr_size(container); i > 0; i--)
        if (!predicate(container, i - 1))
            ctr_remove(container, i - 1);

    for (i = ctr_size(container); i--; )
        if (!predicate(container, i))
            ctr_remove(container, i);

That's arguably better. Nitpick: start at ctr_size(container) - 1. [Feel free to edit your post, and I'll just delete this one.]

Nope. The decrement is occurring in the test, so it occurs after the initialization and before the first iteration.

  filter predicate xs

Haskell, I assume. Two things really make Haskell shine when it comes to problems like this: 1) higher-order list operations -- you're not iterating through indices, so there is no possibility for off-by-one errors, and 2) immutability -- your code takes a new list with the undesirable elements removed; you can't remove elements of a structure at the same time you're iterating through it.

I always love the problems on SPOJ where they give you the number of cases up front, because in Haskell you can almost always throw out that value. Your map function knows when the list is out of elements.

Yeah, I was thinking Haskell, but any functional language will do. Problems like the one in the blog post really make you appreciate them.

The snippet I posted can easily be made into a generic function<T> that takes a collection<T> and a predicate<T>. For example, the Apache Commons library offers such a function for Java, so where available the code comes down to the fairly similar

  CollectionUtils.filter(collection, predicate);

Of course aside from being a bit more verbose, predicate needs to be an object (often a singleton), because you can't pass around functions.

It's not as concise as Haskell, but the addition of FP capabilities to C# make it a lot more pleasant as a practical language than it was in earlier days.

var filteredCollection = collection.Where(x => predicate(x));

As far as I remember you can write that as

  var filteredCollection = collection.Where(predicate);

I agree that C# is a fundamentally usable language.

l = [i for i in l if predicate(i)]

Use the goes-to-zero operator.

  for (i = container.size; i-->0;)
    if(deletep(container, i))
      container.remove(i);

Reminds me of something :)

  while(container.Size > 0)
    container.Remove(0);

No need for variables.

  container.clear();

No need for looping :)

Yeah sure, :) , but I meant for those other cases when there are no Clear() method. :)

The correct idiom is delete list head until list is empty.

The iterator may become invalid if the collection it derived from changes.

Iterator delete methods are crazy to begin with since iteration does not correlate with deletion. But anyway it is not clear where the iterator's cursor will point after you delete the current element. You could end up deleting every second element in the container.

My example wasn't clearing the list, it's a filter. And depending on what language and library you're talking about, it's very clear where the cursor will point to after a delete. There's nothing crazy about it with an even halfway sane collection framework.

Discussion about iterators removing anything aside, I don't think your example disagrees with the parents point. His point was that iterating over a containing while removing items should raise red flags. And it should, always. You should always inspect such loops with more scrutiny because more things are going on, and it's surprisingly easy to get such code correct as multiple things are changing out from under you.

In the systems class I TAed, when students had memory corruption problems, removing items while iterating over a linked list was at the top of my list of things to look for.

Isn't clear() itself a "while (not empty) delete element"?

Maybe, maybe not - depends on the container.

But thats not the point - while (not empty) is not iterating over the loop, so there is no danger of corrupting the iterator.

Very unlikely. There class implementation can almost certainly do it with an O-1 operation, like "self._internal_count = 0".

or self._tabs = new List();

It might be. It also might be a "new List<TabPage>" or even some faster, internal construct. I don't think .NET makes a promise here, though I could be wrong.

A while loop isn't in itself an iterator. There's a difference between

  while(collection.Count > 0) 
  {
   collection.Delete(0);
  }

.. which is a working implementation of clear, though probably superfluous.

and...

  int i = 0;
  while(i < collection.Count) 
  {
   collection.Delete(i);
   i++;
  }

which does try to walk along the list and is broken.

Also, .Net has a specific exception to stop you modifying a collection while an enumerator is walking along it. Google for "Collection was modified; enumeration operation may not execute"

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]);
    }

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.

Correct. I think the logical thing to do would be to delete from the end so that the index is always valid.

for (int i=this.MyControl.TabPages.Count - 1; i > 0; i--) { this.MyControl.TabPages.Remove(this.MyControl.TabPages[i]); }

Imagine the count is 2. The first iteration you delete item 1, the second you delete item 0, and then the loop exits.

EDIT: Actually, as someone else pointed out, it's clearer to use a while loop that deletes the 0th item until the collection is empty.

Actually, you will never delete the final element with that code.

I think what you meant was:

for (int i=this.MyControl.TabPages.Count; i > 0; i--) { this.MyControl.TabPages.Remove(this.MyControl.TabPages[i-1]); }

I prefer:

    for (int i=this.MyControl.TabPages.Count - 1; i >= 0; i--)  {
        this.MyControl.TabPages.Remove(this.MyControl.TabPages[i]); 
    }

Though a simple while loop is much easier to follow, even if its less efficient than removing the elements in reverse.

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

I suppose if you want to be a real optimization junky you'd also use --i instead of i--.

Ten years ago, sure, but nowadays I trust the compiler to do this for me ;-)

That's also what I read of it.

It's TFA's method, except broken (or not fixed, word it as you prefer).

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:

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

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.

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

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

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.

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.

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.

Singly linked lists can still maintain a tail and before-tail pointer, maintaining O(1) tail operations.

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.

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.

True for arrays. Very wrong for singly-linked lists, as in lisp, haskell, erlang, etc.

Reply on news.ycombinator.com