Алгоритм работы с внешней памятью
-
Основы алгоритмов с внешней памятью
- Алгоритмы с внешней памятью обрабатывают данные, которые слишком велики для основной памяти.
- Оптимизированы для эффективного доступа к данным на медленных носителях.
-
Модель внешней памяти
- Абстрактная машина, аналогичная модели с оперативной памятью, но с кэшем.
- Отражает различия в скорости операций чтения и записи между кэшем и основной памятью.
- Время выполнения алгоритма определяется количеством операций ввода-вывода.
-
Алгоритмы и их эффективность
- Используют свойство локализации для извлечения блоков данных.
- Поиск и сортировка выполняются с использованием B-деревьев и M-B сортировки слиянием.
- Перестановка элементов требует времени, пропорционального N или N/B log(M/B)N/B).
-
Применение модели
- Отражает иерархию памяти, не моделируемую в других моделях.
- Важна для анализа алгоритмов с большими наборами данных.
- Используется в географических информационных системах и цифровой обработке сигналов.
-
История и связанные понятия
- Термин «внеядерный» впервые использован в 1962 и 1971 годах соответственно.
- Упоминаются другие связанные понятия, такие как обход графа внешней памяти и параллельная внешняя память.