Scala в примерах: различия между версиями
Содержимое удалено Содержимое добавлено
Annayudi (обсуждение | вклад) →Определение класса List I: методы первого порядка: — перевод параграфа |
Annayudi (обсуждение | вклад) →Пример: сортировка слиянием: — перевод параграфа |
||
Строка 2399:
== Пример: сортировка слиянием ==
Представленную ранее в этой главе сортировку вставками просто сформулировать, но она не очень эффективна. Ее средняя сложность пропорциональна квадрату длины входного списка. Теперь мы разработаем программу для сортировки элементов списка, которая более эффективна. Хороший алгоритм для этого — сортировка слиянием, и работает он следующим образом.
Во-первых, если в списке ноль или один элемент, он уже отсортирован, поэтому возвращаем неизмененный список. Более длинные списки разделяются на два подсписка, каждый из которых содержит примерно половину элементов начального списка. Каждый подсписок сортируется рекурсивным вызовом сортирующей функции, и два получившихся отсортированных списка затем сливаются.
Для общей реализации сортировки слиянием мы все равно должны указать тип элементов списка, который нужно отсортировать, а также функцию, используемую для сравнения элементов. Мы получим максимально обобщенную функцию, передавая их в качестве параметров. Это приводит к такой реализации:
<font size=3><syntaxhighlight lang=Scala>
def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {
def merge(xs1: List[A], xs2: List[A]): List[A] =
if (xs1.isEmpty) xs2
else if (xs2.isEmpty) xs1
else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
else xs2.head :: merge(xs1, xs2.tail)
val n = xs.length/2
if (n == 0) xs
else merge(msort(less)(xs take n), msort(less)(xs drop n))
}
</syntaxhighlight></font>
Сложность <tt>msort</tt> — ''O(N log(N))'', где ''N'' — длина входного списка. Чтобы понять, почему, заметим, что разделение списка пополам и слияние двух отсортированных списков занимает время, пропорциональное длине аргумента(ов). Каждый рекурсивный вызов msort разделяет количество элементов ввода пополам, поэтому происходит ''O(log(N))'' последовательных рекурсивных вызовов, пока не достигается базовый случай со списками длины <tt>1</tt>. Для более длинных списков каждый вызов ведет к двум дальнейшим вызовам. Суммировав, получаем, что на каждом из ''O(log(N))'' уровне вызова каждый элемент начального списка принимает участие в одной операции разделения и одной операции слияния. Сложность каждого уровня вызова пропорциональна ''O(N)''. Поскольку есть ''O(log(N))'' уровней, получим, что общая сложность пропорциональна ''O(N log(N))''. Эта сложность не зависит от начального распределения элементов в списке, поэтому сложность в худшем случае такая же, как и в среднем. Поэтому сортировка слиянием — хороший алгоритм для сортировки списков.
Вот пример того, как используется <tt>msort</tt>:
<font size=3><syntaxhighlight lang=Scala>
msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
</syntaxhighlight></font>
Определение <tt>msort</tt> каррировано, чтобы упростить специализацию этого метода с конкретными функциями сравнения. Например,
<font size=3><syntaxhighlight lang=Scala>
val intSort = msort((x: Int, y: Int) => x < y)
val reverseSort = msort((x: Int, y: Int) => x > y)
</syntaxhighlight></font>
== Определение класса List II: методы высшего порядка ==
== Заключение ==
| |||