0

函数式编程使用不可变数据。当您修改某些内容时，您会重新实例化“世界”，尽可能多地为您的增强世界重用以前的化身。

我正在探索 JavaScript 中的 FP。我在 Lisp 中创建了一个类似于 List 的 List 对象。你cons是一个新的头到一个现有的尾巴上。在将项目添加到持久列表时，我想创建一个与列表一致的持久索引。因此，如果我cons将新联系人添加到联系人列表中，我可能想要索引姓氏和电话号码，以便我可以快速定位项目，而无需有效地启动全表扫描。

问：在 JavaScript 中，可以构建什么样的持久数据结构来提供快速键控访问？

也就是说，我认为这个想法是在构建增强索引时重用以前的索引数据。没有将前一个索引上的所有键克隆到增强索引中，我发现这个问题令人麻木。通过克隆，这将在以编程方式加载数据时浪费大量内存。索引应该是内存高效的，并提供按值快速访问。

4

1 回答 1

3

您可能会使用某种自平衡二叉搜索树，就像使用任何其他语言一样（尽管在许多语言中，已经提供了这样的数据结构）。平均每个插入成本O(log n)，包括将创建O(log n)新搜索节点的重新平衡。

一种相当简单的数据结构是展开树。在 Chris Okasaki 的Purely Functional Datastructures中有一个可爱的扩展树功能实现。事实上，那本书中有很多非常酷的数据结构。强烈推荐。（如果你搜索，你可能会在网上找到冈崎的论文，其中也有展开树的实现。）

于 2013-04-24T00:39:14.000 回答