.NET中SortedDictionary、SortedList和SortedSet

.NET Core / .NET Standard标准库中,命名空间System.Collections.Generic中,一些类是通过包System.Collections分发的。本文分析了该包中不那么基础又有点令人混淆的SortedDictionarySortedListSortedSet这三个类,并对有些相似的SortedListSortedSet进行了一些性能对比。

System.Collections包的源代码位于https://github.com/dotnet/runtime/tree/master/src/libraries/System.Collections

IDictionary

以下几种类型存储的是键值对形式的数据,它们实现了IDictionary<TKey, TValue>接口。

SortedDictionary

源代码显示,SortedDictionary的数据结构由基于红黑树的SortedSet实现。其特性与SortedSet一致。

源代码:https://github.com/dotnet/runtime/blob/master/src/libraries/System.Collections/src/System/Collections/Generic/SortedDictionary.cs

SortedList

源代码显示,SortedList使用两个线性表分别存储键和值。类成员数组keys存储键,类成员数组values存储值。

添加元素时,通过二分查找定位元素应插入的目标位置,并通过线性表的常规插入方法进行插入,复杂度为O(n)。若添加的元素本身已为升序,则复杂度为O(1)。插入时,若数组空间不足,则会按原数组的2倍长度或是所需要的数组大小(以较大的为准)创建新数组,并将原数据复制到新数组中,原数组由垃圾收集器按需回收。

查找元素时,使用二分查找,复杂度为O(log n)。

源代码:https://github.com/dotnet/runtime/blob/master/src/libraries/System.Collections/src/System/Collections/Generic/SortedList.cs

ICollection / ISet

以下的类型存储的是一般的对象,它们实现了ICollection<T>接口。

SortedSet

源代码显示,SortedSet的数据结构为红黑树。

SortedSet通过树结构存储数据,插入和查找都具有O(log n)的时间复杂度。但其插入时需要在堆上分配内存,无法像SortedList那样事先完成空间预留;插入有序数据时也无法提高性能。因为每个树节点所占的内存高于每个数组元素所占的内存,SortedSet占用的内存以及查找时读取的内存比SortedList要多。

通过IEnumerable接口对SortedSet进行遍历时,需要对红黑树进行中序遍历,因此它的枚举器(Enumerator)中有一个用于存储遍历状态的栈,占用的内存大小与红黑树的深度成正比。

源代码:https://github.com/dotnet/runtime/blob/master/src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.cs

性能对比

SortedListSortedSet的查找性能同样是O(log n),但它们的查找速度具体有何不同呢?用两种类型分别存储零到一百万的整数,并依次在集合中查找所有元素计算总时间,结果如下表所示,SortedListSortedSet快50%。

类型平均值误差(置信度99.9%)标准差
SortedList89.03 ms1.738 ms2.198 ms
SortedSet134.07 ms0.913 ms0.763 ms
SortedListSortedSet查找所用时间

SortedListSortedSet的遍历过程速度有何不同呢?用两种类型分别存储零到一百万的整数,并对其进行foreach循环计算总时间,结果如下表所示,SortedListSortedSet快110%。

类型平均值误差(置信度99.9%)标准差
SortedList13.27 ms0.253 ms0.271 ms
SortedSet27.92 ms0.383 ms0.320 ms
SortedListSortedSet遍历所用时间

上述测试使用BenchmarkDotNet测得。测试环境:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.17763.1282 (1809/October2018Update/Redstone5)
Intel Xeon Gold 5218 CPU 2.30GHz, 2 CPU, 64 logical and 32 physical cores
.NET Core SDK=3.1.100
  [Host]     : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT
  DefaultJob : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT

测试代码:

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System;
using System.Collections.Generic;

namespace MemoryTest1
{
    class Program
    {
        static void Main(string[] args)
        {
            var summary = BenchmarkRunner.Run<SearchBenchmark>();
            Console.ReadLine();
        }
    }
    
    public class SearchBenchmark
    {
        private const int Size = 1000000;
        private SortedList<int, int> sortedList;
        private SortedSet<int> sortedSet;

        public SearchBenchmark()
        {
            sortedList = new SortedList<int, int>();
            sortedSet = new SortedSet<int>();
            for (int i = 0; i < Size; ++i)
            {
                sortedList.Add(i, i);
                sortedSet.Add(i);
            }
        }

        [Benchmark]
        public void SearchFromList()
        {
            for (int i = 0; i < Size; ++i)
            {
                sortedList.ContainsKey(i);
            }
        }

        [Benchmark]
        public void SearchFromSet()
        {
            for (int i = 0; i < Size; ++i)
            {
                sortedSet.Contains(i);
            }
        }

        [Benchmark]
        public void EnumerateList()
        {
            foreach (var item in sortedList)
            {
            }
        }

        [Benchmark]
        public void EnumerateSet()
        {
            foreach (var item in sortedSet)
            {
            }
        }
    }
}

留言

有想法?请给我们留言!您的留言不会直接显示在网站内。