Embarrassing code admission of the day (or why C.S. is good for you)
-
O(n)?
-
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
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
-
fakeList[0] fakeList[0] fakeList[0] fakeList[0] Indexer on a list? [edit] For those who are asking - I'm suggesting that it might be a problem since accessing Nth element in the list has O(n) complexity.
yes. list being the simplest data type in which an order is applied to a set of data Though, judging by your rep scores on here you are more likely to know what you are talking about than I am, so ... am i missing something here, do we work in different languages with different concepts of 'list'? should we be using
list.ElementAt(0)
instead?
Pedis ex oris Quidquid latine dictum sit, altum sonatur
-
It's allowed. How else would you get the value at position
i?*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
Yes it is, But also it has O(n) complexity.
-
Cannot find any bug.
It's not a bug per se, it's an efficiency thing.
*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
-
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
Ennis Ray Lynch, Jr. wrote:
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.
But that is not called a bug, is it?
-
fakeList[0] fakeList[0] fakeList[0] fakeList[0] Indexer on a list? [edit] For those who are asking - I'm suggesting that it might be a problem since accessing Nth element in the list has O(n) complexity.
Didn't think that deserved a 1. Corrected. As a hint, the answer has to do with which side of the list you remove the element from. How is it handled re, resizing?
*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
-
O(n)?
-
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
Ah. Now you see, that is another example as to why programming is hard.
Sort of a cross between Lawrence of Arabia and Dilbert.[^]
-Or-
A Dead ringer for Kate Winslett[^] -
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
Not sure if it's intended or not but you're going to delete the list by deleting the first item over and over?
-
Yes it is, But also it has O(n) complexity.
When n = 0, you could have an exponential cost, it wouldn't matter much, now would it?
'As programmers go, I'm fairly social. Which still means I'm a borderline sociopath by normal standards.' Jeff Atwood 'I'm French! Why do you think I've got this outrrrrageous accent?' Monty Python and the Holy Grail
-
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
-
Ennis Ray Lynch, Jr. wrote:
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.
But that is not called a bug, is it?
Yes it is! http://www.codinghorror.com/blog/2011/06/performance-is-a-feature.html[^]
'As programmers go, I'm fairly social. Which still means I'm a borderline sociopath by normal standards.' Jeff Atwood 'I'm French! Why do you think I've got this outrrrrageous accent?' Monty Python and the Holy Grail
-
Not sure if it's intended or not but you're going to delete the list by deleting the first item over and over?
Basically, one way or the other there's a 0(n) operation - either in finding the element at position n, or removing the element at position n. Removing the element at n where n = 0 would, at first glance, appear to be a good optimisation. Unfortunately, it has side effects.
*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
-
When n = 0, you could have an exponential cost, it wouldn't matter much, now would it?
'As programmers go, I'm fairly social. Which still means I'm a borderline sociopath by normal standards.' Jeff Atwood 'I'm French! Why do you think I've got this outrrrrageous accent?' Monty Python and the Holy Grail
Unless the actual implementation of the algorithm starts iterating from the end of the list, from some strange reason.
-
Yes it is, But also it has O(n) complexity.
No, it's O(1) (because there's an array behind): http://msdn.microsoft.com/en-us/library/0ebtbkkc.aspx[^]
If you truly believe you need to pick a mobile phone that "says something" about your personality, don't bother. You don't have a personality. A mental illness, maybe, but not a personality. [Charlie Brooker] ScrewTurn Wiki, Software Localization Tools & Services and My Blog
-
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
Sorry, can't find anything wrong. The only thing I see on sight is you manipulate the size of a list while looping it. This is potentially dangerous, depending on what you do with it.
Random r = new Random((int) DateTime.Now.Ticks); List fakelist = new List(); Console.WriteLine("Populating list"); for(int i = 0; i < 100000; i++){ fakelist.Add(r.NextDouble() + i); } //end for Console.WriteLine("looping list, writing to file"); System.IO.StreamWriter writer = new System.IO.StreamWriter(@"C:\\temp\\fakelist.txt"); int index = 0; while(fakelist.Count > 0){ double temp = fakelist\[0\]; writer.Write(temp); writer.Write("\\t"); if(index%10 == 0){ writer.WriteLine(""); writer.WriteLine(DateTime.Now.ToString("dd/MM/yyyy HH:mm:ss:ffff")); writer.WriteLine(""); } //end if writer.Flush(); index++; fakelist.RemoveAt(0); } //end while Console.WriteLine("Done!"); writer.Close(); Console.WriteLine("Press enter to quit."); Console.ReadLine();V.
-
Unless the actual implementation of the algorithm starts iterating from the end of the list, from some strange reason.
Well, in .NET a List is well documented, so list[0] should be O(1), while list[n-1] is also 0(1) (see post below for MSDN link). A .NET List is supposed to be a dynamic array, with the expected performance of an array for single element access. So reversing the loop shown here would not even cause the access speed to be bad, but even if it were bad, it would not be as bad as the constant resizing (RemoveAt(0)) would be. Morality: use a Queue (or not).
'As programmers go, I'm fairly social. Which still means I'm a borderline sociopath by normal standards.' Jeff Atwood 'I'm French! Why do you think I've got this outrrrrageous accent?' Monty Python and the Holy Grail
-
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
I'm not familiar with internals of List<> in .Net. I was under assumption that it is implemented as plain vanilla list in which case the removal of either head or tail should consume the same amount of time, but your hint tells me that it isn't usual list.
