15

我有一个 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)

我试图将元组插入到 aData.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），但我不确定。

4

2 回答 2

1

数据有没有增加的可能？如果是，那么我建议不要将 while 文件读入内存并以另一种方式处理数据。

一种简单的可能性是为此使用关系数据库。这将相当容易 - 只需加载您的数据，创建一个适当的索引并根据需要对其进行排序。数据库将为您完成所有工作。我肯定会推荐这个。

另一种选择是创建您自己的基于文件的机制。例如：

  1. 选择一些l合理的限制加载到内存中。
  2. 创建n = d `div` l文件，d您的数据总量在哪里。（希望这不会超过您的文件描述符限制。您也可以在每次操作后关闭并重新打开文件，但这会使过程非常缓慢。）
  3. 按顺序处理输入并将每一对(k,v) 放入文件 numberhash v `mod` l中。这确保了具有相同值的对v将在同一个文件中结束。
  4. 分别处理每个文件。
  5. 将它们合并在一起。

它本质上是一个带有文件桶的哈希表。此解决方案假定每个值具有大致相同数量的键（否则某些文件可能会变得异常大）。

您还可以实现一个外部排序，它允许您对基本上任何数量的数据进行排序。

于 2013-04-18T20:09:00.710 回答
-1

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

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

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

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

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

于 2013-04-18T10:59:40.057 回答