286
правок
Изменения
Join
=== Сортировка ===
Поскольку мы легко умеем выполнять слияние упорядоченных последовательностей, то логичным шагом будет рассмотреть сортировку во внешней памяти. Рассмотрим некоторую модификацию алгоритма Merge sort. В стандартном алгоритме все элементы разбиваются на пары, после чего сливаются в упорядоченные последовательности длины 2, те в свою очередь сливаются в последовательности длины 4 и т.д. (для простоты в данном алгоритме будем считать что N это степень двойки). Во внешней памяти не выгодно начинать с последовательностей длины 1, так как чтение происходит блоками длины B. Вместо этого можно целиком считать блок и отсортировать его во внутренней памяти. Тогда количество листьев в дереве сортировки будет не N, а <tex>\dfrac{N}{B}</tex>. Помимо этого, гораздо выгоднее сливать больше чем 2 списка за раз, чтобы уменьшить высоту дерева сортировки. Так как оперативная память размера M, то можно сливать сразу <tex>\dfrac{M}{B}</tex> списков. Итого, на каждом уровне дерева сортировки мы выполняем <tex>\mathcal{O}\left(\dfrac{N}{B}\right)</tex> операций и итоговая сложность {{---}} <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{B}\right) = Sort(N)</tex>.
В качестве небольшой оптимизации можно в начале сортировать во внутренней памяти последовательности длины M, а не B. Хотя итоговая сложность и станет <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{M}\right)</tex>, но это уменьшит высоту дерева сортировки всего на единицу, что не очень сильно скажется на времени работы.
=== Join ===
Рассмотрим следующую задачу {{---}} пусть у нас во внешней памяти есть 2 последовательности вида <tex>(ключ, значение)</tex>. Первая последовательность имеет вид <tex>(k_i, a_{k_i})</tex>, вторая {{---}} <tex>(l_j, b_{l_j})</tex> и мы хотим получить последовательность вида <tex>(i, a_i, b_i)</tex> (не умоляя общности считаем что <tex>(k_1 \dots k_n)</tex> и <tex>(l_1 \dots l_n)</tex> являются перестановками чисел от 1 до n). Очевидно, что задача решается просто сортировками последовательностей по первому аргументу с проходом проходом по ним 2 указателями. Поэтому сложность алгоритма {{---}} <tex>Sort(N)</tex>.
== List Ranking ==
