Что мотивирует модель RAM?
Похоже, что большая часть сегодняшнего анализа алгоритмов проводится в моделях с постоянным произвольным доступом, таких как модель слова RAM. Я мало что знаю о физике, но из популярных источников я слышал, что должно быть ограничение на объем хранилища информации и на скорость перемещения информации, поэтому ОЗУ не кажется физически реализуемым. У современных компьютеров есть все эти уровни кеширования, что, я бы сказал, делает их не очень похожими на RAM. Так почему теоретические алгоритмы должны быть установлены в ОЗУ?
Ответы
Позвольте мне взглянуть на это иначе, чем на vonbrand. Все, что вы сказали, верно: модель RAM нереалистична по ряду причин, и хотя можно защитить различные ее аспекты, такая защита на самом деле не затрагивает суть вопроса.
Суть вопроса - и ответ на ваш вопрос - в том, что модель RAM - лучшее, что у нас есть. По сравнению с другими общепринятыми моделями, он более точно моделирует реальные вычисления. В частности, причина, по которой мы приняли модель RAM, была в первую очередь реакцией на машины Тьюринга, поскольку мы обнаружили, что использование машин Тьюринга приводит к проблемам, которые искусственно трудно решить с точки зрения временной сложности. Модель RAM явно решает эту вопиющую проблему, и поэтому она была принята, хотя и остается далекой от совершенства.
Классическим примером, иллюстрирующим вопиющую проблему с машинами Тьюринга, является проблема равенства строк: заданный ввод
$$ w_1 \# w_2$$
где $w_1, w_2$ являются двоичными последовательностями и $\#$ является разделителем, определяющим, $w_1 = w_2$. Можно показать, что любая машина Тьюринга для задачи равенства принимает$O(n^2)$время. Это неудобно, потому что машины Тьюринга - это то, что все считают универсальной моделью вычислений, но ни один инженер-программист или исследователь алгоритмов не считает, что равенство строк действительно требует$O(n^2)$время. Так что же дает? Строковое равенство должно быть линейным, поэтому мы изобретаем новую модель там, где оно есть, и лучшее решение, доступное прямо сейчас, - это машины Word RAM.
Возможно, когда-нибудь в будущем мы придумаем лучшую модель - простую, концептуально понятную и улучшающую оперативную память в ее способности моделировать реальную вычислительную сложность. На данный момент мы можем использовать только лучшее, что у нас есть.
В качестве первого грубого приближения вы можете потратить время на доступ к слову в памяти как к константе, независимо от предыдущих обращений. Т.е. модель RAM.
Вы правы, сегодняшние машины совсем не похожи на RAM, это действительно окупается (даже красиво), чтобы организовать доступ к данным, чтобы быть как можно более последовательным, или выдавить последний бит информации из (короткого!) Сегмента памяти перед тем, как обрабатывать его вручную. следующий. Но у вас редко есть свобода действий, ваши обращения к памяти по сути случайны, и модель не так уж далека от истины. Кроме того, современные машины имеют гораздо больше, чем один процессор, а в модели только один. И затем есть векторная обработка (выполнение той же операции с вектором данных, а не одна за другой), как это делают «мультимедийные инструкции» (и даже больше с использованием видеокарт для обработки).
Небольшое обсуждение приведено, например, в том, что Бинарный поиск Хунга является патологическим случаем для кешей . Как видите, анализировать даже простые, хорошо понятные алгоритмы с использованием более реалистичных моделей времени доступа к памяти непросто.
Модель RAM основана на асимптотическом анализе алгоритмов, которые разработаны как однопоточные вычисления в памяти.
Оптимизация производительности для конкретного набора инструкций, кешей и прочего - это одно. Другое дело - быть готовым к разрастанию проблемы. Чтобы оценить, насколько хорошо масштабируется ваш алгоритм в памяти, вы, вероятно, захотите игнорировать мелкие факторы и сосредоточиться на больших$\mathcal{O}$обозначение. Большой$\mathcal{O}$ не собирается оптимизировать все для вас, но, по крайней мере, может сказать вам, что ваше решение хорошо масштабируется (или что вам следует попробовать что-то другое).
RAM предполагает небольшой фиксированный набор инструкций, где каждая операция работает в $\mathcal{O}(1)$. Обратите внимание, что это хорошая модель, если нас интересует только асимптотический рост:
Набор команд современного процессора не мал, но мы можем сделать вид, что это действительно так. Эти дополнительные коды операций не имеют большого значения.$\mathcal{O}$ обозначение.
ЦП могут иметь инструкции, время выполнения которых зависит от ввода. Опять же, мы можем игнорировать их, потому что мы можем моделировать их, используя более простые инструкции, не влияя на большие$\mathcal{O}$сложность. То же самое касается уровней кеша: их производительность все еще ограничена некоторой небольшой константой, поэтому они работают в$\mathcal{O}(1)$ по определению.
Да, вы не можете получить доступ к памяти в постоянное время, если она продолжает расти. К счастью, благодаря здравому смыслу этого никогда не требуется. Никто не индексирует весь Интернет в непостоянную память одинокой однопоточной машины.