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

Ответ 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, с бородавкой для сортировки. Может быть лучший способ сортировки текста.