06-05-排序集合-综合对比-SortedSet-vs-SortedDictionary-vs-SortedList选型

SortedSet、SortedDictionary 与 SortedList从语义和负载出发的选择指南系列C# 与常用数据结构源码剖析 · 排序集合篇前置知识二叉搜索树、红黑树、二分查找、摊销分析版本边界公共行为以项目目标框架的 API 契约为准内部结构以对应 .NET 发行 tag 为准一、先问“保存什么”再问“哪个更快”三个类型都能按比较器顺序枚举却表达两种不同抽象SortedSetT保存唯一元素元素本身既是数据也是排序键SortedDictionaryTKey,TValue保存键值映射按 key 排序SortedListTKey,TValue也保存键值映射按 key 排序并提供基于有序位置的 Keys/Values 视图访问能力。如果业务只有一组唯一时间点使用 Set如果要从配置键得到配置值使用 Dictionary 或 List 映射。不要为了某张性能表把映射塞进 Set也不要用DictionaryT,bool模拟 Set。语义越准确非法操作越难进入代码。本文所说的“树型”和“有序数组型”是现代 .NET 常见实现模型不是永久 ABI。具体节点字段、颜色编码、增长规则与 helper 都是私有实现。研究某个版本时要固定 TFM、运行时版本及dotnet/runtime发行 tagUnity 还要固定编辑器版本、脚本后端和目标 Player。下面没有把结构化伪代码冒充真实源码也不提供脱离环境的倍数。二、三种结构各自维护什么不变量2.1 SortedSet比较器等价类至多一个代表逻辑上它维护一棵按 T 排序的平衡搜索树。核心不变量是中序遍历结果按 comparer 严格递增Compare(x, y) 0的元素只能保留一个平衡约束把路径长度限制在 O(log n)Count 与树中逻辑节点数一致。Add返回 bool 很重要false 表示比较器认为已有等价元素而不一定表示object.Equals为 true。Set 适合成员关系、去重、集合运算、有序枚举和范围视图。2.2 SortedDictionaryTKey,TValuekey 唯一value 不参与定位它维护按 key 排序的映射。查找、插入和删除通过 comparer 沿平衡搜索结构定位value 只是关联负载。核心不变量是每个比较器等价类只能有一个 key且树形只由 key 决定。索引器map[key] value可添加或更新Add(key, value)对重复等价键按契约失败。修改已有 value 不需要重排所谓“修改 key”不是原地操作必须删除旧键并插入新键。2.3 SortedListTKey,TValue两个逻辑同步的有序序列其常见模型是并行的 key 和 value 存储keys[i]与values[i]组成一对并且有效 keys 严格有序index: 0 1 2 3 keys: [10] [25] [40] [90] values: [A ] [B ] [C ] [D ]查找 key 可二分插入 30 后为腾出位置需要移动后缀keys: [10] [25] [30] [40] [90] values: [A ] [B ] [E ] [C ] [D ]两个序列必须以相同位置、相同长度同步移动。公共调用者看不到私有数组也不应依赖容量增长公式稳定契约是键值映射、按键顺序以及公开的 Keys/Values 索引访问语义。三、API 语义对照相似名字背后并不相同需求SortedSetSortedDictionarySortedList唯一元素原生语义需人为选择 key/value需人为选择 key/value键值映射不直接提供原生语义原生语义按 comparer 枚举元素顺序key 顺序key 顺序重复判定元素比较为零key 比较为零key 比较为零范围视图有专门集合能力按目标 API 核验通常需定位/枚举或自行封装可二分边界后按位置访问位置式读取不属于核心契约不属于核心契约Keys/Values 视图可按索引读取集合代数并、交、差等不属于映射核心语义不属于映射核心语义“SortedList 支持按索引访问”不等于map[0]访问第零项映射自身的索引器参数是 key。位置访问通过其公开键/值列表视图或目标版本提供的相应 API 完成。具体成员名必须在目标 TFM 下编译核验不要从新版文档倒推旧运行时。var byId new SortedListint, string { [30] Mage, [10] Knight }; int smallestId byId.Keys[0]; string correspondingName byId.Values[0];分别读取 Keys 和 Values 依赖集合未在两次读取之间改变。普通排序集合不保证并发写安全若多步读取必须保持一致需要在应用层同步或先制作不可变快照。四、复杂度表必须连同前提一起阅读令 n 为集合元素数k 为输出范围内元素数C 为一次 comparer 调用的成本操作SortedSetSortedDictionarySortedList按元素/键查找O(C log n)O(C log n)O(C log n)新增O(C log n)O(C log n)定位 O(C log n) 移动 O(n)删除O(C log n)O(C log n)定位 O(C log n) 移动 O(n)更新已有 value不适用定位 O(C log n)定位 O(C log n)全量有序枚举O(n)O(n)O(n)已知位置读取非核心能力非核心能力O(1) 的视图索引读取输出 k 项范围至少 O(k)另加定位至少 O(k)另加定位边界二分后输出 O(k)树型集合的 O(log n) 更新还包含节点分配、引用跳转与局部平衡。SortedList 的 O(n) 移动通常发生在连续内存中常数项可能较低所以“小型集合中数组移动一定更慢”并不成立。相反大型集合在中部高频插入时线性移动会成为明确风险。复杂度也不等于完整延迟字符串比较可能检查多个字符文化相关比较可能比 ordinal 比较昂贵大型值类型在数组移动时复制更多字节扩容会分配新存储树遍历可能遇到缓存未命中。没有固定元素类型、规模和操作比例就没有可信的赢家。对重复插入也要看语义。三者先定位等价类再决定返回 false、抛异常或更新值它不是“什么也没做”的恒定成本。异常路径尤其不适合当正常的重复控制流可优先使用相应 Try 或 Contains 组合但多线程下普通集合仍需同步。五、比较器定义“身份”可变键会破坏定位排序集合依赖IComparerT/IComparerTKey形成稳定全序。至少应满足自反、符号反对称、传递以及比较为零形成传递的等价关系。比较结果在元素驻留集合期间必须稳定。public readonly record struct RankEntry(long PlayerId, int Score); sealed class RankComparer : IComparerRankEntry { public int Compare(RankEntry x, RankEntry y) { int score y.Score.CompareTo(x.Score); // 高分在前 return score ! 0 ? score : x.PlayerId.CompareTo(y.PlayerId); } }如果省略 PlayerId同分玩家比较为零SortedSet 会把他们归入同一等价类两个映射也无法保存两个同分 key。若业务身份是玩家就必须用稳定 ID 打破平局。避免用x.Score - y.Score比较整数减法可能溢出并产生错误符号。浮点键还要明确 NaN、正负零等排序语义最好使用框架 comparer 或经过充分测试的领域规则。字符串需明确 Ordinal、OrdinalIgnoreCase 或具体文化“使用默认值”也是一项领域决策而不是无影响选择。上面的RankEntry是只读值从类型层面阻止了就地改分。如果改用可变引用类型插入后直接修改Score会让元素的逻辑排序位置变化而数据结构没有机会重排// 伪代码反例假设 MutableRankEntry.Score 可写且比较器使用它排序。 var entry new MutableRankEntry(playerId: 42, score: 100); mutableSet.Add(entry); entry.Score 100; // 此后 Contains、Remove 和枚举都可能不再符合调用方直觉。正确模式是参与比较的对象不可变或在修改前 Remove构造新值后 Add。Dictionary/List 的 key 同样必须保持比较意义不变value 可更新因为它不参与定位。六、内存、GC 与缓存局部性树型结构通常以节点引用连接。节点可能是独立托管对象包含元素或键值、左右引用和颜色状态查找沿分支跳转局部性和预取通常不如连续数组。节点数量增加也会增加 GC 管理对象的压力。SortedList 的有效键和值通常位于连续存储中。全量枚举和按位置读取具有较好的空间局部性对值类型尤其可能紧凑。但容量大于 Count 时会有未使用槽位增长时需要新分配并复制删除引用类型 key/value 时还需清除释放区间中的引用避免延长对象生命周期。不能据此写“每元素固定多少字节”。实际内存取决于 32/64 位、对象头、对齐、运行时版本、TKey/TValue 是引用还是何种值类型、容量余量和具体私有布局。也不能把 GC 分配量等同于进程驻留内存。评价时至少观察构建过程总分配与最终 retained size操作后的 Gen0/Gen1/Gen2 行为和暂停峰值容量以及 Clear 后是否仍保留存储顺序枚举的缓存行为更新场景的节点分配或数组搬移Unity Player 中真实脚本后端与设备的帧时间。容量预估能减少 SortedList 构建时的扩容但高估会提高常驻内存。若数据最终静态可批量排序后再构建或选择更适合批量加载的形态具体构造 API 是否能避免逐项移动必须实测不能因为预设容量就误以为中部插入不再移动。七、范围查询先定义边界和输出再选结构范围需求至少包含四个问题边界是否包含、按哪个 comparer、结果需要视图还是快照、查询期间源集合是否变化。SortedSet 提供面向元素范围的能力例如目标 API 支持时可获取上下界之间的视图。视图通常与底层集合关联不应默认它是独立副本修改传播、边界外插入和枚举失效行为要查目标版本契约。var times new SortedSetint { 10, 20, 30, 40, 50 }; SortedSetint window times.GetViewBetween(20, 40); foreach (int time in window) Console.WriteLine(time); // 20, 30, 40边界语义以 API 契约为准SortedDictionary 没有必要假装成 Set 范围视图。可以从有序枚举中过滤并在超过上界时停止或封装按键定位的专用结构到底能否快速跳到下界取决于公开 API 和实现不能从“底层是树”推导任意内部游标能力。SortedList 可对 Keys 做二分定位下界与上界再顺序读取对应位置。BinarySearch是否由其公开视图直接提供要按 TFM 核验应用也可实现 lower-bound。下面是对IListTKey的算法伪代码不是 BCL 源码static int LowerBoundTKey(IListTKey keys, TKey target, IComparerTKey comparer) { int lo 0, hi keys.Count; while (lo hi) { int mid lo ((hi - lo) 1); if (comparer.Compare(keys[mid], target) 0) lo mid 1; else hi mid; } return lo; }无论哪种结构输出 k 条记录至少需要 O(k)。所谓 O(log n) 范围查询一般只描述定位起点而不是完成枚举的总成本。八、按生命周期分析构建、稳态更新与删除8.1 一次构建长期只读配置表、关卡元数据和静态 ID 映射常在加载期构建之后只查询或枚举。SortedList 值得优先实测因为连续存储、低节点数量和位置访问与此模式契合。但若加载输入顺序随机且规模大逐项 Add 会反复搬移可以先按同一 comparer 排序并验证无重复再选择构建流程。若运行期其实不需要始终有序更简单的方案可能是数组排序后只读二分或 Dictionary 查找加独立有序 key 列表。双结构会增加一致性责任只有需求同时要求快速哈希点查和有序输出时才值得。8.2 持续随机插入和删除在线时间表、动态区间索引或编辑器中的有序对象表如果频繁在中部更新树型 SortedDictionary/SortedSet 通常具有更可靠的 O(log n) 最坏边界。SortedList 每次移动后缀可能产生明显写放大。仍应测实际 n若集合很小结构简单和连续性可能抵消复杂度劣势。8.3 只更新 value如果 key 集合稳定只是频繁改变关联 valueSortedDictionary 与 SortedList 都先 O(log n) 定位随后更新 value。SortedList 不需要移动 key树也不需要重平衡。此时读写局部性、value 大小、容量和枚举模式比“更新”二字更能决定选择。8.4 删除模式影响数组成本SortedList 删除末尾项移动很少删除最前项移动几乎所有后续元素随机删除平均移动一部分区间。只写“Remove 是 O(n)”无法预测帧尖峰需要记录删除位置分布。树删除路径为 O(log n)但会比较、追踪节点并执行局部修复也不等于固定时间。九、Unity 案例配置与排行榜不要混成一个问题9.1 静态配置索引物品配置以整数 ID 唯一在加载后只读若还需要按 ID 顺序导出或区间扫描可比较 SortedList 与“排序数组 二分”。如果只做 ID 点查Dictionary 往往语义更直接。不要为了调试窗口偶尔排序就让所有运行时查找承担有序结构成本调试输出可在需要时复制并排序。加载流程应检测重复 ID而不是依赖索引器静默覆盖static SortedListint, ItemConfig BuildIndex( IEnumerableItemConfig source) { var result new SortedListint, ItemConfig(); foreach (ItemConfig item in source) { if (result.ContainsKey(item.Id)) throw new InvalidDataException($Duplicate item id: {item.Id}); result.Add(item.Id, item); } return result; }若规模和加载时间重要应把重复检测、输入是否已排序、序列化成本与最终 Player 内存一起基准。编辑器中的结果不能代表 IL2CPP 设备。9.2 动态排行榜排行榜需要区分“唯一玩家”和“唯一分数”。单纯SortedSet(int Score, PlayerId Id)能用 ID 打破同分但玩家分数变化时必须知道旧键才能 Remove。常见设计是一个按玩家 ID 的映射保存当前条目再用 SortedSet 保存排序键sealed class Leaderboard { private readonly Dictionarylong, RankEntry _byPlayer new(); private readonly SortedSetRankEntry _ranking new(new RankComparer()); public void SetScore(long playerId, int score) { if (_byPlayer.Remove(playerId, out RankEntry old)) _ranking.Remove(old); var current new RankEntry(playerId, score); // 不可变记录更安全 _byPlayer.Add(playerId, current); if (!_ranking.Add(current)) throw new InvalidOperationException(Comparer identity collision.); } }双结构提供 ID 点查与有序排名但每次更新必须原子地维护两者。异常、并发和存档恢复中任何一步失败都可能让它们不一致应封装在一个类型中并用不变量测试。若只需要反复取最高项而不需要完整名次和按玩家删除PriorityQueue 可能更贴近需求若要按名次随机访问树型 Set 并不原生提供 order statistic不能假定第 k 名为 O(log n)。9.3 帧循环与 GC不要每帧用 LINQOrderBy().ToList()重建完整榜单却也不要未经分析就把所有数据放入长期树节点。先测更新频率、展示频率和榜单规模。UI 每秒刷新几次时可以维护 Dictionary 并在刷新时生成快照每次分数变化都要求即时 Top-N 时持续有序结构可能合理。对象池并不能自动消除树节点或数组扩容也可能保留峰值容量。十、常见失败反例反例一用 SortedSet 保存“分数唯一”的玩家比较器只比较 Score使同分玩家被判重复。修复是加入稳定身份字段或重新确认业务是否真的只需唯一分数。反例二修改已经入树的排序字段修改 Score 后没有 Remove/Add破坏逻辑定位。修复是不可变 key/entry或以旧值删除再插入新值。反例三认为 SortedList 的容量预估消除了插入 O(n)容量只减少扩容不能消除为保持排序而移动后缀。修复是批量排序、改变构建算法或选树型映射。反例四为了“有序”放弃哈希结构业务每百万次点查才输出一次排序报告却让所有请求使用 O(log n) 比较。修复是评估 Dictionary 主索引在报告时排序快照或有纪律地维护辅助顺序索引。反例五依赖枚举期间修改或跨线程读取普通集合的枚举器通常检测版本变化这不是线程同步。修复是锁定操作边界、快照或采用适合的并发设计。反例六把私有实现当持久化格式反射序列化树节点、颜色或数组容量会绑定某个运行时内部布局。应只保存逻辑键值并在加载时重建集合。十一、可复现实验测自己的分界点下面是 BenchmarkDotNet 测试骨架代码是业务实验不是 BCL 源码。它把规模与操作阶段分开避免把构建和查询混成一个数字using BenchmarkDotNet.Attributes; [MemoryDiagnoser] public class SortedMapBenchmarks { [Params(32, 1_024, 32_768)] public int N { get; set; } private int[] _keys null!; private SortedDictionaryint, int _tree null!; private SortedListint, int _list null!; [GlobalSetup] public void Setup() { var random new Random(42); _keys Enumerable.Range(0, N).OrderBy(_ random.Next()).ToArray(); _tree new SortedDictionaryint, int(); _list new SortedListint, int(N); foreach (int key in _keys) { _tree.Add(key, key); _list.Add(key, key); } } [Benchmark] public int TreeLookup() { int sum 0; foreach (int key in _keys) if (_tree.TryGetValue(key, out int value)) sum value; return sum; } [Benchmark] public int ListLookup() { int sum 0; foreach (int key in _keys) if (_list.TryGetValue(key, out int value)) sum value; return sum; } }此骨架只测已构建后的命中查询。还应建立独立基准测随机构建、升序构建、中部插入、头/尾/随机删除、value 更新、全量枚举和范围输出否则结论会被一个工作负载偷换。实验报告需记录 SDK/运行时完整版本、TFM、Release 配置、JIT/AOT、CPU、操作系统、元素类型、comparer、输入种子和原始结果。Unity 应用则在目标 Player 用 Profiler 和可控回放采集帧耗时、分配和内存快照。不要把桌面 CoreCLR BenchmarkDotNet 数字直接宣称为 IL2CPP 性能。还要先验证结果正确防止基准测到错误或被优化掉所有容器应得到相同的键值集合和校验和构建基准每次迭代必须从干净容器开始删除基准不能让后续迭代面对已经为空的集合范围基准要返回消费过的结果。十二、最终选型清单优先选择SortedSetT当且仅当主要语义是唯一元素并需要有序枚举、集合代数或元素范围。确认 comparer 的零值正好对应业务重复身份。优先实测SortedDictionaryTKey,TValue当需求是有序键值映射且运行期存在持续、位置不确定的插入和删除希望保持对数级最坏更新边界。接受节点结构的内存与局部性成本。优先实测SortedListTKey,TValue当需求是有序键值映射数据构建后相对稳定强调紧凑存储、顺序扫描或按位置读取。确认构建和更新阶段的数组移动不会造成不可接受尖峰。在三者之外继续问只要快速点查而不要求持续有序是否应使用 Dictionary/HashSet只读数据是否可用排序数组加二分只反复取最高优先级是否应使用 PriorityQueue同时要 ID 点查和排名是否接受双索引及其一致性成本要第 k 名和排名统计是否需要带子树大小的 order-statistic tree 或其他专用结构comparer、可变键、并发、持久化和范围边界是否都有测试具体结论是否已在目标 .NET/Unity 平台和真实负载中复现选择排序集合不是从三列 O 符号中挑最小值而是在数据身份、更新模式、输出顺序、内存布局和平台约束之间做匹配。先用语义排除错误类型再用复杂度发现风险最后用可复现实验决定真实分界点。这样得到的结论不会依赖某个私有字段也不会随着一条未经证实的基准数字一起失效。下一篇ConcurrentDictionary线程安全字典的实现边界