Функциональная карта-подобная структура данных с данными произвольной длины в качестве ключей? - PullRequest
Новая
       32

Функциональная карта-подобная структура данных с данными произвольной длины в качестве ключей?

3 голосов
/ 12 апреля 2011

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

Для конкретности рассмотрим тип Haskell 

(Ord k) => Map [k] v

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

Ответы [ 3 ]

6 голосов
/ 12 апреля 2011

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

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

3 голосов
/ 12 апреля 2011

Три?

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

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

1 голос
/ 12 апреля 2011

Вот один из них: 

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)

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

...