使用功能更新最有效地实现数组？ [英] What is the most efficient implementation of arrays with functional updates?
问题描述
我需要一个类似数组的数据结构，具有最快的功能更新。我已经看到了几个不同的弹性数组实现，它为我提供了这个属性（Braun，Random Access Lists），但是我想知道是否有一个专门针对当我们对追加或预处理不感兴趣的情况进行优化的实现 - 只是更新。
I need an array-like data structure with the fastest possible functional update. I've seen a few different implementation of flexible arrays that provide me with this property (Braun, Random Access Lists) but I'm wondering if there is an implementation that is specifically optimized for the case when we are not interested in append or prepend - just updates.
推荐答案
Jean-CristopheFilliâtre有一个非常好的实现的持久性数组，这在该文件链接在同一页面（这是关于持久性union-find，其中持久性数组是核心组件）。该代码可以直接在在那里。
Jean-Cristophe Filliâtre has a very nice implementation of persistent arrays, that is described in the paper linked at the same page (which is about persistent union-find, of which persistent arrays are a core component). The code is directly available there.
想法是数组的最后一个版本表示为通常的数组， O（1）访问和更新操作，以前的版本表示为最后一个版本，加上差异列表。如果您尝试访问以前版本的结构，则阵列将被重新连接以应用差异列表，并再次提供有效的表示。
The idea is that "the last version" of the array is represented as an usual array, with O(1) access and update operations, and previous versions are represented as this last version, plus a list of the differences. If you try to access a previous version of the structure, the array is "rerooted" to apply the list of differences and present you again the efficient representation.
当然不是O（1）在所有工作流程下（如果您不断访问和修改结构的无关版本，您将经常支付重新调用成本），但是对于主要使用一个版本的常见工作流程，并且偶尔回溯到旧版本再次成为最后一个版本，并获得更新，这是非常有效的。在观察性纯界面下隐藏的可变性非常好用。
This will of course not be O(1) under all workflows (if you constantly access and modify unrelated versions of the structure, you will pay rerooting costs frequently), but for the common workflow of mainly working with one version, and occasionally backtracking to an older version that becomes the "last version" again and gets the updates, this is very efficient. A very nice use of mutability hidden under a observationally pure interface.
这篇关于使用功能更新最有效地实现数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
