Сбой памяти при переносе [(K, [V])] в [(V, [K])]

У меня есть файл размером 279 МБ, содержащий ~ 10 миллионов пар ключ/значение, с ~ 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)

Я мог бы подумать о нескольких вещах, которые я делаю неправильно:

• 2MB кажется немного низким (значительно меньше, чем 2 ГБ оперативной памяти, установленной моей машиной), поэтому, возможно, мне нужно сказать GHC, что это нормально, чтобы использовать больше?
• Мои проблемы могут быть связаны с алгоритмической структурой/структурой данных. Может быть, я использую неправильные инструменты для работы?
• Моя попытка использовать ленивый IO может вернуться, чтобы укусить меня.

Сейчас я склоняюсь к (1), но я не уверен ни в коем случае.

Ответы

Ответ 1

Возможно ли, что данные будут увеличиваться? Если да, то я предлагаю не читать файл while в памяти и обрабатывать данные по-другому.

Одна простая возможность - использовать для этого реляционную базу данных. Это довольно просто - просто загрузите свои данные, создайте правильный индекс и отсортируйте его по мере необходимости. База данных сделает всю работу за вас. Я определенно рекомендую это.

---

Другой вариант - создать собственный файловый механизм. Например:

• Выберите некоторый предел l, который разумно загрузить в память.
• Создайте n = d `div` l файлы, где d - общая сумма ваших данных. (Надеюсь, это не будет превышать лимит дескриптора файла. Вы также можете закрыть и снова открыть файлы после каждой операции, но это сделает процесс очень медленным.)
• Обработать вход последовательно и поместить каждую пару (k,v) в номер файла hash v `mod` l. Это гарантирует, что пары с одинаковым значением v попадут в один и тот же файл.
• Обработать каждый файл отдельно.
• Объедините их вместе.

Это по существу хэш-таблица с файловыми ковшиками. Это решение предполагает, что каждое значение имеет примерно одинаковое количество ключей (в противном случае некоторые файлы могут быть исключительно большими). ​​

---

Вы также можете реализовать внешний вид который позволит вам сортировать в основном любой объем данных.

Ответ 2

Чтобы разрешить файлы, размер которых превышает доступную память, рекомендуется обрабатывать их в кусках размером с укусом за раз.

Вот твердый алгоритм для копирования файла A в новый файл B:

• Создайте файл B и заблокируйте его на своем компьютере.
• Начало цикла
  • Если в файле A нет следующей строки, то завершите цикл
  • Читайте в следующей строке файла A
  • Применить обработку к строке
  • Убедитесь, что файл B содержит строку уже
  • Если файл B не содержит строку уже, добавьте строку в файл B
  • Перейти к началу цикла
• Разблокировать файл B

Также полезно сделать копию файла A во временную папку и заблокировать ее во время работы с ней, чтобы другим людям в сети не мешали изменять оригинал, но у вас есть моментальный снимок файла как это было в момент начала процедуры.

Я намерен пересмотреть этот ответ в будущем и добавить код.