是否存在具有多个索引的高效索引持久数据结构

Question

我正在寻找一种有效的索引持久数据结构。我通常在.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）有效的修改 - 我希望它快速

我意识到我在这里要求很多，但我想要避免甚至试图重新发明轮子，如果它已经完成。

由于

Answer 1

我不确定为什么在其他地方，并且在对您的问题的现有回复中，人们建议叠加现有结构。嵌入结构（地图的地图，列表的地图，字典的字典，......）仅适用于两个索引，如果一个比另一个更宽松（两个具有相同索引的Index1意味着这两个值具有相同的Index2索引），这是一个不必要的约束。

我会使用地图记录，因为许多地图都需要不同的索引，我会保持不变量，即地图中存在的每个值都存在于同一记录中的所有其他值中。显然，添加值需要将其添加到记录中的所有地图。同样的删除。不可能通过封装从外部违反不变量。

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

Answer 2

正如您可以使用字典词典一样，我希望例如地图的F＃地图可能就是您想要的，例如。

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

可能？我不清楚你是否还需要通过整数id快速访问。

您也可以查看Clojure的图书馆;我对Clojure知之甚少，但是一系列高效的持久数据结构似乎是Clojure的优势之一。

Answer 3

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

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

例如，如果您使用List，则可以告诉它您要拉出具有特定组值的所有对象。

如果您需要按组快速访问，则可以拥有列表地图，以便您可以提取组中的所有对象。

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