Срывание вида
Это - все о правильном инструменте для задания. Ни один не лучшие 100% времени. Обе системы были созданы человеком и имеют дефекты. Извините, но мы сосем и создание идеального материала.
мне нравится динамический контроль типов, потому что он выходит из моего пути, но да ошибки периода выполнения могут накопиться, который я не запланировал. Где, поскольку статический контроль типов может зафиксировать вышеупомянутые ошибки, но управлять новичком (на типизированных языках) программист сумасшедшая попытка бросить между постоянным символом и строкой.
3 ответа
Это:
Нужно будет найти только наименьший элемент в списке, потому что это все, что используется.
... должен действительно сказать, что функции нужно только выполнить минимальный объем работы , который требуется алгоритму сортировки , чтобы найти наименьший элемент.
Например, если мы используем быструю сортировку в качестве основного алгоритма сортировки, тогда голова. quicksort эквивалентен алгоритму оптимального (!) выбора, известному как « quickselect », который в худшем случае является линейным. Более того, мы можем реализовать k -quickselect просто с помощью take k. quicksort .
Wikipedia отмечает в своей статье об алгоритмах выбора, что (выделено мной):
Поскольку языковая поддержка для сортировки более повсеместна, Упрощенный подход сортировки с последующим индексированием предпочтителен во многих средах, несмотря на его недостаток в скорости. Действительно, для ленивых языков этот упрощенный подход может даже дать вам наилучшую возможную сложность для k наименьших / наибольших отсортированных (с максимальным / минимальным в качестве особого случая), если ваша сортировка достаточно ленивая.
Быстрая сортировка работает хорошо. в этом сценарии, тогда как сортировка по умолчанию в Haskell (сортировка слиянием) не так хорошо работает, поскольку она выполняет больше работы, чем строго необходимо, чтобы вернуть каждый элемент отсортированного списка. Как этот пост в списке рассылки Haskell отмечает:
lazy quicksort может создать пакет этот упрощенный подход может даже дать вам наилучшую возможную сложность для k наименьших / наибольших отсортированных (с максимальным / минимальным в качестве особого случая), если ваша сортировка достаточно ленивая.
Быстрая сортировка хорошо работает в этом сценарии, тогда как сортировка по умолчанию в Haskell (сортировка слиянием) не так хорош, поскольку он выполняет больше работы, чем это строго необходимо для возврата каждого элемента отсортированного списка. Как этот пост в списке рассылки Haskell отмечает:
lazy quicksort может создать пакет этот упрощенный подход может даже дать вам наилучшую возможную сложность для k наименьших / наибольших отсортированных (с максимальным / минимальным в качестве особого случая), если ваша сортировка достаточно ленивая.
Быстрая сортировка хорошо работает в этом сценарии, тогда как сортировка по умолчанию в Haskell (сортировка слиянием) не так хорош, поскольку он выполняет больше работы, чем это строго необходимо, чтобы вернуть каждый элемент отсортированного списка. Как этот пост в списке рассылки Haskell отмечает:
lazy quicksort может создать пакет первые k наименьших элементов в
O (n + k log k) общее время [1]
, в то время как ленивая сортировка слиянием требует
O (n + k log n) общего времени [2]
Для большего может прочитать это сообщение в блоге .
Алгоритм, который вы только что описали, имеет особое имя: «сортировка по выбору». Это O (n 2 ), так что это не самая быстрая вещь, которую вы могли сделать. Однако, если вам нужны первые «k» элементов в отсортированном массиве, сложность будет O (kn), что хорошо, если «k» достаточно мало (как в вашем примере).
Обратите внимание, что вы используете чистый функционировать на функциональном языке. Компилятор, вероятно, сможет сгенерировать оптимизированный код для sort в обоих случаях, посмотрев на способ составления функций. Он может легко сделать вывод, что вам нужен минимальный элемент, когда вы составляете head и sort .
Если вы создадите функцию сравнения, которая отслеживает ее аргументы, как это в командной строке 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
Итак
qsort ('f':"oobar")
= qsort ('b':"a") ++ "f" ++ qsort ('o':"or")
= ("a" ++ "b") ++ "f" ++ qsort ('o':"or")
И теперь мы сделали достаточно, чтобы обнаружить, что 'a' является первым элементом результата, без необходимости оценивать другой вызов «qsort». Я пропустил фактическое сравнение, потому что оно скрыто внутри вызова «partition». На самом деле «разделение» также является ленивым, поэтому на самом деле аргумент другого «qsort» не был оценен, насколько я его показал.