Sharon wrote:
I used the wrong word here.
By inserting i mean: string[1] = value.
Not creating a new element.
List<T> have exactly the same compleity on assignment.
yes, insertion is expensive on AraryLists, but appending isn't. And you
can probably use Append and later do .Reverse if needed.
Append??
Sorry, I should have said "..you can probably use .Add to append and
later..."
If you allocate the array with a certain capacity the .Add upto that
limit are certainly O(1).
True.
About Add method at msdn:
If Count is less than Capacity, this method is an O(1) operation. If the
capacity needs to be increased to accommodate the new element, this method
becomes an O(n) operation, where n is Count.
However I have never had a problem filling a list, and i've made some
pretty big ones, so an O(n) insert, giving O(n^2) list-filling should
probably have bit me by now.
Lets look at a small test program:
using System;
using System.Collecti ons.Generic;
using System.Collecti ons;
class ArrayListAddCom plexityTest
{
[STAThread]
static void Main(string[] args)
{
int half_count = 10000000;
List<int> l = new List<int>();
DateTime start = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime half = DateTime.Now;
for (int i = 0; i < half_count; ++i)
l.Add(i);
DateTime end = DateTime.Now;
Console.WriteLi ne("first half = {0}s, second half = {1}s", (half
- start).TotalSec onds, (end - half).TotalSeco nds);
if (hack)
foreach (int i in l)
Console.WriteLi ne(i);
}
public static volatile bool hack = false;
}
The volatile boolean hack makes sure the compiler or runtime can't
optimize away the actual generation of the list :)
This program terminates with the output:
first half = 0,3605184s, second half = 0,3404896s
Which clearly shows:
1. List<T>.Add is fast enough for most anything
2. List<T>.Add is O(1), no matter what Capacity is used
Actually, it seems like .Add is sublinear, but that's just GC and
realloc messing with you. The figures are *definatly* solid enouogh to
prove that while List<T>.Add is O(n), it is also O(1) on my system,
atleast for upto 10 million ints.
I think -- but haven't actually tested -- that .Add in arraylists are
amortized O(1). I havent had any performance problems filling lists with
100s of thousands of entries, so I find it hard to believe that
ArrayList.A dd has complexity O(n).
But it does, when Count == Capacity.
Well, now it's tested and it's amortized O(1), Capacity doesn't matter.
If perfomance is the issue, use a profiler to find the problems. Don't
micro-optimize.
It really depends, if the array is fixed size, then there is no need to use
ArrayList.
I thinks it's better to understand how a collection works, than later change
the implementation
because the profiler shows a problem.
I agree that it's good to know how collections works, but just use
whatever's most handy untill there is actually a problem.
The tests i've done now shows clearly that using [] over IList<T> should
probably not be done for performance reasons anytime.
--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music:
http://ungdomshus.nu <=-
