Julia中如何实现传参不丢顺序的不可变按值排序字典

现有方法顺序丢失的原因 #

• 方法1问题：基础Dict是基于哈希表实现的无序结构，本身不存储键值对的顺序信息。sort(dict; byvalue=true)返回的是排好序的键值对迭代器，重新赋值回Dict类型时，构造函数会按照键的哈希值重新排列存储位置，排序顺序直接丢失。
• 方法2问题：OrderedDict是可变结构，仅能保留插入顺序，多层函数传递过程中如果出现新增/删除键、修改键值对等操作，原有顺序就会被改动，无法保证顺序固定。
• 两种方法都没有从结构层面保证不可变，自然会出现偶发的顺序错乱。

推荐方案：使用Base内置的ImmutableDict #

ImmutableDict是Julia标准库自带的完全不可变字典结构，会永久保留构造时的键值对插入顺序，任何新增、删除、修改操作都会返回全新的字典实例，永远不会改动原对象的内容和顺序，跨函数传递时不存在顺序丢失的风险，同时完全支持标准字典的索引、迭代等接口，不需要将结果转成元组存储。

实现代码 #

# 原始字典
raw_dict = Dict(i => sqrt(i*rand()) for i = 1:20)
# 按值排序得到键值对迭代器，不需要调用collect()转元组
sorted_kv = sort(raw_dict; byvalue=true)
# 按排序顺序构造不可变字典
immu_sorted_dict = foldr(
    (kv, acc) -> Base.ImmutableDict(acc, kv.first => kv.second),
    sorted_kv;
    init=Base.ImmutableDict{keytype(raw_dict), valtype(raw_dict)}()
)

使用说明 #

• 可以直接用immu_sorted_dict[key]的方式取值，和普通字典用法一致
• 迭代、遍历键值对时永远遵循构造时的按值排序顺序
• 任何对该字典的修改操作都不会影响原对象，从根源上避免传递过程中的顺序篡改

备选方案：固定排序规则的SortedDict #

如果需要字典自动维护排序规则，不需要手动构造排序后再生成，可以使用DataStructures.jl提供的SortedDict，通过自定义排序逻辑实现按值排序。注意该结构是可变的，如果需要完全不可变，可以在构造完成后对其进行封装禁止修改，相比内置ImmutableDict需要额外引入第三方包。

注意：不要用普通Dict类型变量承接排好序的键值对集合，只要最终存储结构本身不支持保序/不可变，任何排序结果都会在构造时丢失。

内容的提问来源于stack exchange，提问作者stochastic learner