Haskell中的内存有效字符串

Question

通常推荐的Haskell字符串类型似乎是ByteString或Text.我经常使用大量短(英文单词大小)字符串,并且通常需要将它们存储在诸如Data.Map的查找表中.在许多情况下,我发现在这种情况下,字符串表可以占用比ByteStrings表更少的内存.Word8的Unboxed Data.Vectors也比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字的英文文本的文件上运行时,带有严格字节串键的版本使用大约50MB内存,带有Word8向量的版本使用6MB.

Answer 1

在没有其他答案的情况下,我会在这里走出困境.

当需要在Haskell中存储和比较大量小字符串时,最佳做法是什么？

如果小字符串是人类可读的(例如英文单词),那么使用Text.如果它们只能由计算机读取,请使用ByteString.使用严格或惰性变体的决定取决于您如何构建和使用这些小字符串.

您不应该使用自己的未装箱Vector的Word8.如果您遇到特定情况,其中常规String速度超过Text或者ByteString,则将详细信息放在StackOverflow上,我们将尝试找出原因.如果你进行详细的分析,并且可以证明一个未装箱Vector的Word8一贯工作明显优于Text或者ByteString,那么就开始在邮件列表,irc,reddit等上进行对话; 标准库不是一成不变的,总是欢迎改进.

但是我觉得很有可能你只是在做一些奇怪的事情,正如hammar和shang所说的那样.

PS针对您的特定用例,而不是存储大量小字符串,您应该考虑更适合您需求的数据结构,例如,如danr所暗示的Trie.