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

Question

这里提出了类似的问题，但他们没有解决为什么sort和awk之间存在速度差异。

我首先在Unix Stackexchange上提出了这个问题，但既然他们告诉我这对于 Stackoverflow 来说是一个很好的问题，我会将其发布在这里。

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

awk --> O(n) ？
排序 --> O(n log n) ？

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

列表 1 = 7 Mb
列表 2 = 690 Mb

测试命令

sort -u input.txt -o output.txt 

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

结果 AWK：
List1
real 0m1.643s
user 0m1.565s
sys 0m0.062s

List2
真实2m6.918s
用户2m4.499s
系统0m1.345s

结果排序：
List1
real 0m0.724s
user 0m0.666s
sys 0m0.048s

List2
真实 1m27.254s
用户 1m25.013s
系统 0m1.251s

我一遍又一遍地进行这些测试并发现了一致的结果。也就是说，该排序速度要快得多。有人可以解释为什么以及是否有更快的方法吗？

************ 更新 ************
可能会影响我的结果的事情是

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

Answer 1

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