Tuesday, July 26, 2016

The performance of setting T[] vs. List by index

Source: wikimedia.org

Let's compare asymptotic time complexity of two following loops:
int[] _array = Enumerable.Range(0, n).ToArray();
List<int> _list = Enumerable.Range(0, n).ToList();

//ListChangeByIndex
for (var i = 0; i < n; i++)
{
    _list[i] = i + 1;
}

//ArrayChangeByIndex
for (var i = 0; i < n; i++)
{
    _array[i] = i + 1;
}
How do you think, which one is faster?
.
.
.
.
.
.
.
.
Many developers think the fist one will be slower, because in each loop computer is forced to visit all nodes from 0 to i to finally set the variable.
However, that's not the case. Both loops have O(n) complexity. That's because in the .NET source we can clearly see that's underlying data structure for a List<T> is an array: list.cs. Therefore, those two loops are essentially equal.

2 comments:

  1. I recommend a nice article regarding .NET collections complexity: http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

    ReplyDelete
    Replies
    1. Indeed a must-read for every .NET pro. Here is another, simillar article: http://www.growingwiththeweb.com/2013/02/what-data-structure-net-collections-use.html

      Delete