Внешние сортировка и перестановка: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
'''Сортировка распределением''' | '''Сортировка распределением''' | ||
''Сортировка распределением'' [9] представляет собой рекурсивный процесс, который использует набор из S - 1 элементов разбиения для распределения элементов на S несовпадающих «корзин». Все элементы в одной корзине предшествуют всем элементам в следующей корзине. Сортировка завершается рекурсивной сортировкой отдельных корзин и объединением их в единый, полностью отсортированный список. | |||
| Строка 97: | Строка 97: | ||
Метод рандомизированного зацикливания или связанные с ним методы сортировки слиянием, рассмотренные в конце раздела «Сортировка слиянием», являются предпочтительными для сортировки с использованием параллельных дисков. Преимущество алгоритмов сортировки распределением над подходами на основе слияния, представленными в разделе «Сортировка слиянием», заключается в том, что они обычно лучше используют нижние уровни кэша в иерархии памяти реальных систем, о чем можно судить по анализу алгоритмов сортировки распределением и сортировки слиянием на моделях иерархической памяти. | Метод рандомизированного зацикливания или связанные с ним методы сортировки слиянием, рассмотренные в конце раздела «Сортировка слиянием», являются предпочтительными для сортировки с использованием параллельных дисков. Преимущество алгоритмов сортировки распределением над подходами на основе слияния, представленными в разделе «Сортировка слиянием», заключается в том, что они обычно лучше используют нижние уровни кэша в иерархии памяти реальных систем, о чем можно судить по анализу алгоритмов сортировки распределением и сортировки слиянием на моделях иерархической памяти. | ||
'''Сортировка слиянием''' | '''Сортировка слиянием''' | ||
| Строка 142: | Строка 143: | ||
Алгоритмы для БПФ быстрее и проще, чем для сортировки, поскольку вычисления неадаптивны по своей природе и, таким образом, схема коммуникаций фиксирована заранее [16]. | Алгоритмы для БПФ быстрее и проще, чем для сортировки, поскольку вычисления неадаптивны по своей природе и, таким образом, схема коммуникаций фиксирована заранее [16]. | ||
== Нижние границы для операций ввода-вывода == | == Нижние границы для операций ввода-вывода == | ||