rgr*_*erg 9 ocaml haskell functional-programming immutability data-structures
我需要一个类似数组的数据结构,尽可能快地进行功能更新.我见过几个不同的实现提供我与这个属性(百灵,随机访问列表)灵活的阵列,但我不知道是否有是专为优化的情况下,当我们不感兴趣的追加或预先准备的实现 - 只是更新.
gas*_*che 13
Jean-CristopheFilliâtre有一个非常好的持久化数组实现,在同一页面链接的论文中描述(这是关于持久性union-find,其中持久性数组是核心组件).代码可以在那里直接使用.
我们的想法是,数组的"最后一个版本"表示为通常的数组,具有O(1)访问和更新操作,以前的版本表示为最后一个版本,以及差异列表.如果您尝试访问该结构的先前版本,则会将该阵列"重新连接"以应用差异列表,并再次向您显示有效表示.
这当然不是所有工作流程下的O(1)(如果您经常访问和修改结构的不相关版本,您将经常支付重新连接成本),但对于主要使用一个版本的常见工作流程,偶尔回溯到旧版本再次成为"最后一个版本"并获得更新,这非常有效.在观察纯粹的界面下隐藏的可变性的非常好用.