写点什么

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

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

关注

评论

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

VMware ESXi 8.0U3 macOS Unlocker & OEM BIOS Huawei (华为) 定制版

sysin

macos esxi OEM

麻省理工IOT教授撰写的1058页Python程序设计人工智能实践手册!

我再BUG界嘎嘎乱杀

Python 人工智能 程序设计 后端 开发语言

Workflow通用并发控制组件:ResourcePool资源池

1412

c++ 开源项目 workflow 并发’

蓝易云 - 中小型企业为什么纷纷选择云服务器?

百度搜索:蓝易云

运维 服务器 云服务器 服务器租用 高防服务器

选择户外LED显示屏的4个理由

Dylan

互联网 广告 信息 LED LED显示屏

得物AB实验平台数据驱动决策实践

得物技术

大数据 架构 统计学 企业号2024年7月PK榜

分享 | 建设全渠道反欺诈平台 持续提升交易风险管控能力

芯盾时代

金融 反欺诈 风控系统 风险检测

项目提效神器:10款顶级项目工单管理系统

爱吃小舅的鱼

项目管理 项目管理系统 工单管理 项目工单管理 项目工单管理系统

RazorSQL for Mac(多功能SQL数据库编辑器) v10.6.1注册激活版

Rose

Magic Disk Cleaner for Mac(磁盘垃圾清理工具) v2.8.1激活版

Rose

蓝易云 - MySQL的Json类型个人用法详解

百度搜索:蓝易云

json MySQL 云计算 运维 数据

Sketch for mac(专业矢量绘图设计软件) v100.2中文激活版

Rose

蓝易云 - 在云上使用过哪些外网暴露服务,简单说一下优缺点(nginx-ingress,treafik,云alb,云loadblance)

百度搜索:蓝易云

nginx 运维 云服务器 Traefik loadbalance

「最新永久激活版」DaVinci Resolve Studio 19 ( 达芬奇影视后期调色剪辑) v19.0B5激活版

Rose

DBeaverEE for Mac(数据库管理) v24.1.3 企业激活版

Rose

Rhinoceros 8 (犀牛8 中文最新版) v8.9下载

Rose

作为ToB市场总监的你 被老板质疑过花销太大吗?

客户在哪儿AI

ToB营销 ToB获客 ToB增长 ToB销售

网络爬虫开发:JavaScript与Python特性的小差异

我再BUG界嘎嘎乱杀

Python JavaScript 爬虫 开发语言

AI技术图像编辑软件:Luminar Neo for Mac/win 激活版

你的猪会飞吗

苹果软件下载 Mac破解软件

Marked 2 for Mac(文件预览工具) v2.6.38免激活版

Rose

「空投」对于项目来说是好是坏?

TechubNews

如何冲破大模型时代的算力关卡?天翼云给出答案

脑极体

AI

Dato for Mac(菜单栏时钟软件) v5.3.1激活版

Rose

Ghost Buster Pro for mac(苹果电脑内存清理专家) v3.3.2激活版

Rose

Dynamic Wallpaper for Mac 个性化高清动态壁纸软件 苹果壁纸下载

Rose

阿里云 EMR StarRocks VS 开源版本功能差异介绍

阿里云大数据AI技术

大数据 数据仓库 OLAP EMR

借助大模型能力,晓多科技智能客服的效率与服务双提升

新消费日报

人工智能:重塑语言翻译的未来

天津汇柏科技有限公司

人工智能 语言翻译

DBeaverUE for Mac(数据库管理软件) v24.1.3 旗舰激活版

Rose

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