Блог

Вполне может быть, что ответ на этот вопрос очевиден и громкий «такой вещи не существует», но я попробую: существует ли функциональная структура данных, подобная карте, которая более эффективна, чем стандартная карта, когда ключи имеют произвольный, часто очень большой, размер?

Для большей конкретности рассмотрим тип Haskell

 (Ord k) => Map [k] v
  

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

О хешировании не может быть и речи? У ключевой структуры нет префикса, который можно было бы эффективно вычислить?

Если нет, как насчет hashmap? Возьмите очень большой ключ, уменьшите его до чего-то очень маленького, используйте это как индекс в структуре.

• Хэш-карта при взломе.
• Доклад Йохана Тиббела о структурах хэш-дерева

Три?

Если у вас есть два почти идентичных длинных ключа, Map сравнит их оба с самого начала, но trie сравнит только те суффиксы, которые еще не были устранены предыдущими сравнениями (если вы понимаете, что я имею в виду). Таким образом, trie в этой ситуации был бы более экономичным по времени.

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

Вот один:

 module ListMap where
import Data.Map as M

data ListMap k v = ListMap { ifEmpty :: Maybe v, ifFull :: Maybe k (ListMap k v) }

empty :: ListMap k v
empty = ListMap Nothing M.empty

singleton :: [k] -> v -> ListMap k v
singleton [] v = ListMap.empty { ifEmpty = Just v }
singleton (k:ks) v = ListMap.empty { ifFull = M.singleton k (ListMap.singleton ks v) }

lookup :: Ord k => [k] -> ListMap k v -> Maybe v
lookup [] lm = ifEmpty lm
lookup (k:ks) lm = M.lookup k (ifFull lm) >>= ListMap.lookup ks

insert :: Ord k => [k] -> v -> ListMap k v -> ListMap k v
insert [] v lm = lm { ifEmpty = Just v }
insert (k:ks) v lm = lm { ifFull = M.alter (Just . insertion) k (ifFull lm) }
  where insertion = maybe (ListMap.singleton ks v) (ListMap.insert ks v)
  

По сути, это создает дерево префиксов для элементов списка, поэтому вы сравниваете только по мере необходимости.