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

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

3 голосов
/ 24 октября 2009

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

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

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) эффективный в модификации - я хотел бы, чтобы это было быстро

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

Спасибо

Ответы [ 3 ]

2 голосов
/ 25 октября 2009

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

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

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

0 голосов
/ 24 октября 2009

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

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

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

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

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

0 голосов
/ 24 октября 2009

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

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

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

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

...