286
правок
Изменения
м
Нет описания правки
Из-за описанного выше, для оценки сложности алгоритмов во внешней памяти была предложена другая модель. Модель говорит следующее {{---}} у нас есть какая-то внешняя память и процессор со своей внутренней памятью. Внутренняя память ограничена и имеет размер порядка <tex>M</tex> машинных слов. Внешняя память имеет размер хотя бы порядка <tex>N</tex> машинных слов, где <tex>N</tex> {{---}} размер рассматриваемой задачи. Чтение и запись из внешней памяти происходит блоками последовательных данных размера <tex>B</tex> {{---}} машинных слов. В качестве меры сложности принимается количество операций ввода-вывода, которые выполняет алгоритм, где одна операция ввода-вывода это либо чтение из внешней памяти одного блока размера <tex>B</tex>, либо запись.
У данной модели есть один существенный недостаток {{---}} мы никак не учитываем время, которое тратится на вычисления, а считаем только ''IO-complexity''. Из-за этого многие задачи в данной модели решаются быстрее, чем в модели с ''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), так как тогда время позиционирования станет не просто существенно меньше времени чтения.
== Примитивные задачи ==
=== 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_nk_N)</tex> и <tex>(l_1 \dots l_nl_N)</tex> являются перестановками чисел от 1 до nN). Очевидно, что задача решается просто сортировками последовательностей по первому аргументу с последующим проходом по ним 2 указателями. Поэтому сложность алгоритма {{---}} <tex>Sort(nN)</tex>.
== List Ranking ==
3) Таблица R из пар <tex>(i, r_i)</tex>, в которой записаны ранги элементов модифицированного списка
Также пройдемся 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). В таком случае никакие два выброшенных элемента не будут идти в списке подряд.
