Алгоритмы во внешней памяти. Базовые конструкции — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
== Модель вычислений во внешней памяти ==  
 
== Модель вычислений во внешней памяти ==  
Обычно оценка сложности рассматриваемых алгоритмов происходит в модели под названием ''RAM-машина''. Это означает, что у нас есть оперативная память, из которой мы можем читать и писать произвольную ячейку памяти за время элементарной операции. Таким образом время вычислительных операций и операций с памятью приравниваются, что сильно упрощает анализ.  
+
Обычно оценка сложности рассматриваемых алгоритмов происходит в модели под названием ''RAM-машина''<ref>[[wikipedia:Random-access_machine |Wikipedia {{---}} Random-access machine]]</ref>. Это означает, что у нас есть оперативная память, из которой мы можем читать и писать произвольную ячейку памяти за время элементарной операции. Таким образом время вычислительных операций и операций с памятью приравнивается, что сильно упрощает анализ.  
  
Но в таком случае размер данных, с которыми мы работаем, должен помещаться в оперативную память. Предположим, что ее размер порядка <tex>10-100</tex> GB, а обработать нам нужно порядка <tex>10</tex> TB информации. Очевидно, что необходимо использовать какую-то внешнюю память, например {{---}} жесткий диск. Хотя диски существенно дешевле  
+
Но в таком случае размер данных, с которыми мы работаем, должен помещаться в оперативную память. Предположим, что ее размер порядка <tex>10-100</tex> GB, а обработать нужно порядка <tex>10</tex> TB информации. Очевидно, что необходимо использовать какую-то внешнюю память, например {{---}} жесткий диск. Хотя диски существенно дешевле  
 
[[Файл:External memory.png|240px|thumb|Оперативная память слева вмещает <tex>\dfrac{M}{B}</tex> блоков размера <tex>B</tex>. Внешняя память справа неограниченна.]]  
 
[[Файл:External memory.png|240px|thumb|Оперативная память слева вмещает <tex>\dfrac{M}{B}</tex> блоков размера <tex>B</tex>. Внешняя память справа неограниченна.]]  
оперативной памяти и имеют высокую емкость, они гораздо медленнее оперативной памяти из-за механического построения считывания. Для сравнения, время обращения к оперативной памяти порядка <tex>100</tex> ns, а к HDD порядка <tex>10</tex> ms. Разница колоссальная (<tex>10^{-7}</tex> s и <tex>10^{-2}</tex> s). Однако, основное время тратится на позиционирование головки жесткого диска, из-за чего разрыв в скорости последовательного чтения не такой большой. Из оперативной памяти можно читать порядка <tex>10</tex> GB/s, с HDD {{---}} порядка <tex>100</tex> MB/s.
+
оперативной памяти и имеют высокую емкость, они гораздо медленнее из-за механического построения считывания. Для сравнения, время обращения к оперативной памяти порядка <tex>100</tex> ns, а к HDD {{---}} порядка <tex>10</tex> ms (<tex>10^{-7}</tex> s и <tex>10^{-2}</tex> s). Однако, основное время тратится на позиционирование головки жесткого диска, из-за чего разрыв в скорости последовательного чтения не такой большой. Из оперативной памяти можно читать со скоростью порядка <tex>10</tex> GB/s, с HDD {{---}} порядка <tex>100</tex> MB/s.
  
Из-за описанного выше, для оценки сложности алгоритмов во внешней памяти была предложена другая модель. Модель говорит следующее {{---}} у нас есть какая-то внешняя память и процессор со своей внутренней памятью. Внутренняя память ограничена и имеет размер порядка <tex>M</tex> машинных слов. Внешняя память считается безграничной в рамках рассматриваемой задачи, то есть имеет размер хотя бы порядка <tex>N</tex> машинных слов, где <tex>N</tex> {{---}} размер задачи. Чтение и запись из внешней памяти происходит блоками последовательных данных размера <tex>B</tex> {{---}} машинных слов. В качестве меры сложности принимается количество операций ввода-вывода, которые выполняет алгоритм, где одна операция ввода-вывода это либо чтение из внешней памяти одного блока размера <tex>B</tex>, либо запись.
+
Из-за описанного выше, для оценки сложности алгоритмов во внешней памяти была предложена другая модель. Модель гласит следующее: существует какая-то внешняя память и процессор со своей внутренней памятью. Внутренняя память ограничена и имеет размер порядка <tex>M</tex> машинных слов. Внешняя память считается безграничной в рамках рассматриваемой задачи, то есть имеет размер хотя бы порядка <tex>N</tex> машинных слов, где <tex>N</tex> {{---}} размер задачи. Чтение и запись из внешней памяти происходит блоками последовательных данных размера <tex>B</tex> машинных слов. В качестве меры сложности принимается количество операций ввода-вывода, которые выполняет алгоритм, где одна операция ввода-вывода это либо чтение из внешней памяти одного блока размера <tex>B</tex>, либо запись.
  
У данной модели есть один существенный недостаток {{---}} мы никак не учитываем время, которое тратится на вычисления, а считаем только ''IO-complexity''. Из-за этого многие задачи в данной модели решаются быстрее, чем в модели с ''RAM-машиной''. Например, прочитав какой-то блок, далее мы имеем право произвести экспоненциальный по сложности перебор и это никак не будет учитываться. Поэтому нужно иметь в виду, что данная модель стремится эффективно использовать жесткий диск, а не балансировать между использованием процессора и жесткого диска.
+
У данной модели есть один существенный недостаток: мы никак не учитываем время, которое тратится на вычисления, а считаем только обращения к диску. Из-за этого многие задачи в данной модели решаются быстрее, чем в модели с ''RAM-машиной''. Например, прочитав какой-то блок, далее мы имеем право произвести экспоненциальный по сложности перебор, и это никак не будет учитываться. Поэтому нужно иметь в виду, что данная модель стремится эффективно использовать жесткий диск, а не балансировать между использованием процессора и жесткого диска.
  
 
== Размер блока ==
 
== Размер блока ==
Так как время позиционирования головки внешнего диска весьма непредсказуемо, то необходимо взять размер блока таким, чтобы время чтения самих данных было гораздо больше, чем время позиционирования к этим данным. То есть должно выполняться <tex>seek\_time \leqslant read\_time</tex>. Если <tex>read\_time = 100</tex> MB/s, то <tex>B \geqslant 1</tex> MB. На практике, размер блока нужно брать больше чем <tex>1</tex> MB (около <tex>8-16</tex> MB), так как тогда время позиционирования станет существенно меньше времени чтения.
+
Так как время позиционирования головки внешнего диска весьма непредсказуемо, то необходимо взять размер блока таким, чтобы время чтения самих данных было гораздо больше, чем время позиционирования к этим данным. То есть должно выполняться <tex>seek\_time \leqslant read\_time</tex>. Если <tex>read\_time = 100</tex> MB/s, <tex>seek\_time = 10</tex> ms, то <tex>B \geqslant 1</tex> MB. На практике, размер блока нужно брать больше чем <tex>1</tex> MB (около <tex>8-16</tex> MB), так как тогда время позиционирования станет существенно меньше времени чтения.
  
== Примитивные задачи ==
+
== Базовые задачи ==
 
=== Scan ===
 
=== Scan ===
Рассмотрим следующую задачу {{---}} на диске записаны <tex>N</tex> чисел и нужно найти их сумму (например, по какому-нибудь модулю). Очевидно, что эта задача равносильна просто считыванию данных с диска. Сложность линейного сканирования данных с диска это <tex>\left\lceil\dfrac{N}{B}\right\rceil = Scan(N)</tex>. Важно заметить, что из-за округления в общем случае <tex>\sum\limits_{i = 1}^{k}Scan(N_i) \neq Scan(\sum\limits_{i = 1}^{k}N_i)</tex>.
+
На диске записаны <tex>N</tex> чисел, нужно найти их сумму (например, по какому-нибудь модулю). Очевидно, что эта задача равносильна просто считыванию с диска. Сложность линейного сканирования данных с диска {{---}} <tex>\left\lceil\dfrac{N}{B}\right\rceil = Scan(N)</tex>. Важно заметить, что из-за округления, в общем случае <tex>\sum\limits_{i = 1}^{k}Scan(N_i) \neq Scan\left(\sum\limits_{i = 1}^{k}N_i\right)</tex>.
  
 
=== Слияние упорядоченных последовательностей ===
 
=== Слияние упорядоченных последовательностей ===
 +
Пусть имеется две упорядоченные последовательности размера <tex>N_1</tex> и <tex>N_2</tex> соответственно. Чтобы их слить, достаточно завести во внутренней памяти <tex>3</tex> блока. В первые <tex>2</tex> мы будем читать сами последовательности, а в третий {{---}} записывать результат слияния, используя [[Сортировка_слиянием#Слияние_двух_массивов | стандартный алгоритм]] с <tex>2</tex> указателями. Как только какой-то из указателей дошел до конца блока, необходимо считывать следующий, а когда буфер с результатом слияния заполнился {{---}} необходимо записывать его во внешнюю память и очищать. Сложность алгоритма {{---}} <tex>\mathcal{O}(Scan(N_1 + N_2))</tex>
  
Пусть имеется две упорядоченные последовательности размера <tex>N_1</tex> и <tex>N_2</tex> соответственно. Чтобы их слить, можно завести во внутренней памяти 3 блока. В первые 2 мы будем читать сами последовательности, а в третий будем записывать результат слияния, используя стандартный алгоритм с 2 указателями. Как-то только какой-то из указателей дошел до конца блока необходимо считывать следующий, а когда буфер с результатом слияния заполнился {{---}} необходимо записывать его во внешнюю память и очищать. Сложность алгоритма {{---}} <tex>\mathcal{O}(Scan(N_1 + N_2))</tex>
+
=== Сортировка ===
 +
Поскольку мы легко умеем выполнять слияние упорядоченных последовательностей, логичным шагом будет рассмотреть сортировку во внешней памяти. Рассмотрим некоторую модификацию алгоритма [[Сортировка слиянием|Merge sort]]. В стандартном алгоритме все элементы разбиваются на пары, после чего сливаются в упорядоченные последовательности длины <tex>2</tex>, те в свою очередь сливаются в последовательности длины <tex>4</tex> и так далее (для простоты описания будем считать, что <tex>N</tex> и <tex>B</tex> это степени двойки). Во внешней памяти не выгодно начинать с последовательностей длины <tex>1</tex>, так как чтение происходит блоками длины <tex>B</tex>. Вместо этого можно целиком считать блок и отсортировать его во внутренней памяти. Тогда количество листьев в дереве сортировки будет не <tex>N</tex>, а <tex>\dfrac{N}{B}</tex>. Помимо этого, гораздо выгоднее сливать больше чем <tex>2</tex> списка за раз, чтобы уменьшить высоту дерева сортировки. Так как оперативная память размера <tex>M</tex>, то можно сливать сразу <tex>\dfrac{M}{B}</tex> списков. Итого, на каждом уровне дерева сортировки мы выполняем <tex>\mathcal{O}\left(\dfrac{N}{B}\right)</tex> операций и итоговая сложность {{---}} <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{B}\right) = Sort(N)</tex>.
  
=== Сортировка ===
+
[[Файл:External sort.png]]
Поскольку мы легко умеем выполнять слияние упорядоченных последовательностей, то логичным шагом будет рассмотреть сортировку во внешней памяти. Рассмотрим некоторую модификацию алгоритма Merge sort. В стандартном алгоритме все элементы разбиваются на пары, после чего сливаются в упорядоченные последовательности длины 2, те в свою очередь сливаются в последовательности длины 4 и т.д. (для простоты в данном алгоритме будем считать что N это степень двойки). Во внешней памяти не выгодно начинать с последовательностей длины 1, так как чтение происходит блоками длины B. Вместо этого можно целиком считать блок и отсортировать его во внутренней памяти. Тогда количество листьев в дереве сортировки будет не N, а <tex>\dfrac{N}{B}</tex>. Помимо этого, гораздо выгоднее сливать больше чем 2 списка за раз, чтобы уменьшить высоту дерева сортировки. Так как оперативная память размера M, то можно сливать сразу <tex>\dfrac{M}{B}</tex> списков. Итого, на каждом уровне дерева сортировки мы выполняем <tex>\mathcal{O}\left(\dfrac{N}{B}\right)</tex> операций и итоговая сложность {{---}} <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{B}\right) = Sort(N)</tex>.
 
  
В качестве небольшой оптимизации можно в начале сортировать во внутренней памяти последовательности длины M, а не B. Хотя итоговая сложность и станет <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{M}\right)</tex>, но это уменьшит высоту дерева сортировки всего на единицу, что не очень сильно скажется на времени работы.
+
В качестве небольшой оптимизации можно в начале сортировать во внутренней памяти последовательности длины <tex>M</tex>, а не <tex>B</tex>. Хотя итоговая сложность и станет <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{M}\right)</tex>, но это уменьшит высоту дерева сортировки всего на единицу, что не очень сильно скажется на времени работы.
  
 
=== Join ===
 
=== Join ===
Рассмотрим следующую задачу {{---}} пусть у нас во внешней памяти есть 2 последовательности вида <tex>(ключ, значение)</tex>. Первая последовательность имеет вид <tex>(k_i, a_{k_i})</tex>, вторая {{---}} <tex>(l_j, b_{l_j})</tex> и мы хотим получить последовательность вида <tex>(i, a_i, b_i)</tex> (не умоляя общности считаем что <tex>(k_1 \dots k_N)</tex> и <tex>(l_1 \dots l_N)</tex> являются перестановками чисел от 1 до N). Очевидно, что задача решается просто сортировками последовательностей по первому аргументу с последующим проходом по ним 2 указателями. Поэтому сложность алгоритма {{---}} <tex>Sort(N)</tex>.
+
Пусть во внешней памяти есть <tex>2</tex> таблицы вида <tex>(key, value)</tex>. Первая таблица имеет вид <tex>(k_i, a_{k_i})</tex>, вторая {{---}} <tex>(l_j, b_{l_j})</tex>. Необходимо получить таблицу вида <tex>(i, a_i, b_i)</tex> (не умаляя общности считаем, что <tex>(k_1 \dots k_N)</tex> и <tex>(l_1 \dots l_N)</tex> являются перестановками чисел от <tex>1</tex> до <tex>N</tex>). Очевидно, что задача решается просто сортировками таблиц по ключу с последующим проходом по ним <tex>2</tex> указателями. Поэтому сложность алгоритма {{---}} <tex>Sort(N)</tex>.
 +
 
 +
Данный алгоритм хоть и крайне прост, является одним из ключевых примитивов. Когда необходимо совершить какую-то операцию над разбросанными по памяти данными, часто задача сводится к последовательности нескольких Join'ов.  
  
 
== List Ranking ==
 
== List Ranking ==
Данная задача заключается в следующем {{---}} нам дан односвязный список, то есть для каждого элемента мы знаем, какой идет следующим за ним в списке. Необходимо для каждого элемента определить, каким он является по счету с конца списка. Расстояние до конца списка будем называть ''рангом'' элемента. Не смотря на простоту задачи в ''RAM-машине'', во внешней памяти задача имеет нетривиальное решение. Из-за того что во внешней памяти все данные лежат хаотично, мы не можем просто пройтись по списку, это может потребовать слишком много операций ввода-вывода.
 
  
Попробуем решить задачу следующим способом {{---}} выкинем из списка какую-то часть элементов, после чего рекурсивно посчитаем ответ для полученного списка, а затем, зная промежуточный ответ, восстановим ответ для исходной задачи. Первая проблема с которой мы сталкиваемся {{---}} это то, что в модифицированном списке ранги элементов отличаются. Чтобы решить эту проблему, решим более общую задачу. Будем считать, что у каждого элемента есть вес <tex>w_i</tex>, а ранг элемента это сумма весов до конца списка. Для решения исходной задачи в самом начале присвоим каждому элементу вес 1.  
+
[[Файл:List.png|300px|thumb|Входные данные и ответ]]
 +
Данная задача заключается в следующем: дан односвязный список, то есть для каждого элемента известно, какой идет следующим за ним. Необходимо для каждого элемента определить, каким он является по счету с конца списка. Расстояние до конца списка будем называть ''рангом'' элемента. Несмотря на простоту задачи в ''RAM-машине'', во внешней памяти задача имеет нетривиальное решение. Из-за того что все данные лежат хаотично, мы не можем просто пройтись по списку, это может потребовать слишком много операций ввода-вывода.
 +
 
 +
=== Идея ===
 +
 
 +
Решим задачу следующим способом: выкинем из списка какую-то часть элементов, после чего рекурсивно посчитаем ответ для полученного списка. Затем, зная промежуточный ответ, восстановим ответ для исходной задачи. Первая проблема {{---}} в модифицированном списке ранги элементов отличаются. Чтобы решить эту проблему, рассмотрим более общую задачу. Будем считать, что у каждого элемента есть вес, а ранг элемента {{---}} это сумма весов до конца списка. Для решения исходной задачи в самом начале присвоим каждому элементу вес <tex>1</tex>.  
 +
 
 +
=== Обозначения ===
  
Теперь, если у нас есть 3 последовательных элемента x, y, z (<tex>next[x] = y</tex>, <tex>next[y] = z</tex>), то при удалении элемента <tex>y</tex> нужно увеличить вес <tex>z</tex> на <tex>w_y</tex>. То есть <tex>w_z'=w_z + w_y</tex>. После того, как мы посчитаем ответ для модифицированного списка, ранг удаленного элемента <tex>y</tex> будет равен <tex>r_y=r_z+w_z</tex>.
+
* <tex>next</tex> {{---}} массив входных данных. <tex>next_x = y</tex> означает, что после элемента <tex>x</tex> идет <tex>y</tex> (<tex>next_i = 0</tex> значит, что элемент <tex>i</tex> последний в списке).  
 +
* <tex>w_i</tex> {{---}} вес элемента с номером <tex>i</tex>
 +
* <tex>r_i</tex> {{---}} ранг элемента с номером <tex>i</tex>
  
Выкидывать по 1 элементу крайне неэффективно, но если выкидывать какую-то весомую часть, то нужно быстро пересчитывать веса элементов. Сделать это можно с помощью уже рассмотренного Join, однако необходимо наложить ограничение на множество удаляемых элементов: никакие два удаленных элемента не должны идти подряд в списке. В противном случае может образоваться цепочка из удаленных элементов произвольной длины. Веса всех элементов этой цепочки нужно будет прибавить к первому не удаленному элементу, что равносильно самой задаче List Ranking, которую мы и пытаемся решить.
+
=== Удаление элементов и восстановление рангов ===
  
Рассмотрим как именно изменять веса элементов. Построим и отсортируем по 1 элементу 3 таблицы:
+
Если есть <tex>3</tex> последовательных элемента <tex>x</tex>, <tex>y</tex>, <tex>z</tex> (<tex>next_x = y</tex>, <tex>next_y = z</tex>), то при удалении элемента <tex>y</tex> нужно увеличить вес <tex>z</tex> на <tex>w_y</tex>. То есть <tex>w_z'=w_z + w_y</tex>. После того, как мы посчитаем ответ для модифицированного списка, ранг удаленного элемента <tex>y</tex> будет равен <tex>r_y=r_z+w_z</tex>.
  
1) Таблица Conn из пар <tex>(i, j)</tex>, где каждая пара значит что после i-ого элемента идет j-ый
+
[[Файл:List-ranking-wr.png|400px|Удаление элемента и восстановление ответа]]
  
2) Таблица W из пар <tex>(i, w_i)</tex>, хранящая веса элементов
+
Выкидывать по <tex>1</tex> элементу крайне неэффективно, но если выкидывать какую-то весомую часть, то нужно быстро пересчитывать веса элементов. Сделать это можно с помощью уже рассмотренного Join, однако необходимо наложить ограничение на множество удаляемых элементов: никакие два удаленных элемента не должны идти подряд в списке. В противном случае может образоваться цепочка из удаленных элементов произвольной длины. Веса всех элементов этой цепочки нужно будет прибавить к первому не удаленному элементу, что равносильно самой задаче List Ranking, которую мы и пытаемся решить.
  
3) Таблица D, в которой записаны удаляемые элементы
+
Рассмотрим как именно изменять веса элементов. Построим и отсортируем по ключу <tex>3</tex> таблицы:
  
Теперь пройдемся 3 указателями по этим таблицам, и если нам встречается триплет вида <tex>(i, j) \in Conn</tex>, <tex>(i, w_i) \in W</tex>, <tex>(i) \in D</tex>, то добавим пару <tex>(j, w_i)</tex>. У нас получится таблица добавок. Теперь из таблицы добавок и таблицы весов можно с помощью того же Join получить таблицу новых весов.
+
# Таблица <tex>Conn</tex> из пар <tex>(i, j)</tex>, где каждая пара значит, что после <tex>i</tex>-ого элемента идет <tex>j</tex>-ый (может быть получена из входных данных за время линейного сканирования)
 +
# Таблица <tex>W</tex> из пар <tex>(i, w_i)</tex>, хранящая веса элементов
 +
# Таблица <tex>D</tex>, в которой записаны удаляемые элементы
  
По возвращению из рекурсии аналогично пересчитываются ранги элементов. Рассмотрим 3 таблицы:
+
Теперь пройдемся <tex>3</tex> указателями по этим таблицам. Как только встречается триплет вида <tex>(i, j) \in Conn</tex>, <tex>(i, w_i) \in W</tex>, <tex>(i) \in D</tex>, то добавим в новую таблицу пару <tex>(j, w_i)</tex>. В конце получится таблица добавок весов. Теперь из таблицы добавок и таблицы весов можно с помощью того же Join получить таблицу новых весов.
  
1) Таблица RevConn из пар <tex>(j, i)</tex>, где каждая пара значит что после i-ого элемента идет j-ый
+
По возвращению из рекурсии аналогично пересчитываются ранги элементов. Рассмотрим <tex>3</tex> таблицы:
  
2) Таблица W из пар <tex>(i, w_i)</tex>, хранящая веса элементов
+
# Таблица <tex>RevConn</tex> из пар <tex>(j, i)</tex>, где каждая пара значит, что после <tex>i</tex>-ого элемента идет <tex>j</tex>-ый
 +
# Таблица <tex>W</tex> из пар <tex>(i, w_i)</tex>, хранящая веса элементов
 +
# Таблица <tex>R</tex> из пар <tex>(i, r_i)</tex>, в которой записаны ранги элементов модифицированного списка
  
3) Таблица R из пар <tex>(i, r_i)</tex>, в которой записаны ранги элементов модифицированного списка
+
Также пройдемся <tex>3</tex> указателями по этим таблицам. Если нам встречается триплет вида <tex>(j, i) \in RevConn</tex>, <tex>(j, w_j) \in W</tex>, <tex>(j, r_j) \in R</tex>, то добавим пару <tex>(i, r_j + w_j)</tex> в таблицу новых рангов. Однако в эту таблицу попадут все элементы, у которых следующий элемент не был удален. Поэтому далее необходимо заменить лишние записи, используя таблицу старых рангов и Join.
  
Также пройдемся 3 указателями по этим таблицам, и если нам встречается триплет вида <tex>(i, j) \in Conn</tex>, <tex>(i, w_i) \in W</tex>, <tex>(i, r_i) \in D</tex>, то добавим пару <tex>(j, r_i + w_i)</tex> в таблицу новых рангов. Однако в эту таблицу могли попасть лишние записи, которые надо заменить используя таблицу старых рангов и Join.
+
=== Выбор удаляемых элементов ===
  
Открытым остался только вопрос какие элементы удалять. В идеале было бы удалять каждый второй элемент (больше нельзя, иначе ограничение будет нарушено), но понять какой элемент четный, какой нечетный не проще чем сама задача ранжирования. Один из способов удалять элементы вероятностный. Для каждого элемента в списке бросим монетку. После этого выбросим всех орлов, после которых в списке идет решка (делается опять же с помощью Join). В таком случае никакие два выброшенных элемента не будут идти в списке подряд.  
+
Открытым остался вопрос о том, какие элементы удалять. В идеале было бы удалять каждый второй элемент (больше нельзя, иначе ограничение будет нарушено), но понять какой элемент четный, какой нечетный не проще чем сама задача ранжирования. Один из способов удалять элементы {{---}} вероятностный. Для каждого элемента в списке бросим монетку. После этого выбросим всех орлов, после которых в списке идет решка (делается опять же с помощью Join). В таком случае никакие два выброшенных элемента не будут идти в списке подряд.  
  
Подсчитаем матожидание выброшенных элементов {{---}} <tex>E(D) = \sum\limits_{(i, j) \in Conn}\frac{1}{4} = \frac{N}{4}</tex>
+
Подсчитаем [[Математическое ожидание случайной величины| математическое ожидание]] количества выброшенных элементов {{---}} <tex>E(D) = \sum\limits_{(i, j) \in Conn}\dfrac{1}{4} = \dfrac{N}{4}</tex>
  
 
Тогда время работы алгоритма можно оценить с помощью рекурренты <tex>T(N) = T\left(\dfrac{3N}{4}\right) + Sort(N) = \mathcal{O}(Sort(N))</tex>
 
Тогда время работы алгоритма можно оценить с помощью рекурренты <tex>T(N) = T\left(\dfrac{3N}{4}\right) + Sort(N) = \mathcal{O}(Sort(N))</tex>
 +
 +
== См. также ==
 +
* [[Cache-oblivious алгоритмы]]
 +
* [[B-дерево]]
 +
* [[B+-дерево]]
 +
 +
== Примeчания ==
 +
<references/>
 +
 +
== Источники информации ==
 +
* [https://www.lektorium.tv/course/22905 Максим Бабенко {{---}} Курс алгоритмов во внешней памяти.]
 +
* [https://en.wikipedia.org/wiki/External_memory_algorithm Wikipedia {{---}} External memory algorithm.]
 +
 +
[[Категория:Алгоритмы]]
 +
[[Категория:Алгоритмы во внешней памяти]]

Текущая версия на 19:34, 4 сентября 2022

Модель вычислений во внешней памяти

Обычно оценка сложности рассматриваемых алгоритмов происходит в модели под названием RAM-машина[1]. Это означает, что у нас есть оперативная память, из которой мы можем читать и писать произвольную ячейку памяти за время элементарной операции. Таким образом время вычислительных операций и операций с памятью приравнивается, что сильно упрощает анализ.

Но в таком случае размер данных, с которыми мы работаем, должен помещаться в оперативную память. Предположим, что ее размер порядка [math]10-100[/math] GB, а обработать нужно порядка [math]10[/math] TB информации. Очевидно, что необходимо использовать какую-то внешнюю память, например — жесткий диск. Хотя диски существенно дешевле

Оперативная память слева вмещает [math]\dfrac{M}{B}[/math] блоков размера [math]B[/math]. Внешняя память справа неограниченна.

оперативной памяти и имеют высокую емкость, они гораздо медленнее из-за механического построения считывания. Для сравнения, время обращения к оперативной памяти порядка [math]100[/math] ns, а к HDD — порядка [math]10[/math] ms ([math]10^{-7}[/math] s и [math]10^{-2}[/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]seek\_time \leqslant read\_time[/math]. Если [math]read\_time = 100[/math] MB/s, [math]seek\_time = 10[/math] ms, то [math]B \geqslant 1[/math] MB. На практике, размер блока нужно брать больше чем [math]1[/math] MB (около [math]8-16[/math] MB), так как тогда время позиционирования станет существенно меньше времени чтения.

Базовые задачи

Scan

На диске записаны [math]N[/math] чисел, нужно найти их сумму (например, по какому-нибудь модулю). Очевидно, что эта задача равносильна просто считыванию с диска. Сложность линейного сканирования данных с диска — [math]\left\lceil\dfrac{N}{B}\right\rceil = Scan(N)[/math]. Важно заметить, что из-за округления, в общем случае [math]\sum\limits_{i = 1}^{k}Scan(N_i) \neq Scan\left(\sum\limits_{i = 1}^{k}N_i\right)[/math].

Слияние упорядоченных последовательностей

Пусть имеется две упорядоченные последовательности размера [math]N_1[/math] и [math]N_2[/math] соответственно. Чтобы их слить, достаточно завести во внутренней памяти [math]3[/math] блока. В первые [math]2[/math] мы будем читать сами последовательности, а в третий — записывать результат слияния, используя стандартный алгоритм с [math]2[/math] указателями. Как только какой-то из указателей дошел до конца блока, необходимо считывать следующий, а когда буфер с результатом слияния заполнился — необходимо записывать его во внешнюю память и очищать. Сложность алгоритма — [math]\mathcal{O}(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{N}{B}[/math]. Помимо этого, гораздо выгоднее сливать больше чем [math]2[/math] списка за раз, чтобы уменьшить высоту дерева сортировки. Так как оперативная память размера [math]M[/math], то можно сливать сразу [math]\dfrac{M}{B}[/math] списков. Итого, на каждом уровне дерева сортировки мы выполняем [math]\mathcal{O}\left(\dfrac{N}{B}\right)[/math] операций и итоговая сложность — [math]\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{B}\right) = Sort(N)[/math].

External sort.png

В качестве небольшой оптимизации можно в начале сортировать во внутренней памяти последовательности длины [math]M[/math], а не [math]B[/math]. Хотя итоговая сложность и станет [math]\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{M}\right)[/math], но это уменьшит высоту дерева сортировки всего на единицу, что не очень сильно скажется на времени работы.

Join

Пусть во внешней памяти есть [math]2[/math] таблицы вида [math](key, value)[/math]. Первая таблица имеет вид [math](k_i, a_{k_i})[/math], вторая — [math](l_j, b_{l_j})[/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'ов.

List Ranking

Входные данные и ответ

Данная задача заключается в следующем: дан односвязный список, то есть для каждого элемента известно, какой идет следующим за ним. Необходимо для каждого элемента определить, каким он является по счету с конца списка. Расстояние до конца списка будем называть рангом элемента. Несмотря на простоту задачи в 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] таблицы:

  1. Таблица [math]Conn[/math] из пар [math](i, j)[/math], где каждая пара значит, что после [math]i[/math]-ого элемента идет [math]j[/math]-ый (может быть получена из входных данных за время линейного сканирования)
  2. Таблица [math]W[/math] из пар [math](i, w_i)[/math], хранящая веса элементов
  3. Таблица [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] таблицы:

  1. Таблица [math]RevConn[/math] из пар [math](j, i)[/math], где каждая пара значит, что после [math]i[/math]-ого элемента идет [math]j[/math]-ый
  2. Таблица [math]W[/math] из пар [math](i, w_i)[/math], хранящая веса элементов
  3. Таблица [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{1}{4} = \dfrac{N}{4}[/math]

Тогда время работы алгоритма можно оценить с помощью рекурренты [math]T(N) = T\left(\dfrac{3N}{4}\right) + Sort(N) = \mathcal{O}(Sort(N))[/math]

См. также

Примeчания

Источники информации