BaselineAdd of size 1000 took 10856 ticksBaselineAdd of size 10000 took 47490 ticksBaselineAdd of size 100000 took 343267 ticks
ListAdd of size 1000 took 5459 ticksListAdd of size 10000 took 43505 ticksListAdd of size 100000 took 738327 ticks
PreSizedListAdd of size 1000 took 4241 ticksPreSizedListAdd of size 10000 took 152861 ticksPreSizedListAdd of size 100000 took 664572 ticks
WronglyPreSizedListAdd of size 100000 took 746042 ticksVeryWronglyPreSizedListAdd of size 100000 took 772499 ticksLinkedListAdd of size 1000 took 4210 ticksLinkedListAdd of size 10000 took 42905 ticksLinkedListAdd of size 100000 took 794595 ticksListRemoveByIndex of size 1000 took 145411 ticksListRemoveByObject of size 1000 took 3590562 ticks
- If you can help it, don't use Remove() - use RemoveAt()!
- For smallish lists, LinkedLists perform rather well
- The penalty for wrongly sizing lists seems small (maybe the code is wrong or maybe my understanding is!).
- It's remarkably hard to write generics that rely on generics (especially when LinkedList<> doesn't derive from the same interfaces as List<>)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace CollectionsTiming
{
class Program
{
private const int TestSize = 100000;
static void Main(string[] args)
{
var p = new Program();
p.DoIt();
}
public void DoIt()
{
InternalListAddTestRun("BaselineAdd", TestSize / 100, () => new NopList<TestObject>());
InternalListAddTestRun("BaselineAdd", TestSize / 10, () => new NopList<TestObject>());
InternalListAddTestRun("BaselineAdd", TestSize, () => new NopList<TestObject>());
Console.WriteLine();
InternalListAddTestRun("ListAdd", TestSize / 100, () => new List<TestObject>());
InternalListAddTestRun("ListAdd", TestSize / 10, () => new List<TestObject>());
InternalListAddTestRun("ListAdd", TestSize, () => new List<TestObject>());
Console.WriteLine();
InternalListAddTestRun("PreSizedListAdd", TestSize / 100, () => new List<TestObject>(TestSize / 100));
InternalListAddTestRun("PreSizedListAdd", TestSize / 10, () => new List<TestObject>(TestSize / 10));
InternalListAddTestRun("PreSizedListAdd", TestSize, () => new List<TestObject>(TestSize));
Console.WriteLine();
InternalListAddTestRun("WronglyPreSizedListAdd", TestSize, () => new List<TestObject>(TestSize / 100));
InternalListAddTestRun("VeryWronglyPreSizedListAdd", TestSize, () => new List<TestObject>(TestSize / 1000));
Console.WriteLine();
InternalListAddTestRun("LinkedListAdd", TestSize / 100, () => new LinkedList<TestObject>());
InternalListAddTestRun("LinkedListAdd", TestSize / 10, () => new LinkedList<TestObject>());
InternalListAddTestRun("LinkedListAdd", TestSize, () => new LinkedList<TestObject>());
Console.WriteLine();
InternalListRemoveTestRun("ListRemoveByIndex", TestSize, TestSize / 100, (list, index, obj) => list.RemoveAt(index));
InternalListRemoveTestRun("ListRemoveByObject", TestSize, TestSize / 100, (list, index, obj) => list.Remove(obj));
Console.WriteLine();
//InternalListRemoveTestRun("PreSizedAdd", TestSize, TestSize / 100, () => new List<TestObject>(TestSize / 100));
Console.WriteLine();
Console.ReadLine();
}
public void InternalListRemoveTestRun(string name, int totalSize, int removeSize, Action<List<TestObject>, int, TestObject> removeAction)
{
InternalTestRun(name, removeSize, () => InternalRemoveTestRun(totalSize, removeSize, removeAction));
}
public long InternalRemoveTestRun(int totalSize, int removeSize, Action<List<TestObject>, int, TestObject> removeMethod)
{
var testList = new List<TestObject>(totalSize);
for (int i = 0; i < totalSize; i++)
{
testList.Add(new TestObject(i));
}
SortedList<int, Tuple<int, TestObject>> toRemove = new SortedList<int, Tuple<int, TestObject>>(removeSize);
var rand = new Random();
while (toRemove.Count < removeSize)
{
int candidate = rand.Next(totalSize);
toRemove[candidate] = new Tuple<int, TestObject>(candidate, testList[candidate]);
}
Stopwatch s = new Stopwatch();
s.Start();
foreach (var tuple in toRemove.Values.Reverse())
{
removeMethod(testList, tuple.Item1, tuple.Item2);
}
s.Stop();
var result = s.ElapsedTicks;
return result;
}
public void InternalListAddTestRun(string name, int maxSize, Func<LinkedList<TestObject>> initialiser)
{
InternalTestRun(name, maxSize, () => LinkedListAddTestRun(maxSize, initialiser));
}
public void InternalListAddTestRun(string name, int maxSize, Func<IList<TestObject>> initialiser)
{
InternalTestRun(name, maxSize, () => ListAddTestRun(maxSize, initialiser));
}
public void InternalTestRun(string name, int maxSize, Func<long> testMethod)
{
var result = testMethod();
Console.WriteLine("{0}\tof size {1}\ttook {2} ticks", name, maxSize, result);
}
public long ListAddTestRun(int maxSize, Func<IList<TestObject>> initialiser)
{
Stopwatch s = new Stopwatch();
s.Start();
var testObject = initialiser();
for (int i = 0; i < maxSize; i++)
{
testObject.Add(new TestObject(i));
}
s.Stop();
var result = s.ElapsedTicks;
return result;
}
public long LinkedListAddTestRun(int maxSize, Func<LinkedList<TestObject>> initialiser)
{
Stopwatch s = new Stopwatch();
s.Start();
var testObject = initialiser();
for (int i = 0; i < maxSize; i++)
{
testObject.AddLast(new TestObject(i));
}
s.Stop();
var result = s.ElapsedTicks;
return result;
}
}
class NopList<T> : IList<T>
{
public void Add(T to)
{
}
public NopList()
{
}
public NopList(int capacity)
{
}
public int IndexOf(T item)
{
throw new NotImplementedException();
}
public void Insert(int index, T item)
{
throw new NotImplementedException();
}
public void RemoveAt(int index)
{
throw new NotImplementedException();
}
public T this[int index]
{
get
{
throw new NotImplementedException();
}
set
{
throw new NotImplementedException();
}
}
public void Clear()
{
throw new NotImplementedException();
}
public bool Contains(T item)
{
throw new NotImplementedException();
}
public void CopyTo(T[] array, int arrayIndex)
{
throw new NotImplementedException();
}
public int Count
{
get { throw new NotImplementedException(); }
}
public bool IsReadOnly
{
get { throw new NotImplementedException(); }
}
public bool Remove(T item)
{
throw new NotImplementedException();
}
public IEnumerator<T> GetEnumerator()
{
throw new NotImplementedException();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
throw new NotImplementedException();
}
}
class TestObject
{
public string MyKey { get; set; }
public string SomeRandomText { get; set; }
public int Index { get; set; }
public TestObject(int index)
{
MyKey = Guid.NewGuid().ToString();
SomeRandomText = Guid.NewGuid().ToString();
Index = index;
}
}
}
No comments:
Post a Comment