Алгоритм объединения-объединения больших файлов - PullRequest
Новая
       25

Алгоритм объединения-объединения больших файлов

1 голос
/ 11 августа 2011

Предположим, у меня есть четыре больших файла (слишком больших, чтобы помещать их в память даже по отдельности), в которых есть информация, которую мне нужно обработать. Я намерен создать один объект уровня приложения (запись) из каждой строки в файле # 1. Файлы 2-4 имеют дополнительные фрагменты информации, необходимые для создания этого объекта записи. Например, структура файла может быть следующей:

Файл № 1:
ключ, описание

Файл № 2:
ключ, метаданные, размер

Файл № 3:
Происхождение, скорость, ключ

Файл № 4:
ключ, startDate, endDate

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

Ответы [ 2 ]

2 голосов
/ 11 августа 2011

Использование базы данных хранилища значений ключей

Базы данных - лучшие инструменты для обработки наборов данных, превышающих объем вашей памяти.Поместите свои файлы в хранилище значений ключей (NoSQL DB, как CouchDB или Cassandra, будет отличным вариантом).Решите вашу проблему, используя ключевые запросы.

Использование сортировки и двоичного поиска

Если вы не можете использовать базы данных, отсортируйте файл по ключевому столбцу (это легко сделать с помощью GNU sort ).Чем вы можете получить доступ к своим файлам в nlogn времени, используя ключ.Переберите самый большой файл и обработайте каждую запись, используя обращения к другим файлам.Таким образом, чтение с вашего диска может быть кэшировано.

1 голос
/ 11 августа 2011

Вы можете выгрузить все в базу данных (на самом деле, просто SQL), а затем удалить «неполные» записи.

Чтобы сделать это для файлов, вы можете сделать это:

  • Сортировка всех файлов по ключу id
  • открыть все отсортированные файлы
  • читать первую запись из каждого файла
  • если у вас нет 4 «совпадающих» записей, откажитесь от записи с наименьшим идентификатором, пока не сделаете
  • объединить 4 "совпадающие" записи
  • промыть и повторить
...