4446
правок
Модель без явного задания параметров кэша: различия между версиями
Материал из WEGA
Модель без явного задания параметров кэша (посмотреть исходный код)
Версия от 13:22, 27 февраля 2017
, 27 февраля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 48: | Строка 48: | ||
Что касается сортировки, то фундаментальной особенностью модели ввода-вывода является то, что сортировка N элементов при помощи сравнения требует | Что касается сортировки, то фундаментальной особенностью модели ввода-вывода является то, что сортировка N элементов при помощи сравнения требует <math>\Theta (Sort(N)) \;</math> переносов содержимого памяти [2], где <math>Sort(N) = \frac{N}{B} log_{\frac{M}{B}} \; \frac{N}{M}</math>. В модели без явного задания параметров кэша сортировка может быть выполнена за <math>\Theta (Sort(N)) \;</math> переносов содержимого памяти при условии принятия так называемого ''предположения о высоте кэша'' – <math>M \ge B^{1 + \varepsilon} \;</math> [15,22]. Было показано, что выполнение этого предположения обязательно [16], что доказывает разницу в эффективности между алгоритмами без явного задания параметров кэша и алгоритмами в модели ввода-вывода (где это предположение не требуется для определения границы сортировки). | ||
При выполнении поиска B-деревья обеспечивают стоимость O( | При выполнении поиска B-деревья обеспечивают стоимость <math>O(log_B \; N)</math>, что является оптимальным в модели ввода-вывода для поиска на базе сравнения. Эта стоимость достижима и в модели без явного задания параметров кэша, что было показано для статического [25] и для динамического случая [13]. Позднее было предложено несколько вариантов деревьев поиска без явного задания параметров кэша. Кроме того, в [12] было показано различие между алгоритмами без явного задания параметров кэша и алгоритмами модели ввода-вывода, а именно – что константы, достижимые в границе <math>O(log_B \; N)</math>, доказуемо различаются. | ||
Перестановка в модели ввода-вывода имеет сложность | Перестановка в модели ввода-вывода имеет сложность <math>\Theta (min \{ Sort(N), N \} ) \;</math> в предположении, что элементы неделимы [2]. Было доказано [16], что эта асимптотическая сложность не может быть получена в модели без явного задания параметров кэша, так что и в случае этой задачи разделение имеет место. | ||
Была предложена реализация очередей с приоритетами на базе модели без явного задания параметров кэша с <math>O(\frac{1}{B} log_{\frac{M}{B}} \; \frac{N}{M})</math> амортизированных переносов содержимого памяти. | |||
К настоящему времени также разработаны алгоритмы модели без явного задания параметров кэша для задач вычислительной геометрии [1, 6, 7, 8, 10, 15], графовых задач [4, 17, 18, 23], для сканирования динамических множеств [ ], укладки статических деревьев [11], задач поиска на мультимножествах [21], динамического программирования [19], частичной устойчивости [10], матричных операций [22] и быстрого преобразования Фурье [22]. | |||
К настоящему времени также разработаны алгоритмы модели без явного задания параметров кэша для задач вычислительной геометрии [1, 6, 7, 8, 10, 15], графовых задач [4, 17, 18, 23], для сканирования динамических множеств [9], укладки статических деревьев [11], задач поиска на мультимножествах [21], динамического программирования [19], частичной устойчивости [10], матричных операций [22] и быстрого преобразования Фурье [22]. | |||
== Применение == | == Применение == | ||
