Сортировка короткого замыкания

Question

Я понимаю, что:

head (map (2**) [1..999999])

На самом деле будет оцениваться только 2 ** 1, и ни один из остальных, но книга, которую я читаю, говорит, что:

head (sort somelist)

Нужно будет найти только самый маленький элемент в списке, потому что это все, что используется. Как это работает? Насколько я могу судить, это было бы невозможно с известными мне алгоритмами сортировки (такими как пузырьковая сортировка).

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

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

Answer 1

Это:

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

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

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

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

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

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

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

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

пока ленивый сортировщик нуждается в

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

Более подробно вы можете прочитать это сообщение в блоге .

Answer 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 оценивает строку лениво, по одному символу за раз. Левый столбец печатается при обнаружении каждого символа, а правый столбец записывает требуемые сравнения, как указано в «trace».

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

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

> 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» не был оценен, насколько я это показал.

Answer 3

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

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