Сортировка и подсчет количества появлений строк

Question

У меня есть файл 35 ГБ с примером различных строк:

test1
test2
test1
test34!
test56
test56
test896&
test1
test4
etc
...

Есть несколько миллиардов строк.

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

Вот что я использовал в bash:

cat file.txt | sort | uniq -c | sort -nr

Есть ли более эффективный способ сделать это? Или есть способ, которым я могу видеть прогресс, или он просто загрузит мой компьютер еще больше и сделает его еще медленнее?

Answer 1

Если дубликатов много, т.е.если уникальные строки уместились бы в вашей доступной памяти, вы могли бы подсчитать строки и отсортировать их, используя GNU awk:

$ awk '{
    a[$0]++                                # hash the lines and count
}
END {                                      # after counting the lines
    PROCINFO["sorted_in"]="@val_num_desc"  # used for traverse order 
    for(i in a)
        print a[i],i
}' file

Вывод для ваших образцов данных:

3 test1
2 test56
1 test34!
1 test2
1 test4
1 etc
1 test896&
1 ...

Сопутствующая документация: https://www.gnu.org/software/gawk/manual/html_node/Controlling-Scanning.html

Обновление Поскольку памяти было недостаточно (см. Комментарии), разбейте файл на 0-2 первых символа строки.Распределение не будет равномерным:

$ awk '{
    ch=substr($0,match($0,/^.{0,2}/),RLENGTH)  # 0-2 first chars
    if(!(ch in a))                             # if not found in hash
        a[ch]=++i                              # hash it and give a unique number
    filename=a[ch]".txt"                       # which is used as filename
    print >> filename                          # append to filename
    close(filename)                            # close so you wont run out of fds
}' file

Вывод с вашими тестовыми данными:

$ ls -l ?.txt
-rw-rw-r-- 1 james james 61 May 13 14:18 1.txt
-rw-rw-r-- 1 james james  4 May 13 14:18 2.txt
-rw-rw-r-- 1 james james  4 May 13 14:18 3.txt
$ cat 3.txt
...

300 МБ и 1,5 М строк за 50 секунд.Если я удалил close(), это заняло бы всего 5 секунд, но вы рискуете исчерпать дескрипторы файлов.Я думаю, вы могли бы увеличить сумму.