4551
правка
Сортировка без явного задания параметров кэша: различия между версиями
Перейти к навигации
Перейти к поиску
м
Сортировка без явного задания параметров кэша (посмотреть исходный код)
Версия от 16:05, 11 марта 2017
, 11 марта 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
Фриго и др [8] представили два алгоритма сортировки без явного задания параметров кэша, которые также могут использоваться для перестановки массива элементов. Первый алгоритм [8, глава 4] носит название ''сортировки воронкой (Funnelsort)'' и напоминает классическую бинарную сортировку слиянием; второй алгоритм [8, глава 5] является алгоритмом ''сортировки распределением''. Оба алгоритма обеспечивают ''оптимальные'' <math>O(\frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{M})</math> переносов блоков памяти при условии соблюдения ''предположения о высоте кэша'' <math>M = \Omega (B^2) \;</math>. | Фриго и др [8] представили два алгоритма сортировки без явного задания параметров кэша, которые также могут использоваться для перестановки массива элементов. Первый алгоритм [8, глава 4] носит название ''сортировки воронкой (Funnelsort)'' и напоминает классическую бинарную сортировку слиянием; второй алгоритм [8, глава 5] является алгоритмом ''сортировки распределением''. Оба алгоритма обеспечивают ''оптимальные'' <math>O(\frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{M})</math> переносов блоков памяти при условии соблюдения ''предположения о высоте кэша'' <math>M = \Omega (B^2) \;</math>. | ||
Рис. 1. Общая рекурсия сортировки воронкой (слева) и 16-слияния (справа) | |||