发布于 由桃又

.NET中SortedDictionary、SortedList和SortedSet

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

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

性能对比

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

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

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

类型平均值误差（置信度99.9%）标准差
SortedList13.27 ms0.253 ms0.271 ms
SortedSet27.92 ms0.383 ms0.320 ms
SortedList和SortedSet遍历所用时间

上述测试使用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)
            {
            }
        }
    }
}

留言

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