Сравнение двух больших файлов

Question

Мне нужно написать программу, которая будет записывать в файл разницу между двумя файлами. Программа должна пройти через файл 600 МБ с более чем 13.464.448 строк, проверить, возвращает ли grep true в другой файл, а затем записывает результат в другой файл. Я написал быстрый тест с около 1.000.000 записей, и потребовалось более часа, поэтому я предполагаю, что этот подход может занять 9 часов.

Есть ли у вас рекомендации относительно того, как сделать это быстрее? Любой конкретный язык, который я должен использовать? Я планировал сделать это в bash или python.

Большое спасибо.

[EDIT 1]: Извините, когда я говорю разницу между двумя файлами, я не имел в виду разницу. Файл результатов находится в другом формате.

Логика немного так:

Файл А имеет 297.599 линии Файл B имеет более 13 миллионов строк

Я выбираю текущую строку быть чтение из файла A, Grep его на FILE B, и если строка присутствует в файле B, я напишу ее в файл результатов. Кстати, файлы A и B имеют разные форматы. Результат файл будет иметь формат файла А.

[EDIT 2]: меня попросили на работе, чтобы создать решение Баш идеально, так что мы не должны устанавливать питон на всех машинах это должно работать на.

Это моя curent реализация:

#!/bin/bash 

LAST_TTP=`ls -ltr TTP_*.txt | tail -1 | awk '{ print $9 }'` 
LAST_EXP=`ls -ltr *.SSMT | tail -1 | awk '{ print $9 }'` 

while read -r line; do 
    MATCH="$(grep $line $LAST_EXP)" 
    echo "line: $line, match: $MATCH" 

    # if not empty 
    if [ ! -z "$MATCH" ] 
    then 
     echo $MATCH >> result 
    fi 

done < $LAST_TTP 

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

Большое спасибо!

Answer 1

Возможно, вы находитесь в списке вместо набора, что приводит к производительности O (n²). Попробуйте:

with open('b') as b: 
    blines = set(b) 
with open('a') as a: 
    with open('result', 'w') as result: 
    for line in a: 
     if line not in blines: 
     result.write(line) 

Предполагая, равномерно длинные (и не слишком длинные строки), производительность этой реализации в O(|A| + |B|) (амортизируется, из-за Pyton's set being extremely fast). Потребность в памяти составляет O(|B|), но с коэффициентом значительно больше 1.

Если порядок строк на выходе не имеет значения, вы также можете отсортировать оба файла, а затем сравнить их по очереди. Это будет иметь производительность порядка O(|A| log |A| + B log |B|). Потребность в памяти будет равна O(|A|+|B|), или, точнее, |A| + |B|.

Answer 2

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

Это алгоритм O (n log n) в отличие от алгоритма O (n^2), с которым вы начали.

Answer 3

Ваша реализация кажется сделать:

grep --fixed-strings --file=file_B file_A > result_file 

Но как @ phihag лет и @mark ответов Ronsam являются лучшими решениями.

Кроме того, если вы хотите использовать тяжелые пушки, ваше решение является хорошим кандидатом для каркасов с уменьшением размера, таких как hadoop.

Answer 4

Команда соединения также делает то, что вы хотите. join требует, чтобы оба файла были отсортированы спереди. Опция -v выводит строку для каждой неоплачиваемой строки.

Таким образом, вы хотите что-то вроде

присоединиться -v 1 sortedfile1 sortedfile2

(вам нужно будет установить Соединить параметры в соответствии с вашим форматом файла, см справочную страницу дизъюнктивно)

Ниже пример объединяет файлы test1.txt и test2.txt, используя второй или. первое поле для соединения. Предполагая, что файлы были отсортированы заранее, используя команду sort. Опция -v 1 выводит только строки test1.txt не может быть соединена.

 
>cat test1.txt 
a 1 2 
b 2 3 

> cat test2.txt 
1 x 
4 x 

> join -v 1 -1 2 -2 1 test1.txt test2.txt 
2 b 3 

> join -v 1 -1 2 -2 1 -o 1.1 1.2 1.3 test1.txt test2.txt 
b 2 3 

сортировать и вступать в оба дела отлично с большими файлами.

Answer 5

Я бы рассмотрел команду comm. Он должен быть быстрее, чем Grep, потому что он будет работать с отсортированными данными, а Grep всегда будет делать линейный поиск

comm -2 -3 <(sort file1) <(sort file2) 

Answer 6

Вы можете ускорить ваш сценарий немного остановив grep, когда он находит первый матч, если это уместно для вашего необходимо.

Если ваш grep поддерживает его, используйте .

Ваша проблема в том, что вы нерестили grep почти 300 000 раз и каждый раз читаете более 13 000 000 строк.

Остановка grep в первом матче поможет немного, но накладные расходы всех этих execs также являются большим фактором. Реализация в Python устранит эту проблему.

Что касается выбора файлов в вашем скрипте, см. BashFAQ/003 и Parsing ls.

Answer 7

Вы также можете использовать AWK:

awk 'NR==FNR { arrA[$0]; next } $0 in arrA' file_A file_B > result

порядок файлов (... file_A file_B) в командной строке очень важно.