Grep вызывает зависание всей системы при сравнении двух файлов

Question

Я хотел сравнить два файла и проверить, существует ли каждая строка в file1 в file2 . Моя первая попытка: grep -v -f file2 file1 . Это приводило к множеству синтаксических ошибок (но ничего не зависало). Я быстро понял, что это потому, что мне нужно использовать -F как описано здесь . Поэтому я запустил grep -Fvf file2 file2 и через несколько секунд вся моя система зависла на несколько минут, пока xorg полностью не рухнул.

Я смог сфотографировать застывший экран:

И как только я наконец смог войти в tty2, меня встретили с этим:

Вопросы:

1. Была ли причина зависания системы просто в том, что ей не хватило оперативной памяти, или есть еще?
2. Почему grep использует ~ 14 ГБ ОЗУ (и хочет больше) для сравнения двух файлов размером 250 МБ?
3. Я мог бы использовать инструменты для ограничения оперативной памяти, которые может использовать grep, но AFAIK - все они просто убьют процесс, как только он достигнет x ГБ ОЗУ, так что это мне не поможет. Что делать в такой ситуации? Давайте предположим, что мы должны использовать grep.

Изменить: я уже нашел обходной путь без grep. Мне действительно любопытно, почему и как это все еще может произойти. +14 ГБ ОЗУ для двух 250 МБ файлов мне просто кажется странным. Я не ищу альтернативу тому, как я могу сравнить свои файлы с этим вопросом.

Answer 1

1. Причина была определенно исчерпана памятью.

2. Поскольку вы не "сравниваете два файла", вы используете один файл размером 250 МБ в качестве источника шаблонов для grep. Grep компилирует эти шаблоны в вариант детерминированного конечного автомата, и представление этих DFA занимает память. Если у вас много шаблонов (например, 250 МБ шаблонов), это занимает много места, потому что преобразование недетерминированного конечного автомата, который соответствует многим шаблонам, в DFA может вызвать экспоненциальный взрыв.

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

Сложность имеет значение, поэтому вы узнаете об О-нотации и обо всех этих причудливых вещах.

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

Вы сказали, что не хотите знать альтернативу, но поскольку в ней используется менее известный инструмент, я все равно скажу вам:

Если вопрос заключается в том, «существует ли каждая строка файла1 также в файле2, независимо от порядка», вам нужно отсортировать оба файла, а затем использовать comm , которая ожидает отсортированные файлы, и выдает (1) строки в файле1, но не в file2, (2) строки в file2, но не в file1 и (3) строки в обоих файлах, для вашего удобства.