[Setzer22]

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.

[sepp2k]

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

[Setzer22]

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.

[batesy3k]

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

sepp2k, 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?

[sepp2k]

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(2ⁿ) 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.

[Skydiver]

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

[Skydiver]

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

[Curtis Rutland]

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.

[Momerath]

Skydiver, 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

[sepp2k]

Momerath, 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

[Momerath]

sepp2k, 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

[Curtis Rutland]

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

// Type: System.Collections.Generic.Queue`1
// Assembly: System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089
// Assembly location: C:\Windows\Microsoft.NET\Framework\v4.0.30319\System.dll

using System;
using System.Collections;
using System.Diagnostics;
using System.Runtime;
using System.Runtime.InteropServices;
using System.Threading;

namespace System.Collections.Generic
{
  [DebuggerTypeProxy(typeof (System_QueueDebugView<>))]
  [ComVisible(false)]
  [DebuggerDisplay("Count = {Count}")]
  [Serializable]
  public class Queue<T> : IEnumerable<T>, ICollection, IEnumerable
  {
    private static T[] _emptyArray = new T[0];
    private T[] _array;
    private int _head;
    private int _tail;
    private int _size;
    private int _version;
    [NonSerialized]
    private object _syncRoot;
    private const int _MinimumGrow = 4;
    private const int _ShrinkThreshold = 32;
    private const int _GrowFactor = 200;
    private const int _DefaultCapacity = 4;

    public int Count
    {
      [TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")] get
      {
        return this._size;
      }
    }

    bool ICollection.IsSynchronized
    {
      get
      {
        return false;
      }
    }

    object ICollection.SyncRoot
    {
      get
      {
        if (this._syncRoot == null)
          Interlocked.CompareExchange<object>(ref this._syncRoot, new object(), (object) null);
        return this._syncRoot;
      }
    }

    static Queue()
    {
    }

    public Queue()
    {
      this._array = Queue<T>._emptyArray;
    }

    public Queue(int capacity)
    {
      if (capacity < 0)
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired);
      this._array = new T[capacity];
      this._head = 0;
      this._tail = 0;
      this._size = 0;
    }

    public Queue(IEnumerable<T> collection)
    {
      if (collection == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
      this._array = new T[4];
      this._size = 0;
      this._version = 0;
      foreach (T obj in collection)
        this.Enqueue(obj);
    }

    public void Clear()
    {
      if (this._head < this._tail)
      {
        Array.Clear((Array) this._array, this._head, this._size);
      }
      else
      {
        Array.Clear((Array) this._array, this._head, this._array.Length - this._head);
        Array.Clear((Array) this._array, 0, this._tail);
      }
      this._head = 0;
      this._tail = 0;
      this._size = 0;
      ++this._version;
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
      if (array == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
      if (arrayIndex < 0 || arrayIndex > array.Length)
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_Index);
      int length1 = array.Length;
      if (length1 - arrayIndex < this._size)
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
      int num = length1 - arrayIndex < this._size ? length1 - arrayIndex : this._size;
      if (num == 0)
        return;
      int length2 = this._array.Length - this._head < num ? this._array.Length - this._head : num;
      Array.Copy((Array) this._array, this._head, (Array) array, arrayIndex, length2);
      int length3 = num - length2;
      if (length3 <= 0)
        return;
      Array.Copy((Array) this._array, 0, (Array) array, arrayIndex + this._array.Length - this._head, length3);
    }

    void ICollection.CopyTo(Array array, int index)
    {
      if (array == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
      if (array.Rank != 1)
        ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
      if (array.GetLowerBound(0) != 0)
        ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
      int length1 = array.Length;
      if (index < 0 || index > length1)
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
      if (length1 - index < this._size)
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
      int num = length1 - index < this._size ? length1 - index : this._size;
      if (num == 0)
        return;
      try
      {
        int length2 = this._array.Length - this._head < num ? this._array.Length - this._head : num;
        Array.Copy((Array) this._array, this._head, array, index, length2);
        int length3 = num - length2;
        if (length3 <= 0)
          return;
        Array.Copy((Array) this._array, 0, array, index + this._array.Length - this._head, length3);
      }
      catch (ArrayTypeMismatchException ex)
      {
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
      }
    }

    public void Enqueue(T item)
    {
      if (this._size == this._array.Length)
      {
        int capacity = (int) ((long) this._array.Length * 200L / 100L);
        if (capacity < this._array.Length + 4)
          capacity = this._array.Length + 4;
        this.SetCapacity(capacity);
      }
      this._array[this._tail] = item;
      this._tail = (this._tail + 1) % this._array.Length;
      ++this._size;
      ++this._version;
    }

    public Queue<T>.Enumerator GetEnumerator()
    {
      return new Queue<T>.Enumerator(this);
    }

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
    {
      return (IEnumerator<T>) new Queue<T>.Enumerator(this);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
      return (IEnumerator) new Queue<T>.Enumerator(this);
    }

    public T Dequeue()
    {
      if (this._size == 0)
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);
      T obj = this._array[this._head];
      this._array[this._head] = default (T);
      this._head = (this._head + 1) % this._array.Length;
      --this._size;
      ++this._version;
      return obj;
    }

    public T Peek()
    {
      if (this._size == 0)
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);
      return this._array[this._head];
    }

    public bool Contains(T item)
    {
      int index = this._head;
      int num = this._size;
      EqualityComparer<T> @default = EqualityComparer<T>.Default;
      while (num-- > 0)
      {
        if ((object) item == null)
        {
          if ((object) this._array[index] == null)
            return true;
        }
        else if ((object) this._array[index] != null && @default.Equals(this._array[index], item))
          return true;
        index = (index + 1) % this._array.Length;
      }
      return false;
    }

    internal T GetElement(int i)
    {
      return this._array[(this._head + i) % this._array.Length];
    }

    public T[] ToArray()
    {
      T[] objArray = new T[this._size];
      if (this._size == 0)
        return objArray;
      if (this._head < this._tail)
      {
        Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._size);
      }
      else
      {
        Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._array.Length - this._head);
        Array.Copy((Array) this._array, 0, (Array) objArray, this._array.Length - this._head, this._tail);
      }
      return objArray;
    }

    private void SetCapacity(int capacity)
    {
      T[] objArray = new T[capacity];
      if (this._size > 0)
      {
        if (this._head < this._tail)
        {
          Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._size);
        }
        else
        {
          Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._array.Length - this._head);
          Array.Copy((Array) this._array, 0, (Array) objArray, this._array.Length - this._head, this._tail);
        }
      }
      this._array = objArray;
      this._head = 0;
      this._tail = this._size == capacity ? 0 : this._size;
      ++this._version;
    }

    public void TrimExcess()
    {
      if (this._size >= (int) ((double) this._array.Length * 0.9))
        return;
      this.SetCapacity(this._size);
    }

    [Serializable]
    public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
    {
      private Queue<T> _q;
      private int _index;
      private int _version;
      private T _currentElement;

      public T Current
      {
        get
        {
          if (this._index < 0)
          {
            if (this._index == -1)
              ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
            else
              ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
          }
          return this._currentElement;
        }
      }

      object IEnumerator.Current
      {
        get
        {
          if (this._index < 0)
          {
            if (this._index == -1)
              ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
            else
              ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
          }
          return (object) this._currentElement;
        }
      }

      internal Enumerator(Queue<T> q)
      {
        this._q = q;
        this._version = this._q._version;
        this._index = -1;
        this._currentElement = default (T);
      }

      public void Dispose()
      {
        this._index = -2;
        this._currentElement = default (T);
      }

      public bool MoveNext()
      {
        if (this._version != this._q._version)
          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
        if (this._index == -2)
          return false;
        ++this._index;
        if (this._index == this._q._size)
        {
          this._index = -2;
          this._currentElement = default (T);
          return false;
        }
        else
        {
          this._currentElement = this._q.GetElement(this._index);
          return true;
        }
      }

      void IEnumerator.Reset()
      {
        if (this._version != this._q._version)
          ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
        this._index = -1;
        this._currentElement = default (T);
      }
    }
  }
}

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?

[Momerath]

Appears they implemented it as a circular queue using an array (line 220 in the spoiler leads me to this conclusion).

[sepp2k]

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

[Curtis Rutland]

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(n²).