所以我正在查看SortedList< TKey,TValue>的实现.并且Add(其中调用Insert如下所示)的实现真的让我感到意外.
添加方法做出明显的二进制搜索来确定KVP应该去哪里的索引,但是Insert似乎可以显着改善(尽管当然是更大的比例)：
private void Insert(int index,TKey key,TValue value)
{
if (this._size == this.keys.Length)
this.EnsureCapacity(this._size + 1);
if (index < this._size)
{
Array.Copy((Array) this.keys,index,(Array) this.keys,index + 1,this._size - index);
Array.Copy((Array) this.values,(Array) this.values,this._size - index);
}
this.keys[index] = key;
this.values[index] = value;
++this._size;
++this.version;
}
如果我正确阅读,我保留在任何时候都是错的权利,这是一个O(2n)操作.
在我看来,值应该用指针来实现.类似于LinkedList的关键字的值,但没有链接,因为它不支持随机访问.更重要的是关键是简单地链接到它的价值. get操作不会慢一些,因为我们有指针也不会删除,而是添加操作现在是O(n).
有人可以明白为什么这个决定可能走向这个方向？
解决方法
这不应该让你感到惊讶,它在MSDN的SortedList文章中有详细的记录：
SortedDictionary has faster insertion and removal operations for unsorted data,O(logn) as opposed to O(n) for SortedList.
SortedDictionary使用红黑树(即“指针”),SortedList是一个数组.根据您收集的内容,您可以选择两者之间.两者都是O(logn)用于查找,但是如果您经常迭代集合,那么您可以在SortedList中获得很大的收益.它更有效地使用cpu缓存.在现代机器上产生巨大的差异.
另外请注意,向集合添加项目的效率在很大程度上取决于项目的排序方式. SortedDictionary真的喜欢随机数据,给它更好的几率,不必重新平衡树.将其排序给出最坏情况的O(n)行为. SortedList真的喜欢排序的项目,使添加O(1).
