当前位置:编程学习 > asp >>

.Net集合类的研究-有序集合(二)-SortedDictionary<TKey,TValue>

从类名就可以看出SortedDictionary<TKey,TValue>和上篇介绍的SortedList一样,都是有序集合,但从类内部的存储结构上看,两者有很大区别,SortedList内部用数组保存,只能算是有序线性表,而SortedDictionary<TKey,TValue>的内部结构是红黑树。

园子里有不少关于红黑树的好文章,已将红黑树分析的很透彻。所以这里不讨论红黑树的结构原理,而讨论SortedDictionary和SortedList有什么差异?何时应该选择使用SortedDictionary?

SortedDictionary内部结构是红黑树,红黑树是平衡二叉树的一种,SortedList是有序线性表,内部结构是Array,运用了二分查找法提高效率。从两者查找、插入、删除操作的时间复杂度来看,都为O(LogN),分辨不出优劣,但内部结构的不同导致了实际操作中的性能差异。

SortedDictionary和SortedList性能比较--插入
由于SortedList用数组保存,每次进行插入操作时,首先用二分查找法找到相应的位置,得到位置以后,SortedList会把该位置以后的值依次往后移一个位置,空出当前位,再把值插入,这个过程中用到了Array.Copy方法,而调用该方法是比较损耗性能的,代码如下:

private void  Insert(int  index, TKey key, TValue value)
{
    ......

    if  (index < this._size)
    {
        Array.Copy(this.keys, index, this.keys, index + 1, this._size - index);
        Array.Copy(this.values, index, this.values, index + 1, this._size - index);
    }
   
    ......
}
SortedDictionary在添加操作时,只会根据红黑树的特性,旋转节点,保持平衡,并没有对Array.Copy的调用。

现在我们用数据测试一下:循环一个int型、容量为100000的随机数组,分别用SortedList和SortedDictionary添加。(代码中的CodeTimer类,来自老赵的文章。)

public void SortedAddInTest()
{
    Random random = new Random();
    int array_count = 100000;
    List<int> intList = new List<int>();
    for (int i = 0; i <= array_count; i++)
    {
        int ran = random.Next();
        intList.Add(ran);
    }

    SortedList<int, int> sortedlist_int = new SortedList<int, int>();
    SortedDictionary<int, int> dic_int = new SortedDictionary<int, int>();
    CodeTimer.Time("sortedList_Add_int", 1, () =>
    {
        foreach (var item in intList)
        {
            if (sortedlist_int.ContainsKey(item) == false)
                sortedlist_int.Add(item, item);
        }
    });
    CodeTimer.Time("sortedDictionary_Add_int", 1, () =>
    {
        foreach (var item in intList)
        {
            if (dic_int.ContainsKey(item) == false)
                dic_int.Add(item, item);
        }
    });
}
结果跟之前分析的一样,为:

sortedList_Add_int
    Time Elapsed:    4,311ms
    CPU Cycles:    8,249,183,130
    Gen0:        0
    Gen1:        0
    Gen2:        0

sortedDictionary_Add_int
    Time Elapsed:    217ms
    CPU Cycles:    278,164,530
    Gen0:        1
    Gen1:        1
    Gen2:        0

由此可以看出:在大量添加操作的情况下,SortedDictionary性能优于SortedList。

SortedDictionary和SortedList性能比较--查询
两者的查询操作中,时间复杂度都为O(LogN),且源码中也没有额外的操作造成性能损失,那么他们在查询操作中性能如何?继续上面一个例子进行测试。

public void SortedAddInTest()
{
    ......

    CodeTimer.Time("sortedList_Search_int", 1, () =>
    {
        foreach (var item in intList)
        {
            sortedlist_int.ContainsKey(item);
        }
    });
    CodeTimer.Time("sortedDictionary_Search_int", 1, () =>
    {
        foreach (var item in intList)
        {
            dic_int.ContainsKey(item);
        }
    });
}
结果为:

sortedList_Search
    Time Elapsed:    602ms
    CPU Cycles:    1,156,460,630
    Gen0:        0
    Gen1:        0
    Gen2:        0

sortedDictionary_Search
    Time Elapsed:    667ms
    CPU Cycles:    1,256,685,950
    Gen0:        0
    Gen1:        0
    Gen2:        0

可以得出:两者在循环10w次的情况下,仅仅相差几十毫秒,可以看出,两者的查询操作性能相差不大。

SortedDictionary和SortedList性能比较--删除
从添加操作例子可以看出,由于SortedList内部使用数组进行存储数据,而数组本身的局限性使得SortedList大部分的添加操作都要调用Array.Copy方法,从而导致了性能的损失,这种情况同样存在于删除操作中。

SortedList每次删除操作都会将删除位置后的值往前挪动一位,以填补删除位置的空白,这个过程刚好跟添加操作反过来,同样也需要调用Array.Copy方法,相关代码如下。

public void RemoveAt(int index)
{
    ......

    if (index < this._size)
    {
        Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);
        Array.Copy(this.values, index + 1, this.values, index, this._size - index);
    }
   
    ......
}
情况跟添加操作一样,所以先在这里预测一下:在大量删除操作的情况下时,SortedDictionary的性能优于SortedList。

让我们继续上面的测试代码来验证这一点。

public void SortedDictionaryTest()
{
    //.......

    CodeTimer.Time("sortedList_Delete_String", 1, () =>
    {
        foreach (var item in temp_List)
        {
            sortedlist.Remove(item);
        }
    });

    CodeTimer.Time("sortedDictionary_Delete_String", 1, () =>
    {
        foreach (var item in temp_List)
  &nb

补充:Web开发 , ASP.Net ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,