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

Question

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

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

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

head (sort somelist) 

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

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

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

Answer 1

Это:

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

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

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

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

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

Quicksort хорошо работает в этом случае, в то время как-то по умолчанию в Haskell (сортировка слиянием) не сочиняет так хорошо, как это делает больше работы, чем строго необходимо возвращать каждый элемент отсортированного списка. Как this post on the Haskell mailing list примечание:

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

O (п + к лог-к) суммарное время [1]

в то время ленивого слияния необходимо

O (п + лог к ​​п) общее время [2]

для больше вы хотели бы прочитать this blog post.

Answer 2

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

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

Answer 3

Если вы создаете функцию сравнения, которая прослеживает свои аргументы, как это в командной строке 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' 

Если вы хотите, чтобы понять, как это работает, посмотрите исходный код функции сортировки и оценки «сортировки„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") 

А теперь мы сделали достаточно, чтобы обнаружить, что «а» является первым элементом в результате без оценки другого вызова «QSort». Я опустил фактическое сравнение, потому что он скрыт внутри вызова «раздела». Фактически «раздел» также ленив, поэтому на самом деле аргумент другому «qsort» не был оценен, насколько я показал его.