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

[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..

[Ennis Ray Lynch Jr]

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

[Andy Brummer]

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.

[Julien Villers]

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

[Pete OHanlon]

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

[V 0]

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.

[Mladen Jankovic]

STL uses vector as name for dynamic arrays, that's just two letters more and much less misleading :)

[Lost User]

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?

[Pete OHanlon]

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

[Mladen Jankovic]

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.

[Chris Losinger]

ahmed zahmed wrote:

removing the first item in a list creates an entirely new list,

:wtf: seriously?

image processing toolkits | batch image processing

[Pete OHanlon]

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

[Lost User]

Well I do a lot of graphics, plenty of vectors around, but yea I guess they're not as common outside of graphics. I don't really like "vector" or "List" as names for a dynamic array. If they'd all just call it an ArrayList, that would make it really obvious. As for people usually assuming lists to be linked .. when I hear list I just think of "ordered bunch of stuff". Then when I start thinking about it I never assume it to be implemented as linked list, because it never is.

[Chris Losinger]

ah. it's one of those lists: an array in a fancy dress.

image processing toolkits | batch image processing

[Pete OHanlon]

Yup. It's a generic ArrayList.

*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

[Gary Wheeler]

The RemoveAt(0) call makes a copy of the list data, minus the first element, on each iteration. The algorithm here is actually written for a linked list. I've always thought the List class was stupidly named since it's really a resizable array, rather than a (linked) list.

Software Zen: delete this;

[BobJanova]

With the hints ... I get it. RemoveAt(0) causes the whole thing to be shuffled which is pretty expensive. Unless there's some other reason why you need to clean up as you go, you should just foreach the whole list. Or if it's actually a queue, use a Queue.

[TheGreatAndPowerfulOz]

well, like I said, and Pete confirmed, it's underlying implementation is an array.

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

[YvesDaoust]

I assume your concern is about the whole operation being O(N^2) when deleting at the front, instead of the O(N) you can achieve when deleting at the back. Is it ? I don't use to call such a misuse a bug, given that the effect is functionally correct. But you are right, if the rest of the processing of the list remains below O(N^2), you can call this a performance bug. BTW, I wonder how many tons of hidden similar deficiencies you can find in modern software. PS: the MS documentation does not really give hints on the complexity of the operations on containers, you have to educated-guess. Shame on them.