为什么这些基于哈希的重复过滤器的工作方式与排序 | uniq 和 sort -u 不同?

Question

我遇到了一个shell脚本，它可以快速消除重复项而无需对行进行排序。在后来的调查中，我还发现 awk 和 perl 也提出了类似的方法。

但是，我注意到这些方法的工作方式与通常的sort -u和sort | uniq略有不同。

$ dd if=/dev/urandom of=sortable bs=1M count=100
100+0 records in
100+0 records out
104857600 bytes (105 MB, 100 MiB) copied, 0.10448 s, 1.0 GB/s
$ wc -l sortable
409650 sortable
$ cat sortable | sort -u | wc -l
404983
$ cat sortable | sort | uniq | wc -l
404983
$ cat sortable | ./sortuniq | wc -l
406650
$ cat sortable | awk '!x[$0]++' | wc -l
406651
$ cat sortable | perl -ne 'print if ! $x{$_}++' | wc -l     
406650

为什么会有差异？我尝试设置一个带有空行、0行、用空格填充的行的小测试文件。我找到了所有的方法都可以做同样的事情。

我能够使用cmp发现awk行数更大，因为它在末尾添加了换行符。但我无法理解其他案件。我对数组唯一文件进行了排序，发现在我的情况下，第一个区别在于第 12 行。我从两个文件(awk '!x[$0]++;' file | sort和sort -u file(中打印了一些行，并且该行似乎已经移动，在sort的11和12之间插入了第12,13和14行。

$ sed -n '11p' sorted | hexdump
0000000 9300 000a
0000003
$ sed -n '12p' sorted | hexdump
0000000 b700 ef00 d062 d0b4 6478 1de1 a9e8 c6fd
0000010 4e05 e385 e678 7cbb 5f46 ce85 3d26 1875
0000020 56e4 baf1 b34a 0006 1dda 06cc efd6 9627
0000030 edbe 3bf7 a2c7 8b3f 1fe0 790e 9b1b 237e
0000040 42ac 3f5b 827b 535d 2e59 4001 3ce1 bd7d
0000050 7712 21c9 e025 751d c591 84ce b809 4038
0000060 372a 07d4 220f 59cc 3e2f 7ac3 88bb 23b1
0000070 fe37 1a36 31f8 fde6 7368 bd89 631b f3a9
0000080 8467 b413 9a28 000a
0000087
$ sed -n '13p' sorted | hexdump
0000000 f800 cb00 f473 583d e2c5 2a8c 7c81 cbcd
0000010 3af1 9cf7 4992 2aab 90ed b018 5f4f b03b
0000020 40f1 8731 17fa d74a ba7e db12 6f8d 5a37
0000030 dd97 837e 4eb2 05d4 7d28 722e 8e49 7ffa
0000040 176d c54b a0a0 a63a 26a2 db5e 4ea8 5f44
0000050 33fe 26a7 40bb 98b0 6660 62bd b56a 949e
0000060 eaa7 9dd1 9427 5fab 7840 f509 4fbf 06ea
0000070 d389 15c8 fbf0 3ea6 4a53 909f 1c75 2acb
0000080 7074 d41e 40f2 14b7 b8aa 04e2 00bf 7b6e
0000090 ff3f 4822 c3e6 b3e9 1708 6a93 55fd a5f6
00000a0 ad3b 9b7d 7c2e faa1 4d25 2f32 c434 4a8c
00000b0 a42e 6d8c 138f 030b accd 086b baa2 6f92
00000c0 6256 e959 b19a c371 f7bf 7c63 773c 9e4d
00000d0 bb2b f555 bc05 9454 29a6 f221 e088 c259
00000e0 9bed ab59 0591 2d30 9162 1dd1 91ea c928
00000f0 cb8f 60bc 6f25 62b2 a424 2f97 0058 0d3e
0000100 95f2 7cf4 d53b 6208 6cba c013 3505 9704
0000110 5a1f f63f 9bea 7d45 2dd6 8084 d078 d8b1
0000120 5fdc fb57 8cf8 6ae8 b791 23bd f2f5 70eb
0000130 9094 407a 228d 5818 a0fa d480 53f7 eb8e
0000140 f07b b288 e39b 60c7 a581 8481 97da 68d9
0000150 7240 2fb1 6ec6 fc57 78cd 4988 90a2 52d3
0000160 2fb6 3efd c140 d890 c2ff 2c0c ad02 47db
0000170 106e da82 dd0f 3f7f 49c1 2d2c dc0f 4a1e
0000180 01d3 95de 000a
0000185
$ sed -n '14p' sorted | hexdump
0000000 c400 0ac8
0000004

$ sed -n '11p' awksorted | hexdump
0000000 9300 000a
0000003
$ sed -n '12p' awksorted | hexdump
0000000 a100 000a
0000003
$ sed -n '13p' awksorted | hexdump
0000000 ff00 000a
0000003
$ sed -n '14p' awksorted | hexdump
0000000 d200 000a
0000003
$ sed -n '15p' awksorted | hexdump
0000000 b700 ef00 d062 d0b4 6478 1de1 a9e8 c6fd
0000010 4e05 e385 e678 7cbb 5f46 ce85 3d26 1875
0000020 56e4 baf1 b34a 0006 1dda 06cc efd6 9627
0000030 edbe 3bf7 a2c7 8b3f 1fe0 790e 9b1b 237e
0000040 42ac 3f5b 827b 535d 2e59 4001 3ce1 bd7d
0000050 7712 21c9 e025 751d c591 84ce b809 4038
0000060 372a 07d4 220f 59cc 3e2f 7ac3 88bb 23b1
0000070 fe37 1a36 31f8 fde6 7368 bd89 631b f3a9
0000080 8467 b413 9a28 000a
0000087
$ sed -n '16p' awksorted | hexdump
0000000 f800 cb00 f473 583d e2c5 2a8c 7c81 cbcd
0000010 3af1 9cf7 4992 2aab 90ed b018 5f4f b03b
0000020 40f1 8731 17fa d74a ba7e db12 6f8d 5a37
0000030 dd97 837e 4eb2 05d4 7d28 722e 8e49 7ffa
0000040 176d c54b a0a0 a63a 26a2 db5e 4ea8 5f44
0000050 33fe 26a7 40bb 98b0 6660 62bd b56a 949e
0000060 eaa7 9dd1 9427 5fab 7840 f509 4fbf 06ea
0000070 d389 15c8 fbf0 3ea6 4a53 909f 1c75 2acb
0000080 7074 d41e 40f2 14b7 b8aa 04e2 00bf 7b6e
0000090 ff3f 4822 c3e6 b3e9 1708 6a93 55fd a5f6
00000a0 ad3b 9b7d 7c2e faa1 4d25 2f32 c434 4a8c
00000b0 a42e 6d8c 138f 030b accd 086b baa2 6f92
00000c0 6256 e959 b19a c371 f7bf 7c63 773c 9e4d
00000d0 bb2b f555 bc05 9454 29a6 f221 e088 c259
00000e0 9bed ab59 0591 2d30 9162 1dd1 91ea c928
00000f0 cb8f 60bc 6f25 62b2 a424 2f97 0058 0d3e
0000100 95f2 7cf4 d53b 6208 6cba c013 3505 9704
0000110 5a1f f63f 9bea 7d45 2dd6 8084 d078 d8b1
0000120 5fdc fb57 8cf8 6ae8 b791 23bd f2f5 70eb
0000130 9094 407a 228d 5818 a0fa d480 53f7 eb8e
0000140 f07b b288 e39b 60c7 a581 8481 97da 68d9
0000150 7240 2fb1 6ec6 fc57 78cd 4988 90a2 52d3
0000160 2fb6 3efd c140 d890 c2ff 2c0c ad02 47db
0000170 106e da82 dd0f 3f7f 49c1 2d2c dc0f 4a1e
0000180 01d3 95de 000a
0000185
$ sed -n '17p' awksorted | hexdump
0000000 c400 0ac8
0000004

索图尼克

这是sortuniq代码。我在这个 shell 脚本集合中找到了它(这就是为什么我将其称为"shell 脚本"(。

#!/usr/bin/php
<?php
$in = fopen('php://stdin',"r");
$d = array();
while($z = fgets($in))
@$d[$z]++;
if($argc > 1 and ($argv[1] == 'c' or $argv[1] == '-c'))
foreach($d as $a => $b)
echo ("$b $a");
else
foreach($d as $a => $b)
echo ("$a");

只是要小心，这是危险的快。在性能测试期间发现此问题之前，我打算询问速度本身。

Answer 1

coreutils 的uniq实际上并不检查这些行是否唯一，而是检查这些行在当前语言环境中是否具有不同的排序顺序。

我们可以检查使用不"难"的排序规则，我们得到的结果与awk.这有效地禁用了排序规则，只比较字节：

$ ( LC_COLLATE=POSIX sort -u sortable | wc -l)
406651
$ ( LC_COLLATE=C sort -u sortable | wc -l)
406651

例

了解原因后，使用有效的文本文件重现此行为很简单。采用日语、阿拉伯语或任何字符，并使用这些字符没有定义排序顺序的区域设置。

$ echo 'あ' > utf8file
$ echo 'い' >> utf8file
$ file utf8file
utf8file: UTF-8 Unicode text
$ sort -u utf8file
あ
$ (LC_COLLATE=en_US.UTF-8 sort -u utf8file)
あ
$ (LC_COLLATE=C sort -u utf8file)
あ
い
$ (LC_COLLATE=POSIX sort -u utf8file)
あ
い
$ (LC_COLLATE=C.UTF-8 sort -u utf8file)
あ
い

代码

我们可以从 util 中的different函数开始跟踪这一点。如果它确定语言环境是硬的，它使用 xmemcoll - 而不是 C 或 POSIX。xmemcoll似乎是一个添加错误报告的 memcoll 包装器。memcoll源解释说，字节不同的字符串将使用strcoll重新检查相等性：

/* strcoll is slow on many platforms, so check for the common case
where the arguments are bytewise equal.  Otherwise, walk through
the buffers using strcoll on each substring.  */
if (s1len == s2len && memcmp (s1, s2, s1len) == 0)
{
errno = 0;
diff = 0;
}
else
{ 
//
}

有趣的是，字节对memcoll来说不是问题。虽然 Cstrcoll将在处停止，memcoll函数会逐个删除字符串开头的字节来解决此问题 - 参见第 39 行到 55 行。