我需要一个具有最快功能更新的类数组数据结构。我已经看到了一些灵活数组的不同实现，它们为我提供了这个属性（Braun，随机访问列表），但我想知道是否有专门针对我们对追加或前置不感兴趣的情况进行优化的实现- 只是更新。
问问题
1468 次
4 回答
13
Jean-Cristophe Filliâtre 有一个非常好的持久数组实现，在同一页链接的论文中进行了描述（这是关于持久联合查找，其中持久数组是核心组件）。该代码可直接在此处获得。
这个想法是将数组的“最后一个版本”表示为一个通常的数组，具有O(1)访问和更新操作，而以前的版本表示为这个最后一个版本，加上一个差异列表。如果您尝试访问该结构的先前版本，则该数组将“重新植根”以应用差异列表并再次为您提供有效的表示。
这当然不是所有工作流下的 O(1) （如果你经常访问和修改结构的不相关版本，你会经常支付重新root 成本），但对于主要使用一个版本，偶尔回溯到旧版本再次成为“最后一个版本”并获得更新，这是非常有效的。一个非常好的使用隐藏在观察纯界面下的可变性。
于 2013-02-05T09:22:56.877 回答
2
您使用哪种语言？在 Haskell 中，您可以将可变数组与 state monad 一起使用，而在 Mercury 中，您可以通过线程化 IO 状态来使用可变数组。Ocaml 也有一个数组模块，不幸的是它不保持引用透明性，如果那是你所追求的。
于 2013-02-05T03:56:22.877 回答
1
几天前，我还需要功能数组，并在这个 SO 问题上有所感受。我对 Gasche 提出的解决方案不满意，因为创建新数组是一项昂贵的操作，而且我需要经常访问旧版本的数组（我计划将其用于在数组上播放的 AI alpha/beta 实现）。
（当我说成本高昂时，我猜它是 O(n*h) 其中 h 是历史大小，因为在最坏的情况下，只有一个单元格被重复更新，并且需要遍历每个单元格的整个更新列表。我也当我需要重新路由阵列时，预计大多数单元格不会更新）。
这就是为什么我提出另一种方法的原因，也许我可以在这里得到一些反馈。我的想法是像在 B 树中一样存储数组，除了它不可变，我可以很容易地通过索引访问和更新任何值。
我在项目的存储库上写了一个小介绍：https ://github.com/shepard8/ocaml-ptarray 。选择顺序是为了使树的深度和顺序均匀，因此我可以获得很好的复杂性，仅取决于获取/设置操作的顺序，即 O(k^2)。
使用 k = 10，我最多可以存储 10^10 个值。实际上，我的数组不应包含超过 200 个值，但这是为了展示我的解决方案的稳健性。
欢迎任何建议！
于 2016-12-30T13:34:28.433 回答