大型单词列表中删除重复项的最快方法是什么？

Question

一个类似的问题在此处被提出，但他们没有解释为什么sort和awk之间会有速度差异。

我首先在Unix Stackexchange上提出了这个问题，但由于他们告诉我这个问题适合在Stackoverflow上发布，所以我将在这里发布它。

我需要对一个大型单词列表进行去重。我尝试了几个命令并做了一些研究这里和这里，他们解释说去重单词列表最快的方法似乎是使用awk，因为awk不排序列表。它使用哈希查找来跟踪项并删除重复项。由于AWK使用哈希查找，他们认为其大O像下面这样

awk --> O(n) ?
sort --> O(n log n) ?

然而，我发现这并不正确。这是我的测试结果。我使用这个Python脚本生成了两个随机单词列表。

List1 = 7 Mb List2 = 690 Mb

测试命令

sort -u input.txt -o output.txt 

awk '!x[$0]++' input.txt > output.txt

AWK结果:
List1
实际时间 0m1.643秒
用户时间 0m1.565秒
系统时间 0m0.062秒

List2
实际时间 2m6.918秒
用户时间 2m4.499秒
系统时间 0m1.345秒

SORT结果:
List1
实际时间 0m0.724秒
用户时间 0m0.666秒
系统时间 0m0.048秒

List2
实际时间 1m27.254秒
用户时间 1m25.013秒
系统时间 0m1.251秒

我一遍又一遍地进行这些测试，发现结果非常一致。也就是说，排序比AWK快得多。有人能解释为什么吗？如果有更快的方法，请说明。

************ 更新 ***********
可能影响结果的因素：

1. 缓存：通过改变测试执行的顺序来排除此可能性
2. 大O符号的常数因子。由于单词列表的大小（600MB），我认为它们应该变得不相关了。
3. 算法的错误实现：我还没有检查过awk和sort的源代码，这仍然是一个可能性

- Karl

---

在每种情况下，n是什么？如果您尝试许多不同的n值，您是否会看到awk的运行时间线性增加，还是sort的增加为n lg n？ - chepner

请在您的问题中添加 awk 代码。 - Cyrus

@chepner，比较这两个单词列表，它们似乎都表现得非常线性。 - Karl

你的测试数据有很多重复项（预计99%），使用sort -u比最坏情况下的处理更高效。使用来自500,000个不同值的1,000,000个随机值进行测试（而不是来自1,000,000个不同值的100,000,000个随机值），awk可以快近14倍。 - chepner

这个问题已经被问了很多次。这里提供一些额外的策略：https://dev59.com/1Izda4cB1Zd3GeqPhxje - ghoti

Answer 1

您的样本输入有很多重复值；在100,000,000的样本大小中，您只有1,000,000个不同的值，因此您只期望有1%的值是唯一的。我不知道sort -u的确切工作方式，但可以想象它是一种合并排序，在每次合并过程中过滤唯一值。因此，有效输入大小将比100,000,000小得多。使用仅从500,000个不同值中选择的1,000,000个值（因此预计50％而不是1％是唯一的）重新运行您的命令会产生以下结果：

% time awk '!x[$0]++' randomwordlist.txt > /dev/null
awk ...  1.32s user 0.02s system 99% cpu 1.338 total
% time sort -u randomwordlist.txt -o /dev/null
sort ...  14.25s user 0.04s system 99% cpu 14.304 total

- chepner

---

有趣的一点，我已经复制了您的实验，使用了1000万个样本大小和500万个不同的值。但是排序仍然比awk快30％--> 排序= 0m10.258s - awk = 0m16.966s - Karl

这可能与操作系统和硬件有关吗？我使用的是2015年的Macbook Pro.. 2.7 GHz英特尔Core i5。 - Karl

抱歉，我的意思是 5,000,000。 - Karl

你可能已经达到了内存限制，导致产生了与交换相关的开销。 - chepner

我还尝试了另一个包含50％唯一值的大型单词列表..结果相同。所以在我看来，这似乎是一个实现问题.. - Karl

只是为了澄清，我使用了100万-50万个单词复制了您的测试，并尝试了1000万-500万个单词。在两种情况下，排序速度更快，因此我不认为这与交换有关。 - Karl

Answer 2

1. 大O符号只告诉你存在某个N，使得O(N)比O(N*log N)更快。实际操作次数包括常数因子和添加的项，因此实际上的数字是
   O(N) ~ k1 * N + c1 和
   O(N * log N) ~ k2 * N * log(N) + c2
   哪一个更快取决于k和c的值。
2. 一些输入/算法组合会导致非常小的k和c。
3. 任何一个程序都可能没有使用最优算法。
4. 缓存效应？如果你总是在测试2之前运行测试1，则第二个测试可能会使用已经缓存的数据，而第一个测试总是必须从头开始加载。正确消除/确定缓存效应是一门艺术。
5. 我没有想到的其他事情，其他人很快就会指出来 :-)

- Jens

---

我认为由于单词列表的大小差异很大，k和c应该变得不相关...(我也用了一个20 Gb的单词列表进行了测试)。在这个实验中，我排除了执行顺序改变的缓存效应。 - Karl