Data.IntMap

Описание

Эффективная реализация отображений от целых ключей к значениям (словари).

Этот модуль повторно экспортирует ленивый API Data.IntMap.Lazy, а также несколько устаревших функций со строгой оценкой. Обратите внимание, что эти функции имеют разные свойства строгости, чем в Data.IntMap.Strict: они оценивают только результат функции комбинирования. Например, значение по умолчанию для insertWith' оценивается только тогда, когда вызывается функция комбинирования и используется это значение.

Эти модули предназначены для импорта с квалификацией, чтобы избежать конфликтов имен с функциями Prelude, например:

 import Data.IntMap (IntMap)
 import qualified Data.IntMap as IntMap

Реализация основана на патрициевых деревьях с большим порядком следования. Эта структура данных особенно хорошо работает с бинарными операциями, такими как union и intersection. Однако мои тесты показывают, что она также (намного) быстрее при вставках и удалениях по сравнению с реализацией с балансировкой размера (см. Data.Map).

• Крис Окасаки и Энди Гиль, «Быстрые интегрируемые целые отображения», Рабочая встреча по ML, сентябрь 1998 г., страницы 77-86, http://citeseer.ist.psu.edu/okasaki98fast.html
• Д.Р. Моррисон, «/PATRICIA — Практический алгоритм для извлечения информации, закодированной в алфавитно-цифровом формате/», Журнал ACM, 15(4), октябрь 1968 г., страницы 514-534.

Комментарии к операциям содержат сложность операции в обозначении Big-O http://en.wikipedia.org/wiki/Big_O_notation. Многие операции имеют сложность в худшем случае O(min(n,W)). Это означает, что операция может стать линейной по количеству элементов с максимальным значением W — числом битов в Int (32 или 64).