Bash，Linux：两个文本文件之间的差异

Question

我有两个文件A-nodes_to_delete和B-nodes_to_keep，每个文件都有许多具有数字ID的行。

我想要获取在nodes_to_delete中但不在nodes_to_keep中的数字ID列表，即A\B

在PostgreSQL数据库内完成这个任务速度太慢了。有没有一种巧妙的方法可以使用Linux CLI工具在bash中解决这个问题？

更新: 这似乎是一个Python任务，但是文件非常大。我已经使用uniq、sort和一些集合论技巧解决了类似的问题。这比数据库等价物快了两三个数量级。

- Adam Matan

---

我很好奇会得到什么答案。Bash更偏向于segphault，我认为它更适合系统管理员。如果你说“用Python”、“用PHP”或者其他什么语言的话，你的机会会更大 :) - extraneon

我看到标题时已经准备好抨击UI不一致和自以为是的帮助论坛了。但当我读到实际问题时，感到有些失望。:( - aehiilrs

Answer 1

comm命令可以实现这一功能。

- msw

---

如果文件还没有排序，请先进行“排序”。 - extraneon

+1 Enlightened，这是一个非常棒的工具，我感到很愚蠢没有早点知道它。谢谢！ - Adam Matan

不会在这里引发争端，但是您的评论只是粗鲁无礼。 - Adam Matan

讽刺的是，“comm”这一概念可以追溯到一个你能够把/bin和/usr/bin的全部内容记在脑中的时代，那个时候还没有Perl、Python和MySQL等这些花哨的工具。回到那个简单的V7时代，你必须利用所有的工具或（哇！）亲手编写ed(1)命令。当然，我们很喜欢这样做! ;) 如果我晚些时间开始学习计算机，我可能就永远不知道“comm”的存在了。 - msw

@Adam Matan：抱歉，无礼绝对不是我的意图。事实上，我发布的命令是了解系统的好方法，我过去也经常这样做来启迪自己。否则，例如join(1)我就不会知道了。 - just somebody

Answer 2

文件 $1 和 $2 之间的集合操作

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

set_intersection () {
   sort $1 $2 | uniq -d
}

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

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

• uniq 打印公共行
• uniq -u (--unique) 仅打印未重复的行
• uniq -d (--repeated) 仅打印重复的行

注意：这些假设文件$1和$2中不存在重复行。如果存在，请先使用$(sort $1 | uniq)预处理它们以消除重复行。

- slinkp

---

我认为这比被接受的答案更好...在所有环境中并不都有comm。 - danwyand

那是对称差异（symmetric difference），而不是普通的集合差异（set difference）。 - Tgr

@Tgr 我的答案会给出对称差异，如果每个文件只读取一次，但第二个文件被读取了两次，因此输出仅为第一个文件中唯一的行。 - slinkp

set_difference 和 set_symmetric_difference 并非总是能正确工作——若第一个输入文件中的某些行不是唯一的，则它们将删除那些独特的行。 - Leon

@Leon，怎么可能有些东西是独特的但又不是独特的，我不明白。 - neboduus

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 列：

$ comm FILE1 FILE2
lines_unique_to_FILE1
    lines_unique_to_FILE2
        lines_which_appear_in_both

使用我们上面的示例文件，运行没有参数的comm命令。注意三列。

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

抑制列输出

使用 -N 抑制第 1、2 或 3 列的输出；请注意，当列被隐藏时，空格会缩小。

$ 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：文件 1 没有排序

- activedecay

---

如果包括OP的具体问题答案（在deleteNodes中输出不在keepNodes中的行），则正确的示例将得到+1分，但如果强调正确解决方案，则会更好：comm -1 -3 <(sort keepNodes) <(sort deleteNodes)。 - John B

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

- John B

---

这个答案如果能解释一下它在做什么会更有帮助。 - neuralmer

Answer 5

也许你需要在PostgreSQL中找到更好的方法，我敢打赌使用平面文件不可能找到更快的方法。你应该能够执行一个简单的内连接，假设两个ID列都被索引，那么速度应该非常快。

- Dark Castle

---

你的技术上是正确的，并且 explain 也支持你的说法，但是它对于非常大的（约数千万）表格根本不起作用。 - Adam Matan

是的，它会受到内存的限制，不像排序通信那样，但我认为如果你有两个只有一个int id字段的表，你可以轻松地处理数千万条记录。 - Dark Castle

理论上是对的，但出于某种原因它根本不起作用。 - Adam Matan

Answer 6

另一种可携带的解决方案，适用于多集合的情况，即允许元素有多个实例的集合，是使用在单独文件中的模式匹配grep：

grep -Fvx -f B A

参数：

• -f：包含一个模式列表的文件，每行一个
• -F：将模式视为字符串，而非正则表达式
• -x：匹配 A-nodes_to_delete 中的整行
• -v：反转匹配（如果不匹配，则匹配）

如果 B 中的模式未匹配到 A 中的任何行，则该命令输出该行，否则不输出任何内容。

这种解决方案的一个好处是，它可以处理多列文件（对于 A），而 comm 和 uniq -u 解决方案需要单列文件。

- Alenvers

Answer 7

所以，这与其他答案略有不同。我不能说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

- YenForYang