Существует ли эффективная индексная постоянная структура данных с несколькими индексами?

Question

Я ищу эффективную индексированную постоянную структуру данных.Обычно я работаю в .NET и знаю о карте FSharp, однако эта реализация и большинство других, о которых я знаю, предоставляют только один «индекс», левую часть сопоставления.

В принципе, вот сценарий

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

Где идентификатор объекта будет глобально уникальным набором добавленных элементов.GroupId может иметь повторяющиеся значения, и я хочу иметь возможность запрашивать все значения с совпадающим GroupId, а имена внутри GroupId будут уникальными, но могут дублироваться в разных GroupId.Это не та ситуация, когда я могу просто создать составной ключ из трех полей, поскольку мне нужен независимый доступ к группам элементов на основе определенных значений полей.

Я могу сделать это и в прошлом, используя словаря словарей, которые были рекомендованы в других постах здесь на Stackoverflow ... Однако я также хочу, чтобы структура данных была полностью устойчивой и все, что означает 2) эффективно В памяти - означает, что версии должны делиться как можно большим количеством узлов 3) эффективно в модификациях - я бы хотел, чтобы это было быстро

Я понимаю, что прошу здесь довольно многого, но я хотел попросить не пытаться даже изобретать велосипед заново, если это уже было сделано.

Спасибо

Answer 1

Я не уверен, почему где-то и в существующих ответах на ваш вопрос люди рекомендуют компоновать существующие структуры.Сложные структуры (карты карт, карты списков, словари словарей, ...) работают только для двух индексов, если один из них слабее другого (два значения, имеющие одинаковый индекс для Индекса1, подразумевают, что эти два значения имеют одинаковый индекс для Индекса2). ), что является ненужным ограничением.

Я бы использовал запись карт, столько из них, сколько вам нужны разные индексы, и я бы сохранил инвариант, согласно которому каждое значение, присутствующее на карте, присутствует во всех остальных в той же записи.Добавление значения, очевидно, требует добавления его ко всем картам в записи.Аналогично с удалением.Инвариант можно сделать невозможным для нарушения извне посредством инкапсуляции.

Если вы беспокоитесь, что значения, хранящиеся в вашей структуре данных, будут дублироваться, не делайте этого.Каждая карта будет содержать только указатель.Все они указывали бы на одно и то же представление значения.Совместное использование будет таким же эффективным, как и с простыми одноиндексными картами.

Answer 2

Точно так же, как вы могли бы использовать Словарь словарей, я ожидаю, что, например,Карта карт F# может быть тем, что вам нужно, например.

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

может быть?Мне неясно, нужен ли вам быстрый доступ по целочисленному идентификатору.

Вы также можете проверить библиотеку Clojure;Я мало что знаю о Clojure, но набор эффективных постоянных структур данных кажется одной из сильных сторон Clojure.

Answer 3

Похоже, вы пытаетесь применить принципы ООП к своему ФП-приложению.

Если вы думаете с точки зрения функций, что именно вы пытаетесь сделать?

Например, если вы используете список, вы можете просто указать ему, что хотите извлечь все объекты, имеющие определенное значение группы.

Если вам нужен быстрый доступ по группам, вы можете использовать карту списков, чтобы вы могли извлекать все объекты в группе.

Существуют разные структуры данных и множество функций, которые работают с каждой из них, но вам следует сначала подумать о своей проблеме с функциональной, а не объектно-ориентированной точки зрения.