Эффективные для памяти строки в Haskell

Question

Обычно рекомендуемые строковые типы Haskell - это ByteString или Text.Я часто работаю с очень большим количеством коротких (размером с английское слово) строк, и обычно мне нужно хранить их в справочной таблице, такой как Data.Map.Во многих случаях я нахожу, что в этом случае таблица Strings может занимать меньше памяти, чем таблица ByteStrings.Распакованные данные. Векторы Word8 также (намного) более компактны, чем ByteStrings.

Какова лучшая практика, когда нужно хранить и сравнивать большое количество маленьких строк в Haskell?

Ниже я попытался сжать конкретный проблемный случай в небольшой пример:

import qualified Data.ByteString.Lazy.Char8 as S
import qualified Data.ByteString as Strict
import qualified Data.Map as Map
import qualified Data.Vector.Unboxed as U
import qualified Data.Serialize as Serialize
import Control.Monad.State

main =   putStr 
  . unlines . map show . flip evalState (0,Map.empty) 
  . mapM toInt 
  . S.words
  =<<
  S.getContents


toInt x = do  
  let x' =   
          U.fromList . Strict.unpack .  -- Comment this line to increase memory usage
           Serialize.encode $ x  
  (i,t) <- get
  case Map.lookup x' t of
    Just j -> return j
    Nothing -> do 
      let i' = i + (1::Int)
      put (i', Map.insert x' i t)
      return i

Когда я запускаю это для файла, содержащего около 400 000 слов английского текста, версия со строгими ключами строки байтов использует около 50 МБ памяти, а версия с векторами Word8 - 6 МБ.

Answer 1

В отсутствие других ответов я собираюсь выйти на конечность здесь.

Какова лучшая практика, когда нужно хранить и сравнивать большое количество маленьких строк в Haskell?

Если маленькие строки предназначены для чтения человеком (например, английское слово), тогда используйте Text.Если они предназначены для чтения только компьютером, используйте ByteString.Решение использовать строгие или ленивые варианты их зависит от того, как вы строите и используете эти маленькие строки.

Вам не нужно использовать свои собственные распакованные Vector s из Word8.Если вы столкнулись с определенной ситуацией, когда обычный String быстрее, чем Text или ByteString, добавьте подробности в StackOverflow, и мы попытаемся выяснить, почему.Если вы выполняете подробный анализ и можете доказать, что распакованный Vector из Word8 последовательно работает значительно лучше, чем Text или ByteString, тогда начните беседы в списках рассылки, irc, reddit и т. Д .;стандартные библиотеки не стоят на пороге, и улучшения всегда приветствуются.

Но я думаю, что весьма вероятно, что вы просто делаете что-то странное, как говорят Хаммар и Шанг.

PS для вашегоВ конкретном случае вместо хранения множества маленьких строк вам следует рассмотреть более подходящую структуру данных, отвечающую вашим потребностям, например, Trie, как предлагает danr.

Answer 2

A (строгий) ByteSting - это конструктор над распакованным ForiegnPtr до Word8 и двумя распакованными целыми числами.

A ForeignPtr - это другой конструктор по Addr# (прим. GHC)и ForeignPtrContents:

data ForeignPtrContents
  = PlainForeignPtr !(IORef (Finalizers, [IO ()]))
  | MallocPtr      (MutableByteArray# RealWorld) !(IORef (Finalizers, [IO ()]))
  | PlainPtr       (MutableByteArray# RealWorld)

...

Для коротких строк ByteStrings просто упаковывают слишком много администрирования, чтобы обеспечить непрерывное представление фактических «строковых» данных.

Для исходного вопроса - я бы проверил среднюю длину слова в вашем корпусе, но я не вижу, чтобы ByteString был более эффективным, чем String aka [Char], который использует 12 байтов на Char (источник оригинальной статьи ByteString).

Общая просьба к Хаскеллерам (не предназначенная для постера оригинального вопроса) - пожалуйста, прекратите избивать String aka [Char] - имеет смысл иметь как String, так и Text (и ByteString, когда вам действительно нужны байты).Или используйте Clean, если непрерывное строковое представление лучше подходит для коротких строк.

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

Answer 3

Я знаю, что это 6-летняя запись, но недавно я задавался вопросом, как найти эту полезную запись в блоге: https://markkarpov.com/post/short-bs-and-text.html. Кажется, что да, это признанная проблема, и Короткая (Текст/ ByteString) - решение.