Embarrassing code admission of the day (or why C.S. is good for you)
-
Pretend the overall logic is entirely sound. The bug below is very subtle and is not a logic bug but a design bug, to make it harder, pretend the overall logic is correct. What is the bug?
//init the list and fill it
List fakeList = new List();
//Find the subtle bug
while (fakeList.Count > 0) {
double temp = fakeList[0];
//..do something
fakeList.RemoveAt(0);
}Hint: Ok, if it is too hard. Remember what a List is in C# and then remember the specifics of that data structure from intro to programming. Edit: The data structure is correct, and the logic is technically correct but wrong. Another Hint: Run it with a populated list of 100,000 elements and check the timing. There is a particular feature of this data structure that happens with this particular code that one small change would avoid.
Need custom software developed? I do custom programming based primarily on MS tools with an emphasis on C# development and consulting. I also do Android Programming as I find it a refreshing break from the MS. "And they, since they Were not the one dead, turned to their affairs" -- Robert Frost
Someone has probably pointed this out already, but since the end result of this function is that the list is emptied, there's no need to remove one element at a time. So instead:
foreach (double temp in fakeList)
{
// do something
}fakeList.RemoveAll();
But then, I don't have a C.S. degree...
-
Took me a moment or two to spot that. Couldn't really see it until I thought it through. Good catch - how did you find it? For others - what happens when you remove at 0? How is this handled in terms of resizing when you remove from the start of the list. As a comparison, remove from the last position instead (ok, it's not the same logical code, but it shows timings).
*pre-emptive celebratory nipple tassle jiggle* - Sean Ewington
"Mind bleach! Send me mind bleach!" - Nagy Vilmos
My blog | My articles | MoXAML PowerToys | Mole 2010 - debugging made easier - my favourite utility
Pete O'Hanlon wrote:
Took me a moment or two to spot that.
That's perfectly reasonable. The same way it took me a moment or too. Even when I saw it, I had to test it, because it all depends on the implementation of the list. The list could simply do the same thing it does for when removing at the end and move the pointer of the beginning of the list to the next element, instead of relocating everything.
"To alcohol! The cause of, and solution to, all of life's problems" - Homer Simpson "Our heads are round so our thoughts can change direction." ― Francis Picabia
-
Pretend the overall logic is entirely sound. The bug below is very subtle and is not a logic bug but a design bug, to make it harder, pretend the overall logic is correct. What is the bug?
//init the list and fill it
List fakeList = new List();
//Find the subtle bug
while (fakeList.Count > 0) {
double temp = fakeList[0];
//..do something
fakeList.RemoveAt(0);
}Hint: Ok, if it is too hard. Remember what a List is in C# and then remember the specifics of that data structure from intro to programming. Edit: The data structure is correct, and the logic is technically correct but wrong. Another Hint: Run it with a populated list of 100,000 elements and check the timing. There is a particular feature of this data structure that happens with this particular code that one small change would avoid.
Need custom software developed? I do custom programming based primarily on MS tools with an emphasis on C# development and consulting. I also do Android Programming as I find it a refreshing break from the MS. "And they, since they Were not the one dead, turned to their affairs" -- Robert Frost
Although I completely agree with this is being a bug in the viewpoint of performance. I am reluctant it say never use this construct. I can see instance where it could be used. How about a Push/Pop type of utilization of the list? FIFO (First In First Out)? While at it's core it is less efficient; The question would be utilization? What is the unknown it's the //.. do something portion of the logic? What's it doing?? Is it going to take more that 5 seconds (based off a previous message)? Does the extra processing outweigh this performance hit? Can it ever break out the loop so fakeList.Clear() cannot be use? What about if I really need to go down the list and not up, and walking backwards isn't an option? I'm not very familiar with C#, so I cannot comment on List vs LinkedList and performance. However, sometimes there is a rational which a code was used. Sometimes it's just wrong. I have used this construct before, and still don't think it was incorrect, yet I wasn't working with a 10k or 100k list. Just my two cents, IMHO..