AICon 上海站|90%日程已就绪,解锁Al未来! 了解详情
写点什么

.NET 不变集合深究

  • 2013-05-06
  • 本文字数:1760 字

    阅读完需:约 6 分钟

自从我们 1 月份报道了不可变集合后,该API 进一步发展,并公布了更多关于内部机制的内容。首先是关于最新版本中做出了哪些改变的概要:

构造函数

尽管不可变集合仍然不提供构造函数,但不必再使用Empty 对象了。以前你会看到这样的代码:

var list = ImmutableList.Empty.Add(1, 2, 3);

新版本中有一个 Create 静态工厂方法,可以使用泛型类型推断。表达式将简化为:

var list = ImmutableList.Create(1, 2, 3);

兼容性

是否实现 IList接口是热议的话题。该接口的支持者认为,与引入 IReadOnlyList之前的库进行交互是十分必要的。而反对者则抱怨对于同样的旧库,没有必要在修改集合的值之前判断 IList.IsReadOnly 是否为 false。

最终,BCL 小组为遗留问题做出妥协,实现了 IList。尽管所有人都同意如果没有 IList.IsReadOnly() 会更好,但现在这背后已经有了太多复杂的因素。

对于公开的不可变类和接口的完整列表,请参阅兼容性表

相等性语义

与其他集合类型一样,不可变集合将只支持引用相等性。 BCL 小组写到

计算集合的值相等性是十分昂贵的,并且对嵌套集合(如 ImmutableDictionary<string, ImmutableList>)相等性的比较也很难定义。最终,提供这种功能在设计不同比较器时会导致更多的问题,就像客户指出的那样。

之前这些集合覆盖了 Object.Equals 而不是 op_equals。

还有人询问是否支持 IStructuralEquatable 。由于其“很难泛化”,BCL 小组已经放弃了支持该接口。例如,在有些场景下可能需要跳过集合中的某些项(如解析器中的空格节点),如果没有特殊的实现,这几乎是不可能的。

而且遗憾的是,为了防止使用继承来添加 IStructualEquatable,不可变类被设计为密封的。

平台支持

不可变集合库专为.NET 4.5 及以后的版本而设计。它利用了新的只读接口,并且开发者不想为旧库维护一个单独的版本。它还可用于 Windows 8 和“protable-net45+win8”配置。

序列化

不可变集合不支持使用 Serializable 特性的旧序列化设计。目前还没有确定是否支持其他序列化设计,如 DataContractSerializer。

本质

不可变集合基于 AVL 树(除栈和队列外)。你可以在不重新复制整个树的情况下在列表的开头、中间或结尾执行插入操作。在维基百科关于持久数据结构这篇文章的树这一节中,有关于这种插入的示例。

不可变散列表也使用了AVL 树。它没有使用在散列值上执行模操作这种普通散列表的桶设计,而是根据原始散列值对树进行排序。这意味着检索操作需要执行一个平均检索时间为O(log n) 的二进制搜索。

请记住在使用多线程操作时,大O 标记法会带来误导。不可变集合的一个替代方案是使用并发集合,它需要昂贵的内部锁来确保线程安全。

不可变集合有一个有意思的特性,它的内部节点并不是不可变的。为了降低构建集合时创建的垃圾,每个节点都起始于一个可编辑的状态。这允许构造函数改变已有的AVL 树,因为它添加了节点,而不是废弃并重新创建。当构造结束、不可变包装器返回的时候,节点将被冻结,以防止进一步修改。

另一个令人感到意外的设计决策是枚举器使用了对象池。在.NET 中,很多枚举器被设计为不会分配任何内存。如果从IList上获取枚举器,需要两次内存分配。但对于List,枚举器是一个结构,不需要任何内存分配。

同样,不可变集合也使用了结构作为枚举器。但由于其内部结构是一个树,因此枚举器需要用一个栈来保存之前访问过的节点,以进行跟踪。为了减少内存分配,将很多这样的栈存储在对象池中(实际也是一个栈),并由一个锁来进行保护。实际上,这是整个不可变集合库中唯一的锁。对枚举器调用Dispose 方法是至关重要的,否则栈将不能返回到对象池中。

更多信息请观看Chinnel 9 的视频不可变集合的内部工作原理

使用建议

在创建不可变集合时,最好是使用Create 函数一次性创建整个集合。这将允许集合对树进行预分配并直接填充节点。第二好的方法是使用builder,不过要调用ToImmutable 才能冻结节点。

在枚举不可变集合中的项时,要使用foreach 循环。由于其内部是树形结构,因此foreach 要比for 快很多。(注:从.NET 2.0 开始,即使是普通的列表,用foreach 读取也比用for 快很多。)

如果集合在创建之后不会改变,那么不可变集合的性能将比用只读包装器保护的普通集合差很多。不可变集合更适用于高效创建与其他集合有少许不同的集合。

查看英文原文 More on Immutable Collections in .NET

2013-05-06 07:051874
用户头像

发布了 59 篇内容, 共 24.6 次阅读, 收获喜欢 3 次。

关注

评论

发布
暂无评论
发现更多内容

一文讲透“MCP协议+LazyLLM”实战:零基础秒建Agent分身!

商汤万象开发者

AI LLM

热更新技术的范式重构:AI驱动下的智能生态基座构建

xuyinyin

Flutter跨端范式重构:小程序容器化驱动的高效App开发基座

xuyinyin

国产直升机发展现状及思考

DevOps和数字孪生

航空航天 低空经济

2025 AI+研发数字峰会,我们在「AI 生产力工具创新论坛」等你来

阿里巴巴云原生

阿里云 云原生 通义灵码

英特尔“大小脑融合”全新方案亮相:构建具身智能系统的理想选择

E科讯

用通义灵码写一个大学社团“自动化运营外挂” | 《趣玩》第3期

阿里巴巴云原生

阿里云 云原生 通义灵码

用通义灵码写一个大学社团“自动化运营外挂” | 《趣玩》第3期

阿里云云效

阿里云 云原生 通义灵码

JDK的SPI有什么缺陷?dubbo做了什么改进?

不在线第一只蜗牛

Java

群贤毕至成果丰,共绘行业新未来,2025慕尼黑上海电子展圆满收官!

极客天地

飞行器半实物联合仿真:技术解析与应用实践

DevOps和数字孪生

AI 英语能力评估App的开发

北京木奇移动技术有限公司

AI技术 AI教育 软件外包公司

用户说 | 手把手体验通义灵码 2.0:AI 程序员如何让我从“调参侠”进阶“架构师”?

阿里云云效

阿里云 云原生 通义灵码

【未来已来,智启新篇】三星Galaxy S25系列:定义旗舰体验

新消费日报

Apipost接口调试全解:从HTTP到gRPC,程序员必备的“协议生存指南

数据追梦人

三门峡文旅集团:用友BIP企业AI全栈云赋能黄河流域文旅产业升级

用友BIP

广州生物医药产业全景解析:如何抓住未来千亿级产业机遇?

安全乐谷

找工作 招聘 就业 广州 找实习

“思考更长时间”而非“模型更大”是提升模型在复杂软件工程任务中表现的有效途径 | 学术研究系列

阿里巴巴云原生

阿里云 云原生

启动!张一元携手用友BIP企业AI全栈云,百年茶香数智焕新

用友BIP

用友助力郴电国际司库建设项目成功上线,战略合作开启数智化转型新征程

用友BIP

故障定位系列-2-服务&接口双粒度动态拓扑,精准定位共享连接池故障

乘云数字DataBuff

可观测性 故障定位 智能运维 运维监控

稳就业,保民生:2025年就业形势与实操指南,助你把握职场先机

安全乐谷

找工作 招聘 就业 找实习 改简历

天润融通AI Agent引领零售行业客户服务变革,塑造持久竞争力

天润融通

用户说 | 手把手体验通义灵码 2.0:AI 程序员如何让我从“调参侠”进阶“架构师”?

阿里巴巴云原生

阿里云 云原生 通义灵码

2025 AI+研发数字峰会,我们在「AI 生产力工具创新论坛」等你来

阿里云云效

阿里云 云原生 通义灵码

酒仙桥的AI变形记

脑极体

AI

2025深圳机器人展览会·高交会

AIOTE智博会

高交会 机器人展 机器人展会 机器人博览会

世界地球日,DeCloud如何助力节能减排?

PowerVerse

DePIN 节能减排 DeCloud

Apipost协议全栈支持+国密算法,调试效率飙出星际!

数据追梦人

一天 Star 破万的开源项目「GitHub 热点速览」

电子尖叫食人鱼

GitHub

全球线上直播会议丨快速赋能企业,仿真技术如何实现降本增效?

Altair RapidMiner

仿真 CAE hyperworks SimSolid Simlab

.NET 不变集合深究_.NET_Jonathan Allen_InfoQ精选文章