immutable 不可变数据结构

in 编程
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

传统c系列语言,数据结构是可变的,例如c++中的数据结构实现,都是经典实现方案。

vector, set, map, unordered_map, priority_queue 对应着线性结构,树状结构,以及hash表结构等。

但是对于immutable 不可变数据结构来讲,例如 https://facebook.github.io/immutable-js/ , 它们的数据结构尽量是以 树状结构实现的,多子节点数,通过增加内存占用,来降低时间消耗。

因为immutable 结构的修改操作,需要构建一个新的 immutable结构, 高效的做法就是 将树状结构中修改的 子树部分路径,重新创建一份,而将未修改的 部分,直接挂在新的树状结构下面,这样就最大程度的减少了 创建新结构时候的 时间 和 内存消耗了

例如: erlang中的 array 结构 是一个10个孩子节点的树状结构

dict 实现为一个2层的树状结构,每个seg中存放16个元素,每个元素都是一个bucket

gb_sets 通用平衡树 实现的 sets

gb_tree 平衡树

orddict 只是一个排序了的 list

ordsets 类似也只是一个 list

关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看