写点什么

.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:051662
用户头像

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

关注

评论

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

架构师训练营作业-web性能压测示例代码

superman

极客大学架构师训练营

总结

孙强

一周信创舆情观察(7.13~7.19)

统小信uos

数据库 舆情 芯片

架构师训练营第七周作业

Bruce Xiong

全国第一枚企业区块链电子印章诞生

CECBC

萝卜章 区块链印章 全流程上链 e签宝

秒懂云通信:如何用阿里云平台发短信?

阿里云Edge Plus

阿里官方 Redis 开发规范

Bruce Duan

redis Redis开发规范

第7周作业一

孙强

第7章总结

武鹏

【研报下载】InfoQ《2020中国技术发展白皮书》重磅发布

InfoQ写作社区官方

写作平台 InfoQ 白皮书 研究报告 热门活动

报销流程太慢太复杂?区块链技术引入票据系统效率翻一倍

CECBC

数据共享 电子票据 优化业务 可信体系

你只加了两行代码,为什么要花两天时间?

Yukun

程序员 debug bug

乘风破浪的文思海辉,以及TA的行业数字化“新人设”

脑极体

MySQL常用函数

Bruce Duan

mysql常用函数

作业1

东哥

极客大学架构师训练营

【week07】作业

chengjing

架构师第七周学习总结

小蚂蚁

埋点全解析,你最关心的可视化埋点在这里!

易观大数据

架构师培训第七周练习

小蚂蚁

《深度工作》学习笔记(1)

石云升

读书笔记 专注 深度工作

SpringBoot分布式验证码登录方案

Bruce Duan

验证码 Kaptcha

【DevCloud·敏捷智库】如何利用故事点做估算

华为云开发者联盟

敏捷 敏捷开发 需求 故事 华为云

【week07】总结

chengjing

Kubernetes 1.0 发布刚六周年,IBM 却想招 12 年经验的

神经星星

程序员 Kubernetes 云原生 招聘 ibm

架构师训练第七周总结

Hanson

通过双 key 来解决缓存并发问题

Bruce Duan

缓存穿透 缓存并发 双key解决缓存并发

性能测试

考尔菲德

计算机网络基础(九)---网络层-内部网关路由协议

书旅

计算机网络 网络协议 操作系统 计算机基础

JAVA已过气?中俄大佬对话告诉你俄罗斯最受欢迎的编程语言是什么!

华为云开发者联盟

Java 开源 程序员 Lambda 编程语言

性能压测工具

武鹏

工作总结

Axe

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