将[(K,[V])]转换为[(V,[K])时的内存故障]

Question

我有一个279MB的文件,包含大约1000万个键/值对,大约有500,000个唯一键.它按键分组(每个键只需要写一次),因此给定键的所有值都在一起.

我想要做的是转换关联,创建一个文件,其中对按值分组,给定值的所有键都存储在一起.

目前,我正在使用Parsec作为元组列表读取对(K,[V])(使用惰性IO,因此我可以在Parsec处理输入文件时将其作为流处理),其中:

newtype K = K Text deriving (Show, Eq, Ord, Hashable)
newtype V = V Text deriving (Show, Eq, Ord, Hashable)

tupleParser :: Parser (K,[V])
tupleParser = ...

data ErrList e a = Cons a (ErrList e a) | End | Err e                

parseAllFromFile :: Parser a -> FilePath-> IO (ErrList ParseError a) 
parseAllFromFile parser inputFile = do                               
  contents <- readFile inputFile                                     
  let Right initialState = parse getParserState inputFile contents   
  return $ loop initialState                                         
  where loop state = case unconsume $ runParsecT parser' state of    
                        Error err             -> Err err             
                        Ok Nothing _ _        -> End                 
                        Ok (Just a) state' _  -> a `Cons` loop state'
        unconsume v = runIdentity $ case runIdentity v of            
                                      Consumed ma -> ma              
                                      Empty ma -> ma                 
        parser' = (Just <$> parser) <|> (const Nothing <$> eof)      

我试图将元组插入Data.HashMap.Map V [K]到转换关联中:

transpose :: ErrList ParseError (K,[V]) -> Either ParseError [(V,[K])]          
transpose = transpose' M.empty                                                   
  where transpose' _ (Err e)          = Left e                                
        transpose' m End              = Right $ assocs m                      
        transpose' m (Cons (k,vs) xs) = transpose' (L.foldl' (include k) m vs) xs
        include k m v = M.insertWith (const (k:)) v [k] m                  

但是当我尝试它时,我得到了错误:

memory allocation failed (requested 2097152 bytes)

我能想到一些我做错的事情:

1. 2MB似乎有点低(远低于我的机器安装的2GB RAM),所以也许我需要告诉GHC可以使用更多？
2. 我的问题可能与算法/数据结构有关.也许我正在使用错误的工具来完成工作？
3. 我试图使用懒惰的IO可能会回来咬我.

我现在倾向于(1),但我不确定.

Answer 1

为了允许大于可用内存的文件，最好一次以一口大小的块来处理它们。

这是将文件 A 复制到新文件 B 的可靠算法：

• 创建文件 B 并将其锁定到您的计算机
• 开始循环
  • 如果文件 A 中没有下一行则退出循环
  • 读入文件A的下一行
  • 将处理应用于生产线
  • 检查文件 B 是否已包含该行
  • 如果文件 B 尚未包含该行，则将该行附加到文件 B
  • 转到循环的开头
• 解锁文件B

将文件 A 的副本复制到临时文件夹中并在使用它时将其锁定，这样网络上的其他人就不会被阻止更改原始文件，但您拥有该文件的快照，这也是值得的此时程序开始。

我打算将来重新审视这个答案并添加代码。