发布在即!企业 AIGC 应用程度测评,3 步定制专属评估报告。抢首批测评权益>>> 了解详情
写点什么

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

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

关注

评论

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

微服务过载保护原理与实战

万俊峰Kevin

微服务 go-zero Go 语言

Week10总结

lggl

总结 作业

架构师训练营第十周笔记

李日盛

学习 微服务 DDD

我家有猫

熊斌

生活方式 七日更 我家有猫

pagerank算法

橘子皮嚼着不脆

区块链的核心技术是什么?

CECBC

区块链

数据仓库的前世今生

数据社

数据仓库 七日更

架构师训练营 大作业(二)

netspecial

极客大学架构师训练营

重磅!四部门联合约谈蚂蚁集团!刚刚,约谈的主要内容曝光……

CECBC

金融

是的,我又换工作了

Rayjun

工作

区块链 链什么?

CECBC

区块链 分布式

日本准备推行AI婚配,年轻人会为“爱情算法”买单吗?

脑极体

从场景出发,日志聚类还可以这么玩

信仰圣光吧丶

AIOPS 日志聚类 日志治理

Flink比Spark好在哪?

数据社

flink spark 七日更

七周七并发模型

田维常

并发

第五周 技术选型作业

简简单单

炎币交易所APP系统开发|炎币交易所软件开发

系统开发

用领域驱动设计驱动系统的重构

积极&丧

架构师训练营 大作业(一)

netspecial

极客大学架构师训练营

架构师训练营第五周作业

zamkai

ARROW阿罗AOW币APP系统软件开发

系统开发

框架VS架构,看两者异同

田维常

框架

Java并发底层知识,锁获取超时机制知多少?

码农架构

Java java 并发

Week10作业

lggl

作业

安全架构:加密与解密

积极&丧

安全架构:反垃圾与风控

积极&丧

Spring 源码学习 10:prepareBeanFactory 和 postProcessBeanFactory

程序员小航

spring 源码 源码阅读

代理模式

soolaugust

设计模式 代理模式 七日更

AOP的姿势之 简化 MemoryCache 使用方式

八苦-瞿昙

aop

避坑指南,Elasticsearch 分页查询的两个问题,你一定要知道

AlwaysBeta

elasticsearch python 爬虫

软件组件设计原则

积极&丧

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