Сортировка Linux против программирования

Question

Я пытаюсь понять, почему мое программное обеспечение (golang) работает в 350 раз медленнее, чем команда сортировки linux? Я сортировал текстовый файл UTF-8 размером около 13 000 000 строк (длиной 4–20 байт).

пример кода из моей функции (если checkDupl false добавить в newArray):

func checkDupl(in []byte) bool {
    for i := range newArray {
        if bytes.Equal(in, newArray[i]) {
            return true
        }
    }
    return false
}

Этот код закончил около 25% за ночь.

Этот код закончился за 8 минут:

  497  export LC_ALL=C
  498  time sort -us -o file_unique.txt file.txt

Answer 1

sort -u работает, сортируя входные данные, затем просматривая и распечатывая каждый уникальный элемент. Это можно сделать, просто запомнив, что было напечатано последним, и напечатав новый элемент каждый раз, когда он изменяется.

Ваш код выглядит как линейный поиск в выходном массиве, поэтому я предполагаю, что он является частью более широкого алгоритма примерно так:

for each X in input:
    if not checkDupl(X) then:
        append X to newArray

Это означает, что ваша функция checkDupl запускается один раз для каждого элемента на входе, а затем цикл внутри checkDupl запускается один раз для каждого элемента на выходе. В худшем случае весь список уникален, поэтому checkDupl смотрит на один элемент в первый раз, затем на два, затем на три, затем на четыре ... Эта последовательность в сумме составляет n (n + 1) / 2, или 0,5н ^ 2 + 0,5н. 13 000 000 в квадрате доминирует над 6,5 млн. Другого термина, поэтому мы называем этот алгоритм «квадратичным временем», или O (n ^ 2). Это наихудший случай, а также средний случай (но ваш лучший случай, 13 000 000 идентичных строк, будет довольно быстрым).

Существует много обычных алгоритмов сортировки, которые работают за O (n log n) времени. POSIX не требует sort, чтобы использовать один из этих , но все разумные реализации будут делать это. Член log (n) растет очень медленно, поэтому он будет намного меньше, чем n ^ 2. Время печати равно O (n), и его можно игнорировать по той же причине, что и выше.

---

Ваша программа будет работать намного дольше, чем sort во всех, кроме самых тривиальных случаях, для всех, кроме самых глупых sort с. Для ваших тринадцати миллионов предметов разница может быть в сотни тысяч раз (игнорируя все остальное в программах).

Вы можете реализовать алгоритм сортировки и повторить подход sort или использовать библиотечную функцию. Вы также можете использовать структуру данных, более подходящую для проверки уникальности, например хеш-таблицу, а не массив, требующий линейного поиска. Скорее всего, лучше использовать библиотечные функции, чем пытаться свернуть все самостоятельно.