使用List< T>的性能差异是多少? vs LinkedList< T>在(c#)库中说 [英] What is the performace difference in using List<T> vs LinkedList<T> say in the (c#) library
问题描述
可能重复:
何时应使用列表与链接列表
Possible Duplicate:
When should I use a List vs a LinkedList
This question is related to my earlier question which was merged: related to List vs LinkedList
如果我不希望对数据结构使用按索引访问,那么通过在List上使用LinkedList可以节省多少?如果不是100%确定我永远不会使用索引访问,我想知道两者之间的区别.
If I expect not to use the access by index for my data structure how much do I save by using LinkedList over List ? If if am not 100% sure I will never use access by index, I would like to know the difference.
假设我有N个实例.在LinkedList中插入和删除只会是o(1)op,而在List中,我可能是O(n),但是由于它已优化,所以很高兴知道n的某些值之间的区别.说N = 1,000,000和N = 1,000,000,000
Suppose I have N instances. inserting and removing in a LinkedList will only be a o(1) op , where as in List it may me be O(n), but since it it optimized, it would be nice to know what the difference is for some values of n. say N = 1,000,000 and N = 1,000,000,000
推荐答案
好的,我做了这个实验,结果如下:
OK I did this experiment and here is the result:
这是具有1000,000个项目的列表和链接列表的经过的滴答声:
This is the elapsed ticks for a list and linked list with 1000,000 items:
LinkedList 500 insert/remove operations: 10171
List 500 insert/remove operations: 968465
与1000,000个项目相比,
链接列表的速度快 100倍.
Linked list is 100 times faster when compared for 1000,000 items.
这是代码:
static void Main(string[] args)
{
const int N = 1000*1000;
Random r = new Random();
LinkedList<int> linkedList = new LinkedList<int>();
List<int> list = new List<int>();
List<LinkedListNode<int>> linkedListNodes = new List<LinkedListNode<int>>();
for (int i = 0; i < N; i++)
{
list.Add(r.Next());
LinkedListNode<int> linkedListNode = linkedList.AddFirst(r.Next());
if(r.Next() % 997 == 0)
linkedListNodes.Add(linkedListNode);
}
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < 500; i++)
{
linkedList.AddBefore(linkedListNodes[i], r.Next());
linkedList.Remove(linkedListNodes[i]);
}
stopwatch.Stop();
Console.WriteLine("LinkedList 500 insert/remove operations: {0}", stopwatch.ElapsedTicks);
stopwatch.Reset();
stopwatch.Start();
for (int i = 0; i < 500; i++)
{
list.Insert(r.Next(0,list.Count), r.Next());
list.RemoveAt(r.Next(0, list.Count));
}
stopwatch.Stop();
Console.WriteLine("List 500 insert/remove operations: {0}", stopwatch.ElapsedTicks);
Console.Read();
}
}
这篇关于使用List< T>的性能差异是多少? vs LinkedList< T>在(c#)库中说的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!