bash, Linux: установить разницу между двумя текстовыми файлами

Question

У меня есть два файла A - nodes_to_delete и B - nodes_to_keep. Каждый файл имеет много строк с числовыми идентификаторами.

Я хочу получить список числовых идентификаторов, которые находятся в nodes_to_delete, но НЕ в nodes_to_keep, например. альтернативный текст http://mathworld.wolfram.com/images/equations/SetDifference/Inline1.gif.

Делать это в базе данных PostgreSQL неоправданно медленно. Любой изящный способ сделать это в bash с использованием инструментов Linux CLI?

ОБНОВЛЕНИЕ: Казалось бы, работа Pythonic, но файлы действительно очень большие. Я решил некоторые похожие проблемы, используя uniq, sort и некоторые методы теории множеств. Это было примерно на два-три порядка быстрее, чем эквиваленты базы данных.

Answer 1

Команда comm делает это.

Answer 2

Кто-то показал мне, как это сделать пару месяцев назад, но потом я не мог найти это некоторое время ... и, глядя, я наткнулся на ваш вопрос. Вот оно:

set_union () {
   sort $1 $2 | uniq
}

set_difference () {
   sort $1 $2 $2 | uniq -u
}

set_symmetric_difference() {
   sort $1 $2 | uniq -u
}

Answer 3

Использовать comm - строка за строкой будет сравнивать два отсортированных файла.

Краткий ответ на ваш вопрос

Эта команда возвращает строки, уникальные для deleteNodes, но не строки в keepNodes.

comm -1 -3 <(sort keepNodes) <(sort deleteNodes)

---

Пример настройки

Давайте создадим файлы с именами keepNodes и deleteNodes и используем их в качестве несортированного ввода для команды comm.

$ cat > keepNodes <(echo bob; echo amber;)
$ cat > deleteNodes <(echo bob; echo ann;)

По умолчанию при запуске comm без аргументов выводятся 3 столбца с таким макетом:

lines_unique_to_FILE1
    lines_unique_to_FILE2
        lines_which_appear_in_both

Используя наши примеры файлов выше, запустите comm без аргументов. Обратите внимание на три столбца.

$ comm <(sort keepNodes) <(sort deleteNodes)
amber
    ann
        bob

Подавление вывода столбца

Подавить столбец 1, 2 или 3 с помощью -N; обратите внимание, что когда столбец скрыт, пробел уменьшается.

$ comm -1 <(sort keepNodes) <(sort deleteNodes)
ann
    bob
$ comm -2 <(sort keepNodes) <(sort deleteNodes)
amber
    bob
$ comm -3 <(sort keepNodes) <(sort deleteNodes)
amber
    ann
$ comm -1 -3 <(sort keepNodes) <(sort deleteNodes)
ann
$ comm -2 -3 <(sort keepNodes) <(sort deleteNodes)
amber
$ comm -1 -2 <(sort keepNodes) <(sort deleteNodes)
bob

Сортировка важна!

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

comm: file 1 is not in sorted order

Answer 4

comm был специально разработан для этого вида использования, но для него требуется отсортированный ввод.

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

awk 'NR == FNR { a[$0]; next } !($0 in a)' nodes_to_keep nodes_to_delete

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

awk -v r='^[0-9]+$' 'NR == FNR && $0 ~ r {
    a[$0]
    next
} $0 ~ r && !($0 in a)' nodes_to_keep nodes_to_delete

Answer 5

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

Answer 6

Итак, это немного отличается от других ответов. Я не могу сказать, что компилятор C ++ - это в точности «инструмент Linux CLI», но запуск g++ -O3 -march=native -o set_diff main.cpp (с приведенным ниже кодом в main.cpp может помочь):

#include<algorithm>
#include<iostream>
#include<iterator>
#include<fstream>
#include<string>
#include<unordered_set>

using namespace std;

int main(int argc, char** argv) {
    ifstream keep_file(argv[1]), del_file(argv[2]);
    unordered_multiset<string> init_lines{istream_iterator<string>(keep_file), istream_iterator<string>()};
    string line;
    while (getline(del_file, line)) {
        init_lines.erase(line);
    }
    copy(init_lines.begin(),init_lines.end(), ostream_iterator<string>(cout, "\n"));
}

Чтобы использовать, просто запустите set_diff B A ( не A B, поскольку B равно nodes_to_keep), и полученная разница будет напечатана на стандартный вывод.

Обратите внимание, что я отказался от нескольких лучших практик C ++, чтобы сделать код проще.

Можно выполнить много дополнительных оптимизаций скорости (за счет увеличения объема памяти). mmap также был бы особенно полезен для больших наборов данных, но это сделало бы код намного более сложным.

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

<Ч />

Что-то проще скопировать и вставить в bash (т.е. пропустить создание main.cpp):

g++ -O3 -march=native -xc++ -o set_diff - <<EOF
#include<algorithm>
#include<iostream>
#include<iterator>
#include<fstream>
#include<string>
#include<unordered_set>

using namespace std;

int main(int argc, char** argv) {
        ifstream keep_file(argv[1]), del_file(argv[2]);
        unordered_multiset<string> init_lines{istream_iterator<string>(keep_file), istream_iterator<string>()};
        string line;
        while (getline(del_file, line)) {
                init_lines.erase(line);
        }
        copy(init_lines.begin(),init_lines.end(), ostream_iterator<string>(cout, "\n"));
}
EOF