10

我听说 .NETSystem.Collections.Immutable集合被实现为平衡二叉树，以Dictionary通过使用整数值GetHashCode作为排序键来满足它们的不变性约束，甚至是传统上对哈希表建模的集合，如 。

如果我有一种生成哈希码便宜的类型，并且比较便宜（例如stringor int），并且我不关心我的集合的排序性，那么选择是否有意义，ImmutableSortedDictionary因为底层数据结构无论如何都排序了？

4

3 回答 3

10

答案是肯定的，在某些情况下偏好是有意义的ImmutableSortedDictionary，例如使用Int32键。

就我而言，Int32我发现使用钥匙ImmutableSortedDictionary是一个更好的选择。

我已经使用 100 万个项目运行了一个小型基准测试：

  • 按 key 升序插入 1,000,000 个项目
  • 更新 1,000,000 个随机项目
  • 扫描 1,000,000 个项目，即对集合中的每个项目进行一次迭代
  • 读取 1,000,000 个随机项目
  • 删除 1,000,000 个随机项目

不可变字典<int, object>

Insert: 2499 ms
Update: 7275 ms
Scan:    385 ms
Read:    881 ms
Delete: 5037 ms

ImmutableSortedDictionary<int, object>

Insert: 1808 ms
Update: 4928 ms
Scan:    246 ms
Read:    732 ms
Delete: 3522 ms

ImmutableSortedDictionary比ImmutableDictionary所有操作都快一点。请注意，插入是按密钥的升序一次完成一项（因为它恰好与我的特定用例匹配）。

但是，您还应该考虑使用带有一些锁定的可变集合。写入可变Dictionary<int, object>对象要快一个数量级。

于 2015-06-04T08:21:32.820 回答
1

基于散列的集合在 .NET 上应该明显更快，因为：

  1. 它可以使用专门用于键的更有效的搜索树，int例如哈希树或帕特里夏树。

  2. 它的内部循环将几乎完全int进行比较而不是通用比较。

但是，如果您需要更好的性能，通常最好切换到可变集合，例如HashSet.

于 2015-04-14T01:15:01.783 回答
-3

这应该不重要。这篇博文的时间复杂度表明，虽然你确实从两者中获得了Dictionary.Add比SortedDictionary.Add( O(1)vs O(log n))更好的性能，ImmutableDictionary并且ImmutableSortedDictionary时间复杂度为O(log n)

于 2015-04-08T18:51:47.337 回答