Как заполнить Data.Map в пространстве и времени эффективным способом

Возвращение в Хаскелл через четыре года после первого взгляда на него. Меня всегда так поражает выразительность, и я сбился с толку из-за моей неспособности предсказать производительность пространства/времени.

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

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

Key : "AEHPS"  Value : ["HEAPS","PHASE","SHAPE"]

Версия С++ читает ~ 320000 слов словаря по одному, всего около 200 мс. Результирующая структура данных представляет собой хеш-карту, хранящуюся в array<99991, vector<string>>, и занимает около 12 мегабайт памяти.

Версия Haskell считывает один и тот же словарь примерно за 5 секунд, а размер кучи программы вздувается до 400 мегабайт! Я изменил тип значения в Data.Map от [String] до [ByteString], чтобы сохранить некоторую память, и это привело к сокращению потребления памяти программы примерно до 290 мегабайт. Это все еще в 24 раза больше, чем моя версия на С++. Это больше, чем просто "накладные расходы", хотя Data.Map является деревом вместо массива.

Поэтому я предполагаю, что я делаю что-то неправильно.

Весь модуль отображается здесь: (устаревшая ссылка)

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

Я попробую другие решения, например Data.HashMap, или заполнить Data.Map с помощью fromListWith. Тем не менее, я хотел бы рассказать о том, что происходит здесь. Спасибо за понимание!

Короткий ответ:

Использование Data.Map.Strict, заставляя оценивать элементы значения и сохраняя ключи как ByteStrings, тоже сделало чудо деления объема памяти почти на 3. Результат равен 100Meg, который только в два раза больше стандартного std::multimap<std::string, std::string> в С++ для одного и того же набора данных. Однако нет ускорения. Git обновлен.

Спасибо всем, кто внес свой вклад, здесь есть интересные материалы!

Ответ 1

Одна ошибка, которую вы делаете, еще не указана, заключается в том, что вы сохраняете неоцененные трюки формы B.pack word в списках, которые являются значениями на вашей карте. Это означает, что вы сохраняете по существу весь входной файл в неэффективном формате String во время построения вашей карты со стоимостью 24 байта на символ в своем входном файле. Использование API Data.Map.Strict не имеет никакого значения здесь, поскольку функции в этом API только заставляют элементы карты иметь слабую головную нормальную форму, которая для списка означает только то, является ли внешний конструктор [] или (:), и не оценивая ни один из элементов списка.

Еще одно улучшение, которое вы можете сделать, - использовать тип ShortByteString, доступный в последних версиях bytestring (тот, который поставляется с GHC 7.8, является достаточно новым). Это специально предназначено для минимизации использования памяти при хранении множества коротких байтов, причем компромисс заключается в том, что большинство операций с ShortByteString требуют копии.

Код примера кода András Kovács будет выглядеть следующим образом:

{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Data.List
import qualified Data.Map.Strict as M
import qualified Data.ByteString.Char8 as B
import qualified Data.ByteString.Short as B (ShortByteString, toShort, fromShort)

shortPack = B.toShort . B.pack

main = do
  words <- lines <$> readFile "dict.txt"
  print $ M.size $
    M.fromListWith (++) $ map (\w -> let !x = shortPack w in (shortPack $ sort w, [x])) words

Каждое из этих изменений экономит около 30% максимального числа мест в моих тестах, в общей сложности более 50% экономии пространства.

Ответ 2

РЕДАКТИРОВАТЬ: удалены ошибочные бенчмаркинга и комментарии, оставлены лишь незначительные советы. См. Reid Barton ответ для прямого решения вопроса OP.

Если вам не нужно менять словарь во время выполнения, то DAWG-s - это почти самое эффективное в пространстве-времени решение может получить (по крайней мере, для игровых игр).

Например, мы можем генерировать и сериализовать DAWG из вашего словаря, который занимает всего 295 Kb, и поддерживает довольно эффективный поиск и сопоставление префикса:

import qualified Data.DAWG.Packed as D -- from my "packed-dawg" package

main = do
  words <- lines <$> readFile "dict.txt"
  D.toFile "dict.dawg" $ D.fromList words -- serialize as "dict.dawg"

Ответ 3

На моем ноутбуке работает около секунды:

import qualified Data.Map as M
import qualified Data.Text as T
import qualified Data.Text.IO as T
import Data.List

type Dict = M.Map T.Text [T.Text]

newDict = M.empty

addWord:: T.Text -> Dict -> Dict
addWord word dict = M.insertWith (++) (T.pack $ sort $ T.unpack word) [word] dict

loadAnagramsFromFile fileName = do
    full <- T.readFile fileName
    let ls = T.lines full
    return $ foldr addWord newDict lsct ls

Это используется Text, с бородавкой для сортировки. Может быть лучший способ сортировки текста.