Embarrassing code admission of the day (or why C.S. is good for you)
-
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.
-
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?
Technically, it "works". But, if you also define working as being the most reasonably efficient, then yes it it is a bug.
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braun -
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
Well I was under wrong impession that
List<>is implemented as linked list and not array. Blame it on C++ and STL :) -
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
Assuming this is C#, removing the first item in a list creates an entirely new list, which I think is a bug in the underlying list code since removing the first item should just rebase the list head at the next item. I think the underlying list code uses an array, believe it or not. It's not a "bug" per se, unless you consider taking a very long time to do a simple operation a bug.
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braun -
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
if you are looking for performance, use a for loop with a control variable and after the loop, call
List.Clear();you'll be saving numerous function calls... remove the first element each time it's not necessary nor benefic.I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
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
-
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
Julien Villers wrote:
A .NET List is supposed to be a dynamic array, with the expected performance of an array for single element access.
Blame it on C++ and STL, but who in his right mind name class for one data structure after another stucture? :)
Julien Villers wrote:
while list[n-1] is also 0(1)
Also, your original post (now edited) suggests that even you was under implession that
List<>is in fact a list not an array ;) -
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
Trust me when I saw it; I laughed.
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
-
Julien Villers wrote:
A .NET List is supposed to be a dynamic array, with the expected performance of an array for single element access.
Blame it on C++ and STL, but who in his right mind name class for one data structure after another stucture? :)
Julien Villers wrote:
while list[n-1] is also 0(1)
Also, your original post (now edited) suggests that even you was under implession that
List<>is in fact a list not an array ;)Yup, it's not a very good choice (ArrayList was nicer, but not generic). On the other hand, consider all the time gained by typing List<> instead of DynamicArray<> :D
'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
-
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
Just the performance thing? If you want to get into the nitty gritty of performance under dot net, what is the impact of something like List vs. List on garbage collection when we are talking millions of records. Discounting the fact that each string probably takes up more memory than a double.
-
Trust me when I saw it; I laughed.
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
In the examples you get with the Sync Framework, there's a similar issue from the other side. Basically, the code checks to see if it has already found a file and, if not, it adds it to the end. The problem, of course, is that the more files you add, the longer the find takes to complete for files that aren't present in the list. I know of companies who are using this in production code, little realising why their applications are slowing down.
*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
-
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.
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, remove from front."); DateTime start = DateTime.Now; while(fakelist.Count > 0){ double temp = fakelist\[0\]; fakelist.RemoveAt(0); } //end while TimeSpan diff = DateTime.Now - start; Console.WriteLine("Time: " + diff.TotalMilliseconds + " milliseconds."); Console.WriteLine("Populating list"); for(int i = 0; i < 100000; i++){ fakelist.Add(r.NextDouble() + i); } //end for Console.WriteLine("looping list,removing from back."); int inverseindex = fakelist.Count-1; start = DateTime.Now; while(fakelist.Count > 0){ double temp = fakelist\[inverseindex\]; fakelist.RemoveAt(inverseindex); inverseindex--; } //end while diff = DateTime.Now - start; Console.WriteLine("Time: " + diff.TotalMilliseconds + " milliseconds."); Console.WriteLine("Done!"); Console.WriteLine("Press enter to quit."); Console.ReadLine();output:
Populating list
looping list, remove from front.
Time: 5468,82 milliseconds.
Populating list
looping list,removing from back.
Time: 0 milliseconds.
Done!
Press enter to quit.So yes, there is a signifant performance gain. Well spotted. :thumbsup:
V.
-
Yup, it's not a very good choice (ArrayList was nicer, but not generic). On the other hand, consider all the time gained by typing List<> instead of DynamicArray<> :D
'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
STL uses
vectoras name for dynamic arrays, that's just two letters more and much less misleading :) -
STL uses
vectoras name for dynamic arrays, that's just two letters more and much less misleading :) -
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[^]Keith Barrow wrote:
another example as to why programming is hard
Programming is easy. Doing it properly is hard.
*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
-
How is that "much less misleading"? It has "mathematical vector" written all over it, but it's not even close to that. Meanwhile why should a list, sans "linked", be linked?
harold aptroot wrote:
How is that "much less misleading"?
Because it is not in direct collision with another widely used data structure and mathematical vector is not used as much as the other tow (list/array) in programming.
harold aptroot wrote:
Meanwhile why should a list, sans "linked", be linked?
It doesn't have to be, theoretically, but in practice when someone mention list, one usually assume it is a linked list and everything that goes with it (costs/benefits), and thus it is misleading. OP's example illustrates my point and I'll quote the guy before you how later edited his post:
Well, in .NET a List is well documented, so list[0] should be O(1), while list[n-1] should be O(n).
Add me to this list and you have 3 guys that were misled by the class name. Even though some of them were aware of how
List<>is actually implemented. -
Assuming this is C#, removing the first item in a list creates an entirely new list, which I think is a bug in the underlying list code since removing the first item should just rebase the list head at the next item. I think the underlying list code uses an array, believe it or not. It's not a "bug" per se, unless you consider taking a very long time to do a simple operation a bug.
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braunahmed zahmed wrote:
removing the first item in a list creates an entirely new list,
:wtf: seriously?
-
ahmed zahmed wrote:
removing the first item in a list creates an entirely new list,
:wtf: seriously?
Well not quite. This is what it does internally:
Array.Copy(this._items, index + 1, this._items, index, this._size - index);
*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
