Короткое замыкание

Этот:

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

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

Например, если мы используем быструю сортировку в качестве базового алгоритма сортировки, то head . quicksort эквивалентен оптимальному (!) алгоритму выбора, известному как 'quickselect', который в худшем случае является линейным. Более того, мы можем реализовать k-quickselect просто с помощью take k . quicksort.

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

Поскольку языковая поддержка сортировки более распространена, упрощенный подход сортировки с последующим индексированием предпочтительнее во многих средах, несмотря на недостаток скорости. Действительно, для ленивых языков этот упрощенный подход может даже обеспечить максимально возможную сложность для k наименьшего/наибольшего отсортированного (с максимумом/минимумом в качестве особого случая), если ваша сортировка достаточно ленива.

Быстрая сортировка хорошо работает в этом сценарии, в то время как сортировка по умолчанию в Haskell (сортировка слиянием) не так хороша, поскольку она выполняет больше работы, чем строго необходимо для возврата каждого элемента отсортированного списка. Как отмечается в этом сообщении в списке рассылки Haskell:

ленивая быстрая сортировка может произвести пакет из первых k наименьших элементов в

O(n + k log k) общее время [1]

в то время как ленивая сортировка слиянием требует

O(n + k log n) общее время [2]

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

Если вы создадите функцию сравнения, которая отслеживает свои аргументы, например, в командной строке GHCi:

> :module + Data.List Debug.Trace
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y

то вы можете сами увидеть поведение:

> sortBy myCompare "foobar"

"     Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
a     Cmp 'b' 'r'
b     Cmp 'f' 'o'
      Cmp 'f' 'r'
f     Cmp 'o' 'o'
      Cmp 'o' 'r'
o     Cmp 'o' 'r'
or"

Haskell лениво оценивает строку, по одному символу за раз. Левая колонка печатается по мере нахождения каждого символа, а правая колонка записывает необходимые сравнения, напечатанные с помощью «трассировки».

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

Тогда попробуй

> head $ sortBy myCompare "foobar"

      Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
'a'

Если вы хотите понять, как это работает, найдите исходный код функции сортировки и оцените 'sort "foobar"' вручную на бумаге.

qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort greater
   where (less, greater) = partition (< x) xs

So

   qsort ('f':"oobar")
 = qsort ('b':"a") ++ "f" ++ qsort ('o':"or")
 = ("a" ++ "b") ++ "f" ++ qsort ('o':"or")

И теперь мы сделали достаточно, чтобы обнаружить, что 'a' является первым элементом в результате, без необходимости оценивать другой вызов qsort. Я опустил фактическое сравнение, потому что оно скрыто внутри вызова «partition». На самом деле «раздел» также ленив, поэтому на самом деле аргумент другого «qsort» не оценивался, насколько я это показал.

Алгоритм, который вы только что описали, имеет конкретное название: «сортировка выбором». Это O(n²), так что это не самое быстрое, что вы можете сделать. Однако, если вам нужны первые «k» элементов в отсортированном массиве, сложность будет O (kn), что хорошо, если «k» достаточно мал (как в вашем примере).

Обратите внимание, что вы используете чистую функцию на функциональном языке. Компилятор, скорее всего, сможет сгенерировать оптимизированный код для sort в обоих случаях, взглянув на то, как составлены функции. Можно легко сделать вывод, что вам нужен минимальный элемент при составлении head и sort.