Внешние алгоритмы используют память
В вычислении , алгоритмы внешней памяти или вне ядра алгоритмов являются алгоритмами , которые предназначены для данных процесса , которые являются слишком большими , чтобы вписаться в компьютере основной память одновременно. Такие алгоритмы должны быть оптимизированы для эффективного извлечения и доступа к данным, хранящимся в медленной основной памяти ( вспомогательной памяти ), такой как жесткие диски или ленточные накопители , или когда память находится в компьютерной сети . [1] [2] Алгоритмы внешней памяти анализируются в модели внешней памяти .
Содержание
Кэш слева содержит блоки размером каждый, всего M объектов. Объем внешней памяти справа неограничен. M B >> B
Алгоритмы внешней памяти анализируются в идеализированной модели вычислений, называемой моделью внешней памяти (или моделью ввода-вывода , или моделью доступа к диску ). Модель внешней памяти - это абстрактная машина, аналогичная модели RAM-машины , но с кеш-памятью в дополнение к основной памяти . Модель учитывает тот факт, что операции чтения и записи в кэше выполняются намного быстрее, чем в основной памяти , и что чтение длинных непрерывных блоков происходит быстрее, чем чтение в случайном порядке с использованием головки чтения и записи диска . Время работы из алгоритма в модели внешней памяти определяется количеством требуемых операций чтения и записи в память. [3] Эта модель была введена Alok Aggarwal и Джеффри Виттер в 1988 году [4] Внешняя модель памяти связана с кэш-модели не обращая внимания , но алгоритмы во внешней памяти модели могут знать , как размер блока , и кэш размер. По этой причине модель иногда называют моделью с учетом кеширования . [5]
Модель состоит из процессора с внутренней памятью или кеш-памятью размера M , подключенного к неограниченной внешней памяти. И внутренняя и внешняя память разделена на блоки размера B . Одна операция ввода / вывода или передачи памяти состоит из перемещения блока из B смежных элементов из внешней памяти во внутреннюю, а время работы алгоритма определяется количеством этих операций ввода / вывода. [4]
Алгоритмы в модели внешней памяти используют тот факт, что при извлечении одного объекта из внешней памяти извлекается весь блок размером . Это свойство иногда называют местностью. B
Поиск элемента среди объектов возможен во внешней модели памяти с помощью B-дерева с коэффициентом ветвления . С помощью B-дерева поиск, вставка и удаление могут выполняться во времени (в нотации Big O ). Информация теоретически это минимальное время выполнения, возможное для этих операций, поэтому использование B-дерева является асимптотически оптимальным . [4] N B О ( бревно B N ) N)>
Внешняя сортировка - это сортировка во внешней памяти. Внешняя сортировка может быть выполнена с помощью сортировки по распределению, которая похожа на быструю сортировку , или с помощью сортировки слиянием по пути . Оба варианта обеспечивают асимптотически оптимальное время выполнения для сортировки N объектов. Эта оценка также применима к быстрому преобразованию Фурье в модели внешней памяти. [2] M B >> О ( N B бревно M B N B ) > \ log _ > >)>
Проблема перестановки состоит в том, чтобы переставить элементы в определенную перестановку . Это можно сделать либо путем сортировки, для чего требуется указанная выше среда выполнения сортировки, либо путем вставки каждого элемента по порядку и игнорирования преимущества локальности. Таким образом, перестановку можно произвести вовремя. N О ( мин ( N , N B бревно M B N B ) ) > \ log _ > >))>
Модель внешней памяти захватывает иерархию памяти , которая не моделируется в других распространенных моделях, используемых при анализе структур данных , таких как машина с произвольным доступом , и полезна для доказательства нижних границ для структур данных. Модель также полезна для анализа алгоритмов, которые работают с наборами данных, слишком большими для размещения во внутренней памяти. [4]
Типичным примером являются географические информационные системы , особенно цифровые модели рельефа , где полный набор данных легко превышает несколько гигабайт или даже терабайт данных.
Эта методология выходит за рамки процессоров общего назначения и также включает вычисления на GPU, а также классическую цифровую обработку сигналов . В вычислениях общего назначения на графических процессорах (GPGPU) используются мощные графические карты (GPU) с небольшим объемом памяти (по сравнению с более привычной системной памятью, которую чаще всего называют просто RAM ) с относительно медленным переходом между процессорами и процессорами. Передача памяти графического процессора (по сравнению с пропускной способностью вычислений).
Раннее использование термина «вне ядра» в качестве прилагательного в 1962 году по отношению к устройствам , которые помимо основной памяти в качестве IBM 360 . [6] Первое использование термина «вне ядра» применительно к алгоритмам появилось в 1971 году. [7]
Эта статья продолжает вводные статьи об асимптотическом анализе сложности алгоритмов на Хабре. Здесь вы узнаете о smoothed анализе и об особенностях анализа алгоритмов во внешней памяти. Любознательных ждут ссылки на дополнительный материал, а в конце я съем полином.
СОДЕРЖАНИЕ
Кэш слева содержит блоки размером каждый, всего M объектов. Объем внешней памяти справа неограничен. M B >> B
Алгоритмы внешней памяти анализируются в идеализированной модели вычислений, называемой моделью внешней памяти (или моделью ввода-вывода , или моделью доступа к диску ). Модель внешней памяти - это абстрактная машина, подобная модели машины RAM , но с кеш-памятью в дополнение к основной памяти . Модель учитывает тот факт, что операции чтения и записи в кэше выполняются намного быстрее, чем в основной памяти , и что чтение длинных непрерывных блоков происходит быстрее, чем чтение в случайном порядке с использованием головки чтения и записи диска . Время работы из алгоритма в модели внешней памяти определяется количеством требуемых операций чтения и записи в память. [3] Эта модель была введена Alok Aggarwal и Джеффри Виттер в 1988 году [4] Внешняя модель памяти связана с кэш-модели не обращая внимания , но алгоритмы во внешней памяти модели могут знать , как размер блока , и кэш размер. По этой причине модель иногда называют моделью с учетом кеширования . [5]
Модель состоит из процессора с внутренней памятью или кеш-памятью размера M , подключенного к неограниченной внешней памяти. И внутренняя и внешняя память разделена на блоки размера B . Одна операция ввода / вывода или передачи памяти состоит из перемещения блока из B смежных элементов из внешней памяти во внутреннюю, а время работы алгоритма определяется количеством этих операций ввода / вывода. [4]
Алгоритмы в модели внешней памяти используют тот факт, что при извлечении одного объекта из внешней памяти извлекается весь блок размера . Это свойство иногда называют местностью. B
Поиск элемента среди объектов возможен во внешней модели памяти с помощью B-дерева с коэффициентом ветвления . Используя B-дерево, поиск, вставка и удаление могут быть выполнены во времени (в нотации Big O ). Информация теоретически , это минимальное время выполнения, возможное для этих операций, поэтому использование B-дерева является асимптотически оптимальным . [4] N B О ( бревно B N ) N)>
Внешняя сортировка - это сортировка во внешней памяти. Внешняя сортировка может выполняться с помощью сортировки по распределению, которая похожа на быструю сортировку , или с помощью сортировки слиянием по пути . Оба варианта обеспечивают асимптотически оптимальное время выполнения для сортировки N объектов. Эта оценка также применима к быстрому преобразованию Фурье в модели внешней памяти. [2] M B >> О ( N B бревно M B N B ) > \ log _ > >)>
Проблема перестановки заключается в перестановке элементов в определенную перестановку . Это можно сделать либо путем сортировки, для чего требуется указанная выше среда выполнения сортировки, либо путем вставки каждого элемента по порядку и игнорирования преимущества локальности. Таким образом, перестановку можно произвести вовремя. N О ( мин ( N , N B бревно M B N B ) ) > \ log _ > >))>
Модель внешней памяти захватывает иерархию памяти , которая не моделируется в других распространенных моделях, используемых при анализе структур данных , таких как машина с произвольным доступом , и полезна для доказательства нижних границ для структур данных. Модель также полезна для анализа алгоритмов, которые работают с наборами данных, слишком большими для размещения во внутренней памяти. [4]
Типичным примером являются географические информационные системы , особенно цифровые модели рельефа , где полный набор данных легко превышает несколько гигабайт или даже терабайт данных.
Эта методология выходит за рамки центральных процессоров общего назначения и также включает вычисления на графическом процессоре, а также классическую цифровую обработку сигналов . В вычислениях общего назначения на графических процессорах (GPGPU) используются мощные графические карты (GPU) с небольшим объемом памяти (по сравнению с более известной системной памятью, которую чаще всего называют просто ОЗУ ) с относительно медленным переходом между процессорами и процессорами. Передача памяти графического процессора (по сравнению с пропускной способностью вычислений).
Раннее использование термина «вне ядра» в качестве прилагательного в 1962 году по отношению к устройствам , которые помимо основной памяти в качестве IBM 360 . [6] Первое использование термина «вне ядра» применительно к алгоритмам появилось в 1971 году. [7]
Анализ алгоритмов во внешней памяти
Прежде чем говорить об алгоритмах во внешней памяти стоит подчеркнуть один момент, который обходят стороной. Теоретические оценки, о которых велась речь, формально выводятся не абы где, а в модели под названием «RAM машина». Это такая модель, в которой доступ к произвольному месту памяти происходит за одну элементарную операцию. Таким образом вы приравниваете вычислительные операции и операции с памятью, что упрощает анализ.
Внешняя память это диск, сеть или другое медленное устройство. Для анализа алгоритмов оперирующих с ними используют другую модель выполнения во внешней памяти. Если упрощать, то в этой модели у компьютера есть машинных слов внутренней памяти, все операции с которой, ничего не стоят, так же ничего не стоят вычислительные операции на CPU, а ещё есть внешняя память, с которой возможно работать только целыми блоками размера слов и каждая такая операция считается элементарной. Причем значительно больше . В этой модели говорят об IO сложности алгоритма.
Таким образом даже если решать на каждом блоке NP-полную задачу в памяти, это не повлияет на IO-сложность алгоритма. Но в такой формулировке это не большая проблема поскольку блок имеет фиксированную длину и мы просто говорим, что вот такая у нас элементарная операция. Однако модель будет не применима для алгоритма драматически уменьшающего число операций на CPU ценой увеличения операций с диском, так что в итоге это будет выгодно. Но даже в таком случае, нужно что бы этот размен был нетривиальным. Причем размен в обратную сторону укладывается в модель, поэтому добавление сжатия не вызывает сложностей. А замена медленного алгоритма сжатия на более быстрый, относится к тривиальному размену.
Второе отличие от RAM модели — формат операций. Оперировать можно только крупными непрерывными блоками. Это отражает работу с дисками на практике. Которая в свою очередь обусловлена тем, что у дисков разрыв между скоростью последовательных операций по сравнению с внутренней памятью меньше, чем аналогичный разрыв между операцией с произвольной ячейкой. Таким образом выгодно нивелировать время позиционирования. В модели мы просто говорим, что нам это удалось и времени позиционирования нет, но есть непрерывные блоки длины , достаточной что бы модель была корректной.
При анализе в этой модели будьте аккуратны с округлением, т.к. чтение одного машинного слова и машинных слов занимает одно и то же время. В общем случае чтение последовательных слов занимает операций, и при небольших вклад округления будет значительным, особенно если потом эта величина умножается на что-то.
Из-за особенностей модели задачи начинают решаться будто быстрее, т.к. вычислительные операции ничего не стоят. Например сортировка слиянием выполняется за , что намного быстрее чем могло бы быть. Но не стоит обманываться, при фиксированных и , все это дает лишь мультипликативную константу, которую легко съедает диск.
SSD и кэш
Есть две темы, которые нельзя обойти. Начнем с кэша. Логика примерно следующая: в целом отношения кэша и оперативной памяти похожи на отношения памяти и диска. Но есть один нюанс: у оперативной памяти нет лага на случайный доступ. Несмотря на то, что чтение из L1 кэша примерно в 200 раз быстрее, чем чтение из памяти, все таки основа модели в лаге на поиск. Существует альтернативная постановка вопроса: составить алгоритм так, что бы минимизировать число промахов кэша, но это тема для отдельного разговора.
SSD всего в 4 раз медленнее памяти на последовательное чтение, но в 1500 раз медленнее на случайное чтение. Именно по этому модель в целом справедлива для него, т.к. вы все равно будете хотеть нивелировать лаг на поиск.
Таким образом эта модель хоть и простая, но остается корректной в большом числе случаев. Подробнее об алгоритмах во внешней памяти с примерами анализа предлагаю ознакомиться в курсе Максима Бабенко из 5 лекций.
Бонус
Напоследок расскажу об интересном обозначении, применяемом при анализе NP-полных задач. Сам я узнал о таком обозначении в лекциях Александра Куликова «Алгоритмы для NP-трудных задач».
Неформально символ «О»-большое съедает всё кроме старшего члена, а у старшего члена съедает мультипликативную константу. Оказывается, существует символ , который съедает не просто мультипликативную константу, а целый полином. Т.е. , и . Так что если вам станет грустно из-за того, что ваша программа тормозит, можете утешать себя мыслью, что алгоритмически её IO-сложность .
Обычно оценка сложности рассматриваемых алгоритмов происходит в модели под названием RAM-машина [1] . Это означает, что у нас есть оперативная память, из которой мы можем читать и писать произвольную ячейку памяти за время элементарной операции. Таким образом время вычислительных операций и операций с памятью приравнивается, что сильно упрощает анализ.
Но в таком случае размер данных, с которыми мы работаем, должен помещаться в оперативную память. Предположим, что ее размер порядка [math]10-100[/math] GB, а обработать нужно порядка [math]10[/math] TB информации. Очевидно, что необходимо использовать какую-то внешнюю память, например — жесткий диск. Хотя диски существенно дешевле
Оперативная память слева вмещает [math]\dfrac
оперативной памяти и имеют высокую емкость, они гораздо медленнее из-за механического построения считывания. Для сравнения, время обращения к оперативной памяти порядка [math]100[/math] ns, а к HDD — порядка [math]10[/math] ms ( [math]10^[/math] s и [math]10^[/math] s). Однако, основное время тратится на позиционирование головки жесткого диска, из-за чего разрыв в скорости последовательного чтения не такой большой. Из оперативной памяти можно читать со скоростью порядка [math]10[/math] GB/s, с HDD — порядка [math]100[/math] MB/s.
Из-за описанного выше, для оценки сложности алгоритмов во внешней памяти была предложена другая модель. Модель гласит следующее: существует какая-то внешняя память и процессор со своей внутренней памятью. Внутренняя память ограничена и имеет размер порядка [math]M[/math] машинных слов. Внешняя память считается безграничной в рамках рассматриваемой задачи, то есть имеет размер хотя бы порядка [math]N[/math] машинных слов, где [math]N[/math] — размер задачи. Чтение и запись из внешней памяти происходит блоками последовательных данных размера [math]B[/math] машинных слов. В качестве меры сложности принимается количество операций ввода-вывода, которые выполняет алгоритм, где одна операция ввода-вывода это либо чтение из внешней памяти одного блока размера [math]B[/math] , либо запись.
У данной модели есть один существенный недостаток: мы никак не учитываем время, которое тратится на вычисления, а считаем только обращения к диску. Из-за этого многие задачи в данной модели решаются быстрее, чем в модели с RAM-машиной. Например, прочитав какой-то блок, далее мы имеем право произвести экспоненциальный по сложности перебор, и это никак не будет учитываться. Поэтому нужно иметь в виду, что данная модель стремится эффективно использовать жесткий диск, а не балансировать между использованием процессора и жесткого диска.
На диске записаны [math]N[/math] чисел, нужно найти их сумму (например, по какому-нибудь модулю). Очевидно, что эта задача равносильна просто считыванию с диска. Сложность линейного сканирования данных с диска — [math]\left\lceil\dfrac\right\rceil = Scan(N)[/math] . Важно заметить, что из-за округления, в общем случае [math]\sum\limits_^Scan(N_i) \neq Scan\left(\sum\limits_^N_i\right)[/math] .
Пусть имеется две упорядоченные последовательности размера [math]N_1[/math] и [math]N_2[/math] соответственно. Чтобы их слить, достаточно завести во внутренней памяти [math]3[/math] блока. В первые [math]2[/math] мы будем читать сами последовательности, а в третий — записывать результат слияния, используя стандартный алгоритм с [math]2[/math] указателями. Как только какой-то из указателей дошел до конца блока, необходимо считывать следующий, а когда буфер с результатом слияния заполнился — необходимо записывать его во внешнюю память и очищать. Сложность алгоритма — [math]\mathcal(Scan(N_1 + N_2))[/math]
Поскольку мы легко умеем выполнять слияние упорядоченных последовательностей, логичным шагом будет рассмотреть сортировку во внешней памяти. Рассмотрим некоторую модификацию алгоритма Merge sort. В стандартном алгоритме все элементы разбиваются на пары, после чего сливаются в упорядоченные последовательности длины [math]2[/math] , те в свою очередь сливаются в последовательности длины [math]4[/math] и так далее (для простоты описания будем считать, что [math]N[/math] и [math]B[/math] это степени двойки). Во внешней памяти не выгодно начинать с последовательностей длины [math]1[/math] , так как чтение происходит блоками длины [math]B[/math] . Вместо этого можно целиком считать блок и отсортировать его во внутренней памяти. Тогда количество листьев в дереве сортировки будет не [math]N[/math] , а [math]\dfrac[/math] . Помимо этого, гораздо выгоднее сливать больше чем [math]2[/math] списка за раз, чтобы уменьшить высоту дерева сортировки. Так как оперативная память размера [math]M[/math] , то можно сливать сразу [math]\dfrac[/math] списков. Итого, на каждом уровне дерева сортировки мы выполняем [math]\mathcal\left(\dfrac\right)[/math] операций и итоговая сложность — [math]\mathcal\left(\dfrac\log_<\frac>\dfrac\right) = Sort(N)[/math] .
В качестве небольшой оптимизации можно в начале сортировать во внутренней памяти последовательности длины [math]M[/math] , а не [math]B[/math] . Хотя итоговая сложность и станет [math]\mathcal\left(\dfrac\log_>\dfrac\right)[/math] , но это уменьшит высоту дерева сортировки всего на единицу, что не очень сильно скажется на времени работы.
Пусть во внешней памяти есть [math]2[/math] таблицы вида [math](key, value)[/math] . Первая таблица имеет вид [math](k_i, a_)[/math] , вторая — [math](l_j, b_)[/math] . Необходимо получить таблицу вида [math](i, a_i, b_i)[/math] (не умаляя общности считаем, что [math](k_1 \dots k_N)[/math] и [math](l_1 \dots l_N)[/math] являются перестановками чисел от [math]1[/math] до [math]N[/math] ). Очевидно, что задача решается просто сортировками таблиц по ключу с последующим проходом по ним [math]2[/math] указателями. Поэтому сложность алгоритма — [math]Sort(N)[/math] .
Данный алгоритм хоть и крайне прост, является одним из ключевых примитивов. Когда необходимо совершить какую-то операцию над разбросанными по памяти данными, часто задача сводится к последовательности нескольких Join'ов.
Данная задача заключается в следующем: дан односвязный список, то есть для каждого элемента известно, какой идет следующим за ним. Необходимо для каждого элемента определить, каким он является по счету с конца списка. Расстояние до конца списка будем называть рангом элемента. Несмотря на простоту задачи в RAM-машине, во внешней памяти задача имеет нетривиальное решение. Из-за того что все данные лежат хаотично, мы не можем просто пройтись по списку, это может потребовать слишком много операций ввода-вывода.
Решим задачу следующим способом: выкинем из списка какую-то часть элементов, после чего рекурсивно посчитаем ответ для полученного списка. Затем, зная промежуточный ответ, восстановим ответ для исходной задачи. Первая проблема — в модифицированном списке ранги элементов отличаются. Чтобы решить эту проблему, рассмотрим более общую задачу. Будем считать, что у каждого элемента есть вес, а ранг элемента — это сумма весов до конца списка. Для решения исходной задачи в самом начале присвоим каждому элементу вес [math]1[/math] .
- [math]next[/math] — массив входных данных. [math]next_x = y[/math] означает, что после элемента [math]x[/math] идет [math]y[/math] ( [math]next_i = 0[/math] значит, что элемент [math]i[/math] последний в списке).
- [math]w_i[/math] — вес элемента с номером [math]i[/math]
- [math]r_i[/math] — ранг элемента с номером [math]i[/math]
Если есть [math]3[/math] последовательных элемента [math]x[/math] , [math]y[/math] , [math]z[/math] ( [math]next_x = y[/math] , [math]next_y = z[/math] ), то при удалении элемента [math]y[/math] нужно увеличить вес [math]z[/math] на [math]w_y[/math] . То есть [math]w_z'=w_z + w_y[/math] . После того, как мы посчитаем ответ для модифицированного списка, ранг удаленного элемента [math]y[/math] будет равен [math]r_y=r_z+w_z[/math] .
Выкидывать по [math]1[/math] элементу крайне неэффективно, но если выкидывать какую-то весомую часть, то нужно быстро пересчитывать веса элементов. Сделать это можно с помощью уже рассмотренного Join, однако необходимо наложить ограничение на множество удаляемых элементов: никакие два удаленных элемента не должны идти подряд в списке. В противном случае может образоваться цепочка из удаленных элементов произвольной длины. Веса всех элементов этой цепочки нужно будет прибавить к первому не удаленному элементу, что равносильно самой задаче List Ranking, которую мы и пытаемся решить.
Рассмотрим как именно изменять веса элементов. Построим и отсортируем по ключу [math]3[/math] таблицы:
- Таблица [math]Conn[/math] из пар [math](i, j)[/math] , где каждая пара значит, что после [math]i[/math] -ого элемента идет [math]j[/math] -ый (может быть получена из входных данных за время линейного сканирования)
- Таблица [math]W[/math] из пар [math](i, w_i)[/math] , хранящая веса элементов
- Таблица [math]D[/math] , в которой записаны удаляемые элементы
Теперь пройдемся [math]3[/math] указателями по этим таблицам. Как только встречается триплет вида [math](i, j) \in Conn[/math] , [math](i, w_i) \in W[/math] , [math](i) \in D[/math] , то добавим в новую таблицу пару [math](j, w_i)[/math] . В конце получится таблица добавок весов. Теперь из таблицы добавок и таблицы весов можно с помощью того же Join получить таблицу новых весов.
По возвращению из рекурсии аналогично пересчитываются ранги элементов. Рассмотрим [math]3[/math] таблицы:
- Таблица [math]RevConn[/math] из пар [math](j, i)[/math] , где каждая пара значит, что после [math]i[/math] -ого элемента идет [math]j[/math] -ый
- Таблица [math]W[/math] из пар [math](i, w_i)[/math] , хранящая веса элементов
- Таблица [math]R[/math] из пар [math](i, r_i)[/math] , в которой записаны ранги элементов модифицированного списка
Также пройдемся [math]3[/math] указателями по этим таблицам. Если нам встречается триплет вида [math](j, i) \in RevConn[/math] , [math](j, w_j) \in W[/math] , [math](j, r_j) \in R[/math] , то добавим пару [math](i, r_j + w_j)[/math] в таблицу новых рангов. Однако в эту таблицу попадут все элементы, у которых следующий элемент не был удален. Поэтому далее необходимо заменить лишние записи, используя таблицу старых рангов и Join.
Открытым остался вопрос о том, какие элементы удалять. В идеале было бы удалять каждый второй элемент (больше нельзя, иначе ограничение будет нарушено), но понять какой элемент четный, какой нечетный не проще чем сама задача ранжирования. Один из способов удалять элементы — вероятностный. Для каждого элемента в списке бросим монетку. После этого выбросим всех орлов, после которых в списке идет решка (делается опять же с помощью Join). В таком случае никакие два выброшенных элемента не будут идти в списке подряд.
Подсчитаем математическое ожидание количества выброшенных элементов — [math]E(D) = \sum\limits_<(i, j) \in Conn>\dfrac = \dfrac[/math]
Тогда время работы алгоритма можно оценить с помощью рекурренты [math]T(N) = T\left(\dfrac\right) + Sort(N) = \mathcal(Sort(N))[/math]
Прочитав эту статью, я вспомнил, как писал внешнюю сортировку, которая использовала O(1) внешней памяти. Функция получала бинарый файл и максимальный размер памяти, которую она могла выделить под массив:
- Разделим файл на блоки, которые помещаются в доступную память. Обозначим эти блоки Block_1, Block_2, …, Block_(S-1), Block_S. Установим P = 1.
- Читаем Block_P в память.
- Отсортируем данные в памяти и запишем назад в Block_P. Установим P = P + 1, и если P ≤ S, то читаем Block_P в память и повторяем этот шаг. Другими словами, отсортируем каждый блок файла.
- Разделим каждый блок на меньшие блоки B_1 и B_2. Каждый из таких блоков занимает половину доступной памяти.
- Читаем блок B_1 блока Block_1 в первую половину доступной памяти. Установим Q = 2.
- Читаем блок B_1 блока Block_Q во вторую половину доступной памяти.
- Объеденим массивы в памяти с помощью in-place слияния, запишем вторую половину памяти в блок B_1 блока Block_Q и установим Q = Q + 1, если Q ≤ S, читаем блок B_1 блока Block_Q во вторую половину доступной памяти и повторяем этот шаг.
- Записываем первую половину доступной памяти в блок B_1 блока Block_1. Так как мы всегда оставляли в памяти меньшую половину элементов и провели слияние со всеми блоками, то в этой части памяти хранятся M минимальных элементы всего файла.
- Читаем блок B_2 блока Block_S во вторую половину доступной памяти. Установим Q = S −1.
- Читаем блок B_2 блока Block_Q в первую половину доступной памяти.
- Объеденим массивы в памяти с помощью in-place слияния, запишем первую половину доступной памяти в блок B_2 блока Block_Q и установим Q = Q −1. Если Q ≥ 1 читаем блок B_2 блока Block_Q в первую половину доступной памяти и повторяем этот шаг.
- Записываем вторую половину доступной памяти в блок B_2 блока Block_S. Аналогично шагу 8, тут хранятся максимальные элементы всего файла.
- Начиная от блока B_2 блока Block_1 и до блока B_1 блока Block_S, определим новые блоки в файле и снова пронумеруем их Block_1 to Block_S. Разделим каждый блок на блоки B_1 и B_2. Установим P = 1.
- Читаем B_1 и B_2 блока Block_P в память. Объеденим массивы в памяти. запишем отсортированный массив назад в Block_P и установим P = P +1. Если P ≤ S, повторяем этот шаг.
- Если S > 1, возвращаемся к шагу 5. Каждый раз мы выделяем M минимальных и максимальных элементов, записываем их в начало и конец файла соответственно, а потом делаем то же самое с оставшимися элементами, пока не дойдем до середины файла.
Реализуем алгоритм на C++.
Для начала определим количество блоков и размер блока в байтах и в элементах и выделим память:
Теперь пункты 2-3 — сортируем каждый блок:
Саму сортировку мы напишем чуть позднее.
Приступим к слияниям. Нижняя половина:
И аналогично верхняя:
Перераспределяем блоки, завершаем цикл и не забываем освободить память:
Осталось реализовать функции flat_quick_sort и in_place_merge. Идею (и большую часть реализации) flat quick sort я взял в статье хабраюзера ripatti. Я только заменил median of medians (посчитал это оверкиллом в среднем случае) на median-of-nine и добавил сортировку вставками для маленьких частей массива.
Со слиянием было сложнее. Сначала я использовал заглушку, использующую O(n) памяти:
Когда я захотел заменить заглушку in-place версией, оказалось, что быстрые алгоритмы in-place слияния в большинстве своем достаточно запутанные (посмотрите, например, On optimal and efficient in place merging). Мне надо было что-то попроще, и я выбрал алгоритм из статьи A simple algorithm for in-place merging:
В вычислении , алгоритмы внешней памяти или вне ядра алгоритмов являются алгоритмами , которые предназначены для данных процесса , которые являются слишком большими , чтобы вписаться в компьютере основной память одновременно. Такие алгоритмы должны быть оптимизированы для эффективного извлечения и доступа к данным, хранящимся в медленной основной памяти ( вспомогательной памяти ), такой как жесткие диски или ленточные накопители , или когда память находится в компьютерной сети . [1] [2] Алгоритмы внешней памяти анализируются в модели внешней памяти .
Что нужно знать перед началом?
По долгу службы я собеседовал студентов для программ стажировки и обучающих курсов. Ни один из тех студентов не знал четкого определения «О»-большое. Поэтому я крайне советую обратиться за таким определением к математической литературе. Базовые сведения в популярной форме вы найдете в цикле статей «Введение в анализ сложности алгоритмов»
Smoothed analysis
Скорее всего, вы впервые слышите это словосочетание. Что неудивительно, т.к. Smoothed анализ появился по меркам математики недавно: в 2001 году. Разумеется это подразумевает, что идея не лежит на поверхности. Я буду считать, что вам уже известен анализ худшего случая, анализ среднего, а так же сравнительно бесполезный анализ лучшего случая: и того три очевидных варианта. Так вот smoothed analysis — четвертый вариант.
Прежде чем объяснить зачем он понадобился, проще сперва уточнить зачем придумали предыдущие три. Я знаю три ключевых ситуации, в которых асимптотический анализ выручает:
— Во время защиты диссертации по математике.
— Когда надо понять почему один алгоритм быстрее другого или потребляет меньше памяти.
— Когда надо предсказать рост времени работы или используемой памяти алгоритма в зависимости от роста размера входа.
Последний пункт справедлив с оговорками. Из-за того, что реальное железо устроено сложно, теоретическая оценка характера роста будет работать как оценка снизу для того, что вы увидите в эксперименте. Я сознательно опускаю расшифровку слова «сложно», т.к. она займет не мало времени. Поэтому я надеюсь, что читатель понимающе кивнет и не станет меня допрашивать.
Для наших целей важно уточнить, что асимптотическая оценка не говорит какой алгоритм работает быстрее, и уж тем более ничего не говорит о конкретной реализации. Асимптотика предсказывает общий вид функции роста, но не абсолютные значения. Алгоритмы быстрого умножения — хрестоматийный пример такой ситуации: метод Карацубы обгоняет наивный только после достижения длины в «несколько десятков знаков», а метод Шёнхаге — Штрассена обгоняет метод Карацубы при длине «от 10 000 до 40 000 десятичных знаков». Невозможно сделать подобные выводы без эксперимента, если смотреть только на асимптотику.
С другой стороны имея на руках результаты эксперимента нельзя сделать вывод, что подобная тенденция будет сохраняться всегда или что нам не повезло с входными данными. В этой ситуации и выручает асимптотический анализ, который помогает доказать, почему алгоритм сортировка Хоара быстрее пузырька. Другими словами одновременно необходимы как экспериментальные данные, так и теоретические результаты для полного понимания и душевного спокойствия.
Это объясняет наличие одной асимптотической оценки, но зачем остальные? Всё просто. Допустим у двух алгоритмов асимптотическая оценка худшего случая одинакова, а результаты экспериментов говорят об явных преимуществах одного над другим. В такой ситуации придется анализировать средний случай в поисках разницы, которая всё объяснит. Именно это происходит при сравнении сортировки Хоара и пузырька, у которых асимптотически одинаковый худший случай, но разный средний.
Smoothed оценка находится посередине между средним и худшим случаем. Она записывается так:
, где некоторая небольшая константа, множество возможных входных данных размера , функция возвращающая время (или память), которое алгоритм затратит на обработку конкретных данных, — математическое ожидание, а скобки разные для удобства.
Говоря простым языком smooth оценка означает, что не существует достаточно большого непрерывного куска данных, на которых алгоритм будет работать в среднем медленнее, чем . Таким образом smoothed оценка сильнее средней, но слабее худшей. Очевидно что варьируя можно смещать её от среднего к максимуму.
Поскольку определение не тривиально я нарисовал картинку для понимания:
Тут нарисовано распределение времени по множеству входных данных для некоторого n. Красные области — худший случай, желтые — средний, а голубые — лучший. Для левого множества средняя и smoothed оценка будут примерно одинаковыми. А вот для правого smoothed оценка будет ближе к худшему случаю. Для обоих множеств smoothed оценка точнее описывает поведение алгоритма. Если представить, что оба рисунка соответствуют одной и той же задаче, но разным алгоритмам, получается интересная ситуация. Оценка лучшего, худшего и среднего случая у них одинаковая. Но на практике левый алгоритм будет работать по ощущениям лучше, т.к. на правый намного проще устроить алгоритмическую атаку.
Подробнее об этом можно прочитать в статье «Smoothed Analysis of Algorithms». В ней применяют этот подход для анализа симплекс метода. По ссылкам можно найти и другие статьи.
Читайте также: