Embarrassing code admission of the day (or why C.S. is good for you)

[Pete OHanlon]

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

[Keith Barrow]

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[^]

[_Zorro_]

Oh, what would be a better approach? ElementAt? I thought it would be the same...

[Claude Martel Olivier]

Not sure if it's intended or not but you're going to delete the list by deleting the first item over and over?

[_Zorro_]

Pete O'Hanlon wrote:

what happens when you remove at 0? How is this handled in terms of resizing when you remove from the start of the list

I see it now, thank's!

[Julien Villers]

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

[Julien Villers]

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

[Pete OHanlon]

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

[Mladen Jankovic]

Unless the actual implementation of the algorithm starts iterating from the end of the list, from some strange reason.

[Dario Solera]

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

[V 0]

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.

[Julien Villers]

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

[Mladen Jankovic]

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.

[GParkings]

IIRC its an extension method so very likely to be the same as it will be using the pre-existing public members unless of course there's some IL magic going on...

Pedis ex oris Quidquid latine dictum sit, altum sonatur

[TheGreatAndPowerfulOz]

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

[Mladen Jankovic]

Well I was under wrong impession that List<> is implemented as linked list and not array. Blame it on C++ and STL :)

[TheGreatAndPowerfulOz]

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

[Sentenryu]

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)

[Mladen Jankovic]

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

[Lost User]

Removing at the beginning is the stupidest thing to do, but not actually a bug is it? A performance regression sure..