Самый быстрый инструмент `uniq` в Linux

Question

У меня есть большой текстовый файл (1,5 Гб),

Я хочу узнать, какой самый быстрый и надежный инструмент в Linux.

Я обычно использую:

awk '!x[$0]++' file.txt

Но когда я использую htopкоманду, я вижу, что использование памяти увеличивается.

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

uniq?
sort?
sed?
awk?

Почему?

Answer 1

Давайте рассмотрим, как работает каждое решение.

• uniqДля этого требуется, чтобы файл уже был отсортирован. Если нет, то сначала нужно пропустить его через конвейер sort, то есть sortпрочитать весь файл в память, переупорядочить его ( O(n log n)), а затем записать в конвейер. Работа uniqочень дешева, так как ему нужно только сравнить соседние строки своего ввода.

• sort -uЭто объединяет работу sort | uniq. Это должно собрать все уникальные входы в память, как awkэто делает скрипт, но затем это также тратит время на их сортировку перед созданием вывода. Это O(n log n), хотя в данном случае nэто количество уникальных элементов, а не все входы. Так что это лучше, чем конвейер.

• sedЯ не уверен, почему вы это перечислили, так как я вообще не могу придумать хорошего способа сделать это sed. Может быть, если вы сначала отсортируете это и передадите в sedскрипт, то сможете сравнить соседние строки. Так что sedпросто сделаете то, что uniqделаете, и, uniqвероятно, сделаете это максимально эффективно.

• awkЭто, вероятно, лучший вариант, поскольку он выполняет только минимально необходимое количество работы. При считывании каждой строки он выполняет эффективный поиск хеша, чтобы узнать, находится ли строка уже в его памяти, и сохраняет только уникальные строки как ключи хеша и счетчик как значение. (Если строка ранее не присутствовала, условие будет истинным, поэтому строка будет напечатана. В противном случае — нет.) Это использует O(n)время и O(uniq n)память.

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

Answer 2

Я просто хотел отметить, что gnu uniqвыглядит ужасно медленно, даже на отсортированном списке.

Я только что попытался получить список префиксов каталогов из списка отсортированных имен файлов:

$ pv all_files | cut -d '/' -f 1,2,3,4 | uniq > all_prefixes

36.7GiB 0:07:41 [81.4MiB/s]

$ pv all_files | cut -d '/' -f 1,2,3,4 | sort -u > all_prefixes2

36.7GiB 0:03:14 [ 193MiB/s]

$ pv all_files  | cut -d '/' -f 1,2,3,4 | awk '!x[$0]++' > all_prefixes3                                        
36.7GiB 0:02:18 [ 270MiB/s] 

sort -u кажется в два раза быстрее uniq, и это с сортировкой чтения из stdin и записи в stdout, так что я пока не вижу, чтобы она делала какую-либо распараллеливание. Я понятия не имею, почему uniq должен быть настолько медленнее sort, ведь ему не нужно сортировать список...

Результат этой команды очень мал (много дубликатов), всего 264 КБ, и сортировка завершается мгновенно после завершения pv.

Те же скорости сохраняются, если поменять порядок команд местами; мой поток здесь ограничен временем процессора, а не доступом к диску и кэшами (у меня всего 8 ГБ ОЗУ, а раздел подкачки не используется).

Я запускаю это на машине Fedora 31 с gnu coreutils sort и uniq и gnu awk; локаль установлена ​​на en_US.UTF-8

ОБНОВЛЯТЬПоскольку это меня очень заинтриговало, я провел еще несколько тестов. Давайте уберем вырезанные части и убедимся, что файл хорошо отсортирован.

cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test

Это займет 8,4 минуты. Тест теперь весит 7,9 ГБ.

Давайте запустим эти инструменты в файле, а не в конвейере. Это позволит этим инструментам выполнить дополнительную оптимизацию, например, сортировку в многопоточном режиме, а также с более быстрого SSD.

Вы можете не заметить, что сортировка также занимает много памяти, так как она проделывает хитрые трюки с временными файлами в /tmp, которые могут быть tmpfs и будут находиться в вашей оперативной памяти (попробуйте отсортировать файл, размер которого больше /tmp, вы столкнетесь с проблемами нехватки места, вот почему мне нужен флаг -T . в приведенной выше команде).

$ time sort -u test > /dev/null
339.24user 3.54system 1:28.87elapsed 385%CPU (0avgtext+0avgdata 2365856maxresident)k
9555544inputs+0outputs (0major+591298minor)pagefaults 0swaps

$ time awk '!x[$0]++' test > /dev/null                                                                                                                             
51.15user 1.55system 0:52.94elapsed 99%CPU (0avgtext+0avgdata 10976maxresident)k
0inputs+0outputs (0major+1923minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                  
421.89user 2.76system 7:06.63elapsed 99%CPU (0avgtext+0avgdata 1980maxresident)k
52712inputs+0outputs (0major+79minor)pagefaults 0swaps

Ну, это похожеВаше решение awk самое быстрое из этих 3, и фактически использует меньше всего памяти

обновление2 и теперь с более простой локалью

$ export LC_ALL=c
$ time sort -u test > /dev/null                                                                                                                                             1.2m ? Tue Apr 21 17:09:22 2020
119.18user 3.64system 0:38.24elapsed 321%CPU (0avgtext+0avgdata 2013472maxresident)k

$ time awk '!x[$0]++' test > /dev/null                                                                                                                                1161ms ? Tue Apr 21 17:07:31 2020
67.23user 2.50system 1:10.16elapsed 99%CPU (0avgtext+0avgdata 10480maxresident)k
7187520inputs+0outputs (0major+1912minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                               
22.05user 2.02system 0:24.24elapsed 99%CPU (0avgtext+0avgdata 1488maxresident)k
2959648inputs+0outputs (1major+72minor)pagefaults 0swaps

На этот разuniq выигрывает гонку... как намекает Стефан Шазелас в комментариях, установка локали на C значительно ускоряет sort и uniq!

Answer 3

Я обнаружил, что сортировка, похоже, является самым быстрым инструментом uniq, как показано здесь -->Самый быстрый способ удалить дубликаты в большом списке слов?