相关疑难解决方法(0)

在讨论算法的时间复杂度时,"恒定摊还时间"是什么意思？

什么时候使用List vs LinkedList更好？

我开始在我的一些C#算法中使用一些LinkedList而不是Lists来希望加速它们.但是,我注意到他们感觉速度慢了.像任何优秀的开发者一样,我认为我应该尽职尽责并验证我的感受.所以我决定测试一些简单的循环.

我认为用一些随机整数填充集合应该就足够了.我在调试模式下运行此代码以避免任何编译器优化.这是我使用的代码:

var rand = new Random(Environment.TickCount);
var ll = new LinkedList<int>();
var list = new List<int>();
int count = 20000000;

BenchmarkTimer.Start("Linked List Insert");
for (int x = 0; x < count; ++x)
  ll.AddFirst(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();

BenchmarkTimer.Start("List Insert");
for (int x = 0; x < count; ++x)
  list.Add(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();

int y = 0;
BenchmarkTimer.Start("Linked List Iterate");
foreach (var i in ll)
  ++y; //some atomic operation;
BenchmarkTimer.StopAndOutput();

int z = 0;
BenchmarkTimer.Start("List Iterate");
foreach (var i in list)
  ++z; //some atomic operation; …