Generic List<> behaviour

  • (2 Pages)
  • +
  • 1
  • 2

22 Replies - 3866 Views - Last Post: 09 August 2012 - 06:13 AM Rate Topic: -----

#1 Setzer22  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 19-June 12

Generic List<> behaviour

Posted 05 August 2012 - 09:03 AM

Hello everyone.

I'm using the List<> class (which comes into the System.Collections.Generic dll) In order to implement the Dijkstra's algorythm.

I want to determine the "range" from a given point to all the nodes of my "map" (not a graph, but a 2d array, as my map is more like a chessboard and I thought this would be easier using a 2d array), each square (or node, although it really isn't) has its own cost (as if the 4 edges connecting to that node were the same, not already familiar with graphs so I don't really know if I'm explaining this right), and, for example I want to know my movement range, if I'm able to go through a total cost of 15 (not 15 squares, but the equivalent, as some of the squares my cost twice to move through). So I'm actually calculating, the optimal path, to get my maximum move range from a given point.

Anyway, this was not actually needed, my main problem is my implementation of the algorythm is not working, it does the first 2 iterations of the loop right, and then, it starts assigning costs lower than they should be, or a lot of the adjacent squares with the same value. I'm not asking for a sollution to this, as it's preety much impossible If I don't explain first how everything works in my program.

So I'm trying to find what's going on and why isn't this working, and I was wondering it might be the list I'm using to store the squares which are going to be checked next, I thought this list was "in order" so what I did was, to add (using the List.Add() method) in an order of priority, new squares to check to this list (which I called CheckList).

After a lot of testing, I've started to think that something may be wrong about the way my list is working, I'm using the Add() method to add new squares to check (at the end of the list, I presume, as it was stated in the msdn documentation) And use Remove(0) to remove the first object of the list (the one which I was checking after it was checked). What I think it could be wrong is that last step, so my question is:

When I remove an element from a list, what happens to the list, does it keep the order, moving all the needed elements up in the list, or it messes up?

for example: my list contains: ["bananas", "apples", "strawberries", "potatoes"]
if i remove "bananas", would my list be like this? ["apples", "strawberries", "potatoes"]

Thank you very much, any help would be appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: Generic List<> behaviour

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,269
  • Joined: 21-June 11

Re: Generic List<> behaviour

Posted 05 August 2012 - 09:23 AM

Quote

When I remove an element from a list, what happens to the list, does it keep the order, moving all the needed elements up in the list


Yes.

Quote

for example: my list contains: ["bananas", "apples", "strawberries", "potatoes"]
if i remove "bananas", would my list be like this? ["apples", "strawberries", "potatoes"]


Yes.

Note though that using the Remove method (or for that matter the Add method) on a list while iterating over it will mess up your loop. No idea whether that's what you're doing, but it's something to be aware of.

Also note that calling Remove(0) on a List is an O(n) operation, so that might not be the best idea performance-wise. Using a Queue would probably be a better idea.

This post has been edited by sepp2k: 05 August 2012 - 09:19 AM

Was This Post Helpful? 0
  • +
  • -

#3 Setzer22  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 19-June 12

Re: Generic List<> behaviour

Posted 05 August 2012 - 09:26 AM

Well, My loop only uses the first element of the list, and does so until the list is empty, so to ensure the loop keeps working until I've checked all the squares needed, I keep adding squares to the list and removing the ones I've already checked from it. I want my loop to check them in the order I added them (just as simple as that) the only thing I wanted to know was if the list wasn't in order, as I thought that could explain why my code is working the way it does (which is not "right"...)

I'll keep looking into it, and try to figure out what's going on, now that I know it's not a problem with my list.

Thank you very much.
Was This Post Helpful? 0
  • +
  • -

#4 batesy3k  Icon User is offline

  • D.I.C Regular

Reputation: 41
  • View blog
  • Posts: 299
  • Joined: 10-September 09

Re: Generic List<> behaviour

Posted 06 August 2012 - 08:33 AM

Hi not to hijack the thread, but was interested in what was said:

View Postsepp2k, on 05 August 2012 - 05:23 PM, said:

Also note that calling Remove(0) on a List is an O(n) operation, so that might not be the best idea performance-wise. Using a Queue would probably be a better idea.

What is a O(n) operation? Is it where it recomputes the whole List object?
Was This Post Helpful? 0
  • +
  • -

#5 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,269
  • Joined: 21-June 11

Re: Generic List<> behaviour

Posted 06 August 2012 - 08:47 AM

An O(n) operation is an operation that takes time linear in the length of the list (asymptotically speaking), i.e. an operation that takes (roughly) twice as long for a list that has twice as many elements. Whereas an O(1) operation would be one that takes (roughly) the same amount of time no matter how long the list is. And an O(2n) operation would be one that takes twice as long for a list that contains only one more element.

And yes, remove(0) is an O(n) operation because it needs to go through the whole list and move each element one place to the front.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3622
  • View blog
  • Posts: 11,290
  • Joined: 05-May 12

Re: Generic List<> behaviour

Posted 06 August 2012 - 10:48 AM

Huh? I was always under the impression that List and List<T> is actually implemented as a doubly linked list, where as it was the old ArrayList that stored everything in an array. It was that ArrayList that would have the O(n) insert at front performance because it needed to adjust the array. A linked list with an insert at the front will have O(1).

Now, I'll have to go look at Reflector to see how List<T> (and List) are implemented...
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3622
  • View blog
  • Posts: 11,290
  • Joined: 05-May 12

Re: Generic List<> behaviour

Posted 06 August 2012 - 10:55 AM

Ah, I didn't even have to break out Reflector. The first line of the MSDN documenation says it all:

Quote

The List<T> class is the generic equivalent of the ArrayList class. It implements the IList<T> generic interface using an array whose size is dynamically increased as required.


That's sad, now I'll have double check some of the places where I was really assuming the faster insert at front performance. Lucky, most of the time, I append to the end.

My new learning for today...

Edit after: And Reflector confirms it. I found:
private T _items[];


This post has been edited by Skydiver: 06 August 2012 - 10:56 AM

Was This Post Helpful? 1
  • +
  • -

#8 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4531
  • View blog
  • Posts: 7,903
  • Joined: 08-June 10

Re: Generic List<> behaviour

Posted 07 August 2012 - 09:00 AM

Quote

Well, My loop only uses the first element of the list, and does so until the list is empty


This is the perfect use case for a Queue<T>. Queues are first-in, first-out collections.



Skydiver,

I learned something new today. By the way, for all of you without Reflector, there are two free alternatives that are also pretty good: JetBrain's dotPeek and Telerik's JustDecompile.
Was This Post Helpful? 0
  • +
  • -

#9 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Generic List<> behaviour

Posted 07 August 2012 - 10:54 AM

View PostSkydiver, on 06 August 2012 - 10:48 AM, said:

Huh? I was always under the impression that List and List<T> is actually implemented as a doubly linked list, where as it was the old ArrayList that stored everything in an array.

From the documentation on List<T>: The List<T> class is the generic equivalent of the ArrayList class. It implements the IList<T> generic interface using an array whose size is dynamically increased as required.

Even Queue<T> uses an array (which I find odd as I'd think a linked list would provide better performance). Again, from the docs: The capacity of a Queue<T> is the number of elements the Queue<T> can hold. As elements are added to a Queue<T>, the capacity is automatically increased as required by reallocating the internal array.

This post has been edited by Momerath: 07 August 2012 - 10:58 AM

Was This Post Helpful? 0
  • +
  • -

#10 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,269
  • Joined: 21-June 11

Re: Generic List<> behaviour

Posted 07 August 2012 - 11:16 AM

View PostMomerath, on 07 August 2012 - 07:54 PM, said:

Even Queue<T> uses an array (which I find odd as I'd think a linked list would provide better performance).


It wouldn't. The (ammortized) asymptotics are the same, but working with linked lists is generally slower because of the cost of allocating new nodes and the loss of locality.

Edit: Note that the implementation of Queue.Dequeue (which is O(1)) is quite different from that of List.Remove (which is O(n)). Presumably it simply increases the starting index by 1 (whereas List.Remove moves every element in the array starting at the given index).

This post has been edited by sepp2k: 07 August 2012 - 11:23 AM

Was This Post Helpful? 1
  • +
  • -

#11 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Generic List<> behaviour

Posted 07 August 2012 - 11:36 AM

View Postsepp2k, on 07 August 2012 - 11:16 AM, said:

It wouldn't. The (ammortized) asymptotics are the same, but working with linked lists is generally slower because of the cost of allocating new nodes and the loss of locality.


I'm guessing that it would depend on how you deal with dequeueing (spelling?) items. Using a pointer to the head of the queue would simplify it when using an array. Based on some timing tests I just did (results below) it does look like that is what they did. Going to have to dig up my Sedgewick book as I thought he implemented Queues as a linked list and performance was something he seemed to be concerned with.

Timing results:

Add to Queue 10,000 items: 3 Milliseconds
Add to List 10,000 items: 0 Milliseconds
Remove from Queue 10,000 items: 1 Milliseconds
Remove from List 10,000 items: 64 Milliseconds

Add to Queue 100,000 items: 3 Milliseconds
Add to List 100,000 items: 0 Milliseconds
Remove from Queue 100,000 items: 2 Milliseconds
Remove from List 100,000 items: 5,931 Milliseconds

Add to Queue 1,000,000 items: 26 Milliseconds
Add to List 1,000,000 items: 9 Milliseconds
Remove from Queue 1,000,000 items: 75 Milliseconds
Remove from List 1,000,000 items: 761,596 Milliseconds


I showed the three results mainly to highlight the performance of removing things from a list. It has a very bad Big O.

Edit: You modified your post while I was waiting for my timing results :) And it appears that RemoveAt is much worse than O(n), more like O(n^2).

This post has been edited by Momerath: 07 August 2012 - 11:40 AM

Was This Post Helpful? 0
  • +
  • -

#12 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4531
  • View blog
  • Posts: 7,903
  • Joined: 08-June 10

Re: Generic List<> behaviour

Posted 07 August 2012 - 11:46 AM

According to dotPeek, here's the actual implementation of System.Collections.Generic.Queue<T>

https://gist.github.com/3288231

(pasted here, but it's easier to read at the gist)
Spoiler


It's most definitely using an array and a pointer to head.

While we're at it, here's List<T>'s implementation.

Now I have a question: this line is from Dequeue:

this._head = (this._head + 1) % this._array.Length;


Why the modulus?
Was This Post Helpful? 1
  • +
  • -

#13 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: Generic List<> behaviour

Posted 07 August 2012 - 11:49 AM

Appears they implemented it as a circular queue using an array (line 220 in the spoiler leads me to this conclusion).
Was This Post Helpful? 1
  • +
  • -

#14 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,269
  • Joined: 21-June 11

Re: Generic List<> behaviour

Posted 07 August 2012 - 12:05 PM

Yes, it's circular. This way the memory consumption of the Queue won't increase infinitely if you continuously add and remove items to the queue while only having a small amount of elements in the queue at each time.

PS: Regarding RemoveAt being O(n^2): I don't think that's the case. At least I have a hard time seeing how it could be.

This post has been edited by sepp2k: 07 August 2012 - 12:07 PM

Was This Post Helpful? 0
  • +
  • -

#15 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4531
  • View blog
  • Posts: 7,903
  • Joined: 08-June 10

Re: Generic List<> behaviour

Posted 07 August 2012 - 12:20 PM

Well, here's the implementation of that method:

    public void RemoveAt(int index)
    {
      if ((uint) index >= (uint) this._size)
        ThrowHelper.ThrowArgumentOutOfRangeException();
      --this._size;
      if (index < this._size)
        Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index);
      this._items[this._size] = default (T);
      ++this._version;
    }


I don't think Array.Copy is O(n2).
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2