Existe uma estrutura persistente índice eficiente de dados com vários índices

Question

Eu estou procurando uma estrutura de dados persistente indexada eficiente. I normalmente trabalham em .NET e estou ciente de Mapa de FSharp, porém, que a implementação e a maioria dos outros que eu estou ciente de apenas fornecer um 'index' single, o lado esquerdo do mapeamento.

Basicamente aqui é o cenário

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

Quando o ID de um objeto será definido globalmente únicos de itens adicionados. GroupId pode ter valores duplicados, e eu quero ser capaz de consultar para todos os valores com uma correspondência GroupId e dentro de um nomes GROUPID será única, mas pode ser duplicada em toda diferente GroupId de. Esta não é uma situação onde eu posso simplesmente criar uma chave composta dos 3 campos como eu precisam de acesso independente para grupos de itens com base em determinados valores de campo.

Eu posso fazer isso, e, no passado, usando dicionários de dicionários, que tem sido recomendado em outros posts aqui em stackoverflow ... No entanto, eu também quero a estrutura de dados a ser 1) Totalmente persistente e tudo que isso significa 2) eficiente na memória - o que significa que as versões necessidade de compartilhar como muitos nós quanto possível 3) eficiente na modifcations - Eu gostaria que ele seja rápido

Eu percebo que eu estou pedindo um pouco aqui, mas eu queria perguntar para evitar até mesmo a tentar re-inventar a roda se já tiver sido feito.

Graças

Answer 1

Eu não sou certo porque em outros lugares, e nas respostas existentes à sua pergunta, as pessoas recomendam para imbricados estruturas existentes. Imbricating estruturas (mapas de mapas, mapas de listas, dicionários de dicionários, ...) só funciona para dois índices se um é mais flexível do que o outro (dois valores que têm o mesmo índice para Index1 implica estes dois valores têm o mesmo índice para Index2 ), que é uma restrição desnecessária.

Gostaria de usar um registro de mapas, como muitos deles como você deseja diferentes índices, e gostaria de manter a invariante que cada valor que está presente em um mapa está presente em todos os outros no mesmo registro. Adicionando um valor, obviamente, requer adicionando-à todos os mapas no registro. Da mesma forma para a remoção. A invariante pode ser feito impossível de transgredir a partir do exterior através de encapsulamento.

Se você se preocupa que os valores armazenados em sua estrutura de dados seria duplicado, não. Cada mapa só iria conter um ponteiro. Eles teriam todos apontam para a mesma representação única do valor. Sharing será tão bom quanto ele já está com simples mapas single-indexado.

Answer 2

Assim como você poderia usar um dicionário de dicionários, espero que por exemplo um F # Mapa de Mapas pode ser o que você quer, por exemplo.

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

talvez? Eu sou claro se você também precisa de acesso rápido por id inteiro.

Você também pode verificar biblioteca de Clojure; Eu não sei muito sobre Clojure, mas uma série de estruturas de dados persistentes eficientes parece ser um dos pontos fortes do Clojure.

Answer 3

Parece que você está tentando aplicar princípios OOP para a sua aplicação FP.

Se você pensar em termos de funções, o que é que você está tentando fazer?

Se você usar uma lista, por exemplo, você pode simplesmente dizer que você quer puxar todos os objetos que têm um determinado valor de grupo.

Se você precisa de acesso rápido pelo grupo você poderia ter um Mapa de listas para que você pode puxar para cima todos os objetos em um grupo.

Existem estruturas de dados diferentes e muitas funções que o trabalho de cada um, mas você deve primeiro pensar em seu problema de uma funcional, não orientada a objetos, POV.