Тип короткого замыкания

Question

Я понимаю это:

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

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

head (sort somelist)

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

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

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

Answer 1

Это:

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

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

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

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

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

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

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

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

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

> head $ sortBy myCompare "foobar"

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

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

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

Так

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

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

Answer 3

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

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