Использовать или не использовать Data.Map

Question

В настоящее время я работаю над Haskell API.Последний предоставляет некоторые функции, которые в настоящее время принимают список списков в качестве входных данных, то есть [(String,[(String, Double)])].

Для наглядности, вот пример списка списков упомянуто выше:

[
    ("A",   [
                ("I1", 1),
                ("I2", 2),
            ]
    ),
    ("B",   [
                ("I1", 3),
            ]
    )
]

Я определил некоторые приватные вспомогательные функции.Одна вспомогательная функция будет искать конкретные записи в этом списке (Data.List.find = O(n));другой будет выполнять пересечения;а другая функция преобразует представленный выше список в следующий:

[
    ("I1",  [
                ("A", 1),
                ("B", 3),
            ]
    ),
    ("I2",  [
                ("A", 2),
            ]
    )
]

Функция, которая выполняет преобразование, использует Data.Map, поскольку она предлагает некоторые функции, которые значительно упрощают этот процесс, например Data.Map.unionWithи Data.Map.insertWith.Ну, так как функция преобразования должна вызывать Data.Map.fromList и Data.Map.toList, я подумал, что было бы неплохо иметь карту карт вместо списка списков с начала,И поэтому я изменил свой пример ввода в соответствии с требованием карта карт .

Опять же, для целей визуализации, вот список сверху как карта карт :

Map.fromList [
    ("A",   Map.fromList [
                ("I1", 1),
                ("I2", 2),
            ]
    ),
    ("B",   Map.fromList [
                ("I1", 3),
            ]
    )
]

Благодаря этому шагу мой код потерял несколько строк, иблагодаря Data.Map.lookup, поиск нужного сейчас занимает всего O(log n) времени.

Тем не менее, я сейчас спрашиваю себя, действительно ли это хорошее решение? карта карт путь?Или функция преобразования должна работать с Data.Map.fromList и Data.Map.toList, а остальные должны работать с списком списков ?Или, что еще лучше, есть ли структура данных, которая больше подходит для такой работы?

Я с нетерпением жду ваших ответов.

Answer 1

Это пахнет как графики и ребра.Один немного другой подход, который может работать, а может и не работать, состоит в том, чтобы переработать вашу проблему, чтобы вместо [(String,[(String,Double)])] вы просто оперировали двумя кортежами строк.Тогда у вас есть [((String, String), Double)], и полученная карта имеет тип Data.Map.Map (String, String) Double.

В качестве альтернативы, если пространство строковых ключей ограничено и, таким образом, может быть эффективно отображено в машинные целые, посмотрите на использование IntMap.Та же семантика, что и у карты, за исключением того, что ключи ДОЛЖНЫ быть машинными (Int32 или Int64).Будет намного лучше производительность.

Answer 2

Инициализация карты карт все еще занимает O(n).

Сначала рассмотрим список списков.

Скажем, внешний список [a ₁ , a ₂ , ..., a _p ], а каждый внутренний элемент - _j = (l _j , [b ₀ , b ₁ , ..., b _{q j} ]). Тогда построение списка списков занимает O (n = & sum; _{j = 1} ^p q _j ).

Для инициализации внутренней карты требуется m _j . = O (q _j ). Для инициализации карты карт требуется O (& sum; _{j = 1} ^p m _j ) = O (n).

Answer 3

Конечно, это зависит от ваших фактических данных, но, возможно, вы могли бы использовать вместо этого Multimap?Есть реализации, плавающие вокруг (например, http://hackage.haskell.org/packages/archive/Holumbus-Distribution/0.0.1.1/doc/html/Holumbus-Data-MultiMap.html), но я не пробовал их.