3

我正在寻找一种高效的索引持久数据结构。我通常在 .NET 中工作并且知道 FSharp 的 Map 但是该实现和我知道的大多数其他实现只提供一个“索引”，即映射的左侧。

基本上这是场景

public class MyObject
    public int Id { get; }
    public int GroupId { get; }
    public string Name { get; }

对象的 ID 将是添加的全局唯一项集。GroupId 可能有重复的值，我希望能够查询具有匹配 GroupId 的所有值，并且在 GroupId 内名称将是唯一的，但可能在不同的 GroupId 之间重复。这不是我可以简单地创建 3 个字段的复合键的情况，因为我需要根据特定字段值独立访问项目组。

我可以做到这一点，并且在过去使用字典中的字典，这已在 STackoverflow 上的其他帖子中推荐过......但是，我也希望数据结构是 1）完全持久性和一切意味着 2）高效在内存中 - 意味着版本需要共享尽可能多的节点 3) 高效的修改 - 我希望它快

我意识到我在这里要求很多，但我想要求避免即使已经完成了重新发明轮子。

谢谢

4

3 回答 3

2

我不确定为什么在其他地方以及对您问题的现有答复中，人们建议使用现有结构。重叠结构（映射的映射、列表的映射、字典的字典......）仅适用于两个索引，如果一个比另一个更松散（两个具有相同索引的值 Index1 意味着这两个值具有相同的索引 Index2 )，这是一个不必要的约束。

我将使用地图记录，其中的数量与您需要不同的索引一样多，并且我将保持地图中存在的每个值都存在于同一记录中的所有其他值中的不变性。添加一个值显然需要将其添加到记录中的所有映射中。同样用于删除。通过封装，可以使不变量无法从外部越界。

如果您担心存储在数据结构中的值会重复，请不要这样做。每个地图只包含一个指针。它们都将指向该值的相同单一表示。共享将与简单的单索引地图一样好。

于 2009-10-25T01:01:23.303 回答
0

就像您可以使用字典词典一样，我希望例如 F# Maps Maps 可能是您想要的，例如

Map<int, Map<string, MyObject> >  // int is groupid, string is name

也许？我不清楚您是否还需要通过整数 ID 快速访问。

您还可以查看 Clojure 的库；我对 Clojure 了解不多，但一系列高效的持久数据结构似乎是 Clojure 的强项之一。

于 2009-10-23T21:38:46.223 回答
0

您似乎正在尝试将 OOP 原则应用于您的 FP 应用程序。

如果你从功能的角度来思考，你想要做什么？

例如，如果您使用列表，您可以告诉它您想要拉取所有具有特定组值的对象。

如果您需要按组快速访问，您可以拥有一个列表地图，以便您可以拉出组中的所有对象。

有不同的数据结构和许多功能适用于每个，但您应该首先从功能性而非面向对象的 POV 考虑您的问题。

于 2009-10-24T00:22:18.950 回答