¿Existe una estructura de datos persistente de índice eficiente con múltiples índices?

Question

Estoy buscando una estructura de datos persistente indexada eficiente. Normalmente trabajo en .NET y soy consciente del Mapa de FSharp. Sin embargo, la implementación y la mayoría de las otras que conozco solo proporcionan un 'índice' único, el lado izquierdo de la asignación.

Básicamente, aquí está el escenario

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

Donde el Id. de un objeto será un conjunto único global de elementos agregados. GroupId puede tener valores duplicados, y quiero poder consultar todos los valores con un GroupId coincidente y dentro de un GroupId los nombres serán únicos, pero pueden duplicarse en diferentes GroupId's. Esta no es una situación en la que simplemente pueda crear una clave compuesta de los 3 campos ya que necesito acceso independiente a los grupos de los elementos en función de los valores de los campos en particular.

Puedo hacer esto, y lo he hecho en el pasado, usando diccionarios de diccionarios, que se recomendó en otras publicaciones aquí en STackoverflow ... sin embargo, también quiero que la estructura de datos sea 1) Completamente persistente y todo lo que signifique. 2) eficiente en la memoria, lo que significa que las versiones necesitan compartir tantos nodos como sea posible 3) eficiente en modifcaciones: me gustaría que fuera rápido

Me doy cuenta de que estoy pidiendo bastante aquí pero quería evitar incluso intentar reinventar la rueda si ya se ha hecho.

Gracias

Answer 1

No estoy seguro de por qué en otra parte, y en las respuestas existentes a su pregunta, la gente recomienda imbricar las estructuras existentes. Las estructuras de imbricación (mapas de mapas, listas de listas, diccionarios de diccionarios, ...) solo funcionan para dos índices si uno está más suelto que el otro (dos valores que tienen el mismo índice para Index1 implica que estos dos valores tienen el mismo índice para Index2 ), que es una restricción innecesaria.

Yo usaría un registro de mapas, tantos de ellos como desee diferentes índices, y mantendría el invariante de que cada valor que está presente en un mapa está presente en todos los demás en el mismo registro. Agregar un valor obviamente requiere agregarlo a todos los mapas en el registro. Del mismo modo para la eliminación. El invariante se puede hacer imposible transgredir desde el exterior a través de la encapsulación.

Si te preocupa que los valores almacenados en tu estructura de datos se dupliquen, no lo hagas. Cada mapa solo contendría un puntero. Todos apuntarían a la misma representación única del valor. Compartir será tan bueno como lo es ya con mapas simples de un solo índice.

Answer 2

Al igual que podría usar un Diccionario de diccionarios, espero que, por ejemplo, un mapa F # de mapas puede ser lo que quieras, por ejemplo,

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

tal vez? No tengo claro si también necesita un acceso rápido por ID de entero.

También puedes revisar la biblioteca de Clojure; No sé mucho sobre Clojure, pero una gama de estructuras de datos persistentes y eficientes parece ser una de las fortalezas de Clojure.

Answer 3

Parece que está tratando de aplicar los principios OOP a su aplicación de PF.

Si piensas en términos de funciones, ¿qué es lo que estás tratando de hacer?

Si utiliza una Lista, por ejemplo, puede decirle que desea extraer todos los objetos que tienen un determinado valor de grupo.

Si necesita un acceso rápido por grupo, puede tener un Mapa de Listas para que pueda recuperar todos los objetos en un grupo.

Hay diferentes estructuras de datos y muchas funciones que funcionan en cada una, pero primero debes pensar en tu problema desde un punto de vista funcional, no orientado a objetos,