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

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

[Matthys Terblanche]

Hi, why not iterate through it and clear the list after the loop? Since the items are all deleted anyway, wont that save time?

[M Hussain]

You can't remove at 0 index because it is being used in above variable. So to remove the 0 index object remove this line;

double temp = fakeList[0];

[gritter55]

Since you just created the list, its count is zero so it will never step into the while loop. Is it that simple?

[xtofl]

From the msdn (msdn entry on List.RemoveAt) "This method is an O(n) operation, where n is (Count - index)." Keeping Count as close as possible to index may improve performance with a factor O(n^2) :)

[Ralph Little]

It also seems to be a demonstration that using stock black-box objects where you don't know the underlying implementation has its faults. Same goes for portability. One particular implementation might be great on one platform but appalling on another. I'm not a big fan of the stl for that reason although I do like the underlying idea.

[Waldemar Sauer]

This is not necessarily a bug or performance problem. Never make an assessment on performance without using a profiler first. For all we know, this code could commonly execute on 0 or 1 items, in which case, there is not much wrong with the code above. What if the above is in a message pump where other threads are allowed to peak at the queue head? That said, with the way it is written above, I probably would have gone for the "foreach(){} fakeList.Clear();" construct.

[ekolis]

The while loop will never execute, as fakeList's initial length is zero.

[scotchfaster]

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

[Fabio Franco]

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

[weberrich]

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