Есть ли более эффективный способ согласования больших наборов данных?

Question

Мне было поручено согласовать два больших набора данных (два больших списка транзакций). По сути, я извлекаю соответствующие поля из двух источников данных в два файла одного и того же формата, затем сравниваю файлы, чтобы найти любые записи, которые находятся в A, но не в B, или наоборот, и сообщаю о них. Я написал запись в блоге на , приложив все усилия для достижения этой цели (нажмите, если интересно).

Суть его состоит в том, чтобы загрузить оба набора данных в большую хеш-таблицу, где ключами являются строки, а значения равны +1 каждый раз, когда они появляются в файле A, и -1 каждый раз, когда они появляются в файле B Затем в конце я ищу любые пары ключ / значение, где значение! = 0.

Мой алгоритм кажется достаточно быстрым (10 секунд для файлов размером 2 * 100 МБ), однако он немного загружает память: 280 МБ для сравнения двух наборов файлов по 100 МБ, я хотел бы снизить его до пиковой нагрузки на 100 МБ и, возможно ниже, если два набора данных отсортированы примерно в одинаковом порядке.

Есть идеи?

Кроме того, дайте мне знать, если это слишком открытый конец для SO.

Answer 1

Я сделал нечто подобное только в сценариях на Unix с использованием shell и perl, однако теория может измениться.

Шаг 1, отсортируйте оба файла, чтобы они были в порядке по одним и тем же критериям. Для этого я использовал команду сортировки unix (мне потребовался уникальный флаг, но вам просто нужна какая-то сортировка файлов с эффективным использованием памяти). Это, вероятно, самая сложная часть, чтобы выяснить самостоятельно.

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

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

Сканирование записей должно быть очень эффективным с точки зрения памяти. Это может быть не так быстро, но для меня я смог записать несколько гигабайт данных с несколькими проходами, просматривая разные поля за пару минут.

Answer 2

Одним из вариантов может быть изменение формата ваших данных в памяти. Если ваши данные представляют собой последовательность чисел, хранящихся в виде текста, хранение их в памяти как целых чисел может уменьшить объем памяти.

Другим вариантом может быть использование некоторой внешней программы для сортировки строк - тогда вы можете выполнить простое сканирование двух файлов по порядку в поисках различий.

Вернемся к вашему вопросу: 280 Мб звучат высоко для сравнения пары файлов по 100 Мб, хотя вы загружаете только один в память (меньший) и просто просматриваете другой, верно? Как вы описываете, я не думаю, что вам нужно иметь полное содержимое обоих в памяти сразу.

Answer 3

Единственный способ, которым я могу придумать, - это не загружать все данные в память одновременно. Если вы измените способ обработки так, чтобы он захватывал по кусочкам каждого файла за раз, это уменьшило бы объем памяти, но увеличило бы дисковый ввод-вывод, что, вероятно, привело бы к более длительному времени обработки.

Answer 4

Используя этот метод, вы должны все время хранить содержимое одного из файлов в памяти. С точки зрения памяти было бы более эффективно просто взять половину файла. Сравните его строка за строкой со вторым файлом. Затем перенесите вторую половину в память и сделайте то же самое. Это перекрытие гарантировало бы отсутствие пропущенных записей. И устранит необходимость временного хранения всего файла.