I've received lots of criticism on my latest article on enumerators. For the convenience of my readers, here are some excerpts.
Removal loops should be iterated backwards to prevent index shuffling.
... while I can certainly see the usefulness in your Slice- and Walk-enumerators ... I don't think they're the best solution to the two examples you quoted.
Simplicity does not justify an example that fails to work correctly. A bad example is still a bad example, no matter how simple.
I'd also like to echo the other comments w.r.t your initial example. Reversing the direction of the iteration is the simplest wasy to simplify the exemplar task, not invoking enumerators and the such like.
They can be summarized in one sentence: "Your examples suck." The main rationale for that reasoning seems to be the accepted way to delete stuff from a TList/TObjectList/TAnyList - start at the end and proceed backwards.
Well, I have two things to say. [I apologize for responding in a new post, but I feel that this is an interesting topic by itself.]
1. Yes, my examples are simplified. Terribly so. Maybe they are even simplistic. At least some part of my readers seems to think so. But that's just the way I like them.
I'm not trying to enforce my ideas on my readers. I'm only displaying them to the public. That's why I tend to minimize all my examples. I'll show you the code, I'll show you the usage, but you should think about the solution and how it applies to your problems. Maybe you'll see that it can be useful and you'll adopt it. Maybe not. Maybe you'll remember it a year from now and suddenly see the light. Maybe you'll use it for a month or two and then decide that I'm a twit and that your previous ways were better. [In this case, please refer to the last paragraph in this post.] I don't really care. I'm giving my ideas out, I'm glad of every feedback and I'm happy if somebody else is using my code. I've received a lot from the Delphi community in past ten years and I like to give back as much as I can.
2. I don't like the 'traverse the list backwards and all will be well' approach to list deletion. I have a really strong aversion to it. It looks fine, it works fine but it smells really bad.
I was thinking a lot about why I dislike it so much and I think that the main reason is that it relies too much on the list internals. Admittedly, this is a very well documented behavior, which will never change in the future. Let's try again - it relies too much on the internals of the underlying structure. If at some point in the future you change the structure, this assumption may fail. OK, it is hard to imagine an underlying structure that would behave almost the same as the TList but would behave differently on Delete, but what if you just forgot to adapt this part of the code to the new structure? Unlikely, I agree.
People will complain that I can't give a strong reason for my fears and they will be correct. I don't have any good cause against this kind of list cleanup.
You see, if I learned something in my programming career, it's that some code should never be used. When you program, some things work out and some not. Some code works fine from the beginning and some causes problem after a problem and bug report after a bug report. A good programmer recognizes that and stops using the code/fragments/patterns that are likely to cause problems in the future. Somehow I have classified the 'downto deletion' in the same category. I don't remember why. That's why I'm not saying it is bad, only that it smells bad.
The other reason is the code readability. If find the code that explicitly states its intention more readable and more maintainable. Your point may, of course, differ.
---
May my ramblings not stop you from commenting. I'm happy when I receive comments that point to my errors, however justifiable they may be. Even if I don't agree with them, they make me rethink my strategies so at the end I'm even more sure in my approach.
Flame on!
Here's the thing... deleting items from a list whilst traversing forwards relies on specific list deletion behaviour (w.r.t the indices of items in the list).
ReplyDeleteNamely that indices of items following a deleted item will not be affected.
Doing so whilst traversing backwards specifically does not rely on any particular behaviour.
If following indices are affected, reverse traversal is unaffected. If following indices are NOT affected, reverse traversal is similarly not affected.
Whichever way you cut it, reverse traversal is the safe way.
Forward traversal is unsafe and needs protection against differing underlying implementations.
Unless of course some list implementation were to be encountered where deleting an item w.r.t it's index could result in a randomising effect on the indices of other items remaining in the list.
In that case I think which direction to traverse in would be the LEAST of your problems.
There is an interesting topic for discussion here.
When is a bad smell just an unusual smell that is actually a better smell than one that you've gotten so used to that you actually prefer?
There is an old saying that your own passage of wind always smells nicer than anyone elses.
The scientific rationale for that is that you are simply more used to your own smell.
;)
I think the point was that it could be simple and work, and it just seemed you were just making a bad excuse to cover a simple mistake.
ReplyDeleteJolyon, I fully agree with you :)
ReplyDeleteI think your right - code smell is mostly a personal thing. The code that smells most is the code that has bitten you in the past.
About what smells bad: I think forward traversal for deletion smells bad. A case can be made for the 'usafeness' of both methods (forward and backward traversal), I thinks its more likely that deleting an item in a list will affect the following items than the previos items in the list.
ReplyDeleteTo express my feelings in the 20+ years I've been programming: I never really found a problem in a forward traversal deletion, but somewhere, somehow along the line I marked it as bad and don't use it. When beginning to create a piece of code to delete items using a forward traversal, I always get that feeling I'm doing something bad. I always change the traversal to backwards. Don't know why, can't point at a specific incident. I just do.
Bottom line: yes, it's personal. It's not a bad example per se, either ways, but it's personal.
Now, what would be a fail safe way to delete items in a list that won't give either of use that unsafe feeling? There must be some algorithm goeroes out there that have an opinion...
@Bart: Forward list deletion works only if you take some very special precautions like manually incrementing the index (as you know) and that automatically introduces some very bad smell.
ReplyDelete---
To all others: I think I've finally figured it out. I digged into dark recesses of my brain and I found the reason for hating 'downto for' deletion.
There isn't any :)
It's more about the use of the indices. When I treat some list more like a collection, I dislike using indices because they imply some order and I know that in reality there isn't any. I'm just abusing the list for non-list purposes. That's why I'd like to cleanup this list without the use of the indices but with the standard enumerators that is impossible and I always had to resort to classical for loop. Now I don't have to anymore.
Bloody messed up, my mind. It works great in free-associative mode, can handle synthetical thinking well, but when I have to switch to analytical mode, I'm suddenly running at one tenth of my usual speed :(
So thanks to all for prodding. It really helped.
Hi all,
ReplyDeleteI'm a delphi developer from the first version and I like very much some opinion on how to...
So I would like to say that we have a big opportunity in seeing ideas on ways to do some of our daily job.
Well done, Gabr!
I definitely prefer "downto" for deletion. The one thing that makes the difference is the speed. If you have a list and delete the first item, you need to copy all the following items to the previous spot in memory (TList does that for you automatically). That doesn't matter very much if you only have a small list. But if you have a couple of thousand items in a list, you will notice the difference.
ReplyDeleteWhen deleting items from a list, both traversing up and down relies on knowledge of the underlying structure. The optimal "correct" way would probably be something like
ReplyDeletewhile List.HasItems do List.Delete(0); //(or DeleteFirst, DeleteRandom, DeleteLast or whatever)
or something to that effect. One problem, obviously, is that this is too slow on most list implementations, but it's the cleanest code nonetheless.
@svein: If you look at it that way, the cleanest method is to use List.Clear.
ReplyDeleteThe question was how to do traversion on a list from which you only want to remove selected members.
Shame on me. That's what happens when you comment on the comments, rather than the original post :-)
ReplyDelete"If at some point in the future you change the structure, this assumption may fail."
ReplyDeleteSome time early in my 25 year old software career, I came across a rather unique definition of a 'bug'.
Bug: An assumption made by a programmer that proves to be false.
I have lived by this for many years, and quickly realized that while coding, the fewer 'assumptions' one makes (even if true at the time), the fewer bugs one has (and your code 'smells' really nice.
Shawn Quick