15

約 1,000 万のキーと値のペアと、約 500,000 の一意のキーを含む 279MB のファイルがあります。キーごとにグループ化されているため (各キーは 1 回だけ書き込む必要があります)、特定のキーのすべての値がまとめられます。

私がやりたいのは、関連付けを転置し、ペアが値でグループ化されたファイルを作成し、特定の値のすべてのキーが一緒に保存されることです。

現在、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 よりもかなり少ないです)。
  2. 私の問題は、アルゴリズム/データ構造に関連している可能性があります。多分私は仕事のために間違ったツールを使用していますか?
  3. 遅延 IO を使用しようとすると、戻ってきて噛まれる可能性があります。

今のところ（1）に傾いていますが、どうしてもわかりません。

4

2 に答える 2

1

データが増える可能性はありますか？はいの場合は、while ファイルをメモリに読み込まず、別の方法でデータを処理しないことをお勧めします。

1 つの簡単な可能性は、そのためにリレーショナル データベースを使用することです。これはかなり簡単です。データをロードし、適切なインデックスを作成して、必要に応じてソートするだけです。データベースがすべての作業を行います。私は間違いなくこれをお勧めします。

もう 1 つのオプションは、独自のファイルベースのメカニズムを作成することです。例えば：

  1. lメモリにロードするのに妥当な制限を選択してください。
  2. n = d `div` lファイルを作成しますd。 はデータの総量です。(これがファイル記述子の制限を超えないことを願っています。各操作の後にファイルを閉じて再度開くこともできますが、これによりプロセスが非常に遅くなります。)
  3. 入力を順番に処理し、各ペア(k,v) をファイル番号に配置しますhash v `mod` l。これにより、同じ値を持つペアがv同じファイルになることが保証されます。
  4. 各ファイルを個別に処理します。
  5. それらを一緒にマージします。

これは基本的に、ファイル バケットを含むハッシュ テーブルです。このソリューションでは、各値にほぼ同じ数のキーがあることを前提としています (そうでない場合、一部のファイルが非常に大きくなる可能性があります)。

基本的に任意の量のデータをソートできる外部ソートを実装することもできます。

于 2013-04-18T20:09:00.710 に答える