Почему эти дублирующие фильтры на основе хеша работают иначе, чем сортировка |uniq и сортировка -u? - PullRequest
Новая
       56

Почему эти дублирующие фильтры на основе хеша работают иначе, чем сортировка |uniq и сортировка -u?

0 голосов
/ 06 октября 2019

Я столкнулся с сценарием оболочки , который быстро удаляет дубликаты без сортировки строк. В ходе более позднего расследования я также обнаружил, что аналогичный метод предлагает с 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), и строка, кажется, сместилась со строками 12, 13и 14, вставленный между sort 11 и 12.:

$ 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

Вот код sortuniq. Я нашел его в этой коллекции сценариев оболочки (поэтому я называю ее «сценарием оболочки»). 

#!/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");

Только будьте осторожны, это опасно быстро. Я планировал спросить о самой скорости, прежде чем обнаружил эту проблему во время тестов производительности.

1 Ответ

0 голосов
/ 07 октября 2019

* * * uniq coreutils на самом деле не проверяет, являются ли строки уникальными, но если строки имеют другой порядок сортировки в текущей локали.

Мы можем проверить это с помощью сопоставления, которое не является "жестким", мыполучить те же результаты, что и с 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)
あ
い

Код

Мы можем проследить это, начиная с функции different в Util . Он использует xmemcoll , если он определяет, что языковой стандарт hard - не 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
    { 
      //
    }

Интересно, что байт \0 не является проблемой для memcoll. В то время как C strcoll останавливается на \0, функция memcoll сбрасывает байты с начала строки один за другим, чтобы обойти это - см. Строки 39 до 55 .

...