Слово ОЗУ

В теоретической информатике модель RAM (машина с произвольным доступом к слову) — это модель вычислений , в которой машина с произвольным доступом выполняет арифметические и побитовые операции над словом из w бит. Майкл Фредман и Дэн Уиллард создали ее в 1990 году для моделирования языков программирования , таких как C. ^[1]

Модель

Модель RAM слова — это абстрактная машина, похожая на машину с произвольным доступом , но с конечной памятью и длиной слова. Она работает со словами размером до w бит, что означает, что она может хранить целые числа размером до . Поскольку модель предполагает, что размер слова соответствует размеру задачи, то есть для задачи размером n , , модель RAM слова является трансдихотомической моделью . ^[2] Модель позволяет выполнять как арифметические операции, так и побитовые операции , включая логические сдвиги , за постоянное время (точный набор инструкций, предполагаемый алгоритмом или доказательством с использованием модели, может различаться). ${\displaystyle 2^{w}-1}$ ${\displaystyle w\geq \log n}$

Алгоритмы и структуры данных

В модели Word RAM сортировка целых чисел может быть выполнена довольно эффективно. Ицзе Хан и Миккель Торуп создали рандомизированный алгоритм для сортировки целых чисел за ожидаемое время (в нотации Big O ) , ^[3] в то время как Хан также создал детерминированный вариант со временем выполнения . ^[4] ${\displaystyle O(n{\sqrt {\log \log n}})}$ ${\displaystyle O(n\log \log n)}$

Проблема динамического предшественника также обычно анализируется в модели Word RAM и была первоначальной мотивацией для модели. Дэн Уиллард использовал y-fast, чтобы решить эту проблему за время, или, точнее, где U — это ограничение на хранимые значения. ^[5] Майкл Фредман и Уиллард также решили проблему, используя деревья слияния за время. ^[1] Используя экспоненциальные деревья поиска , запрос может быть выполнен за . ^[6] ${\displaystyle O(\log w)}$ ${\displaystyle O(\log \log U)}$ ${\displaystyle O(\log _{w}n)}$ ${\displaystyle O({\sqrt {\log n/\log \log n}})}$

Дополнительные результаты по модели Word RAM перечислены в статье о поиске в диапазоне .

Нижние границы, применимые к алгоритмам ОЗУ слов, часто доказываются в модели зонда-клетки .

Смотрите также

• Трансдихотомическая модель

Ссылки

1. Фредман, Майкл ; Уиллард, Дэн (1990). «Прорыв информационно-теоретического барьера с помощью деревьев слияния». Симпозиум по теории вычислений : 1–7.
2. Фактически обычно предполагается, что n меньше, чем , так что рассматриваемая структура данных может быть проиндексирована с помощью w -битных адресов. ${\displaystyle 2^{w}}$
3. Хан, Ицзе; Торуп, М. (2002), «Сортировка целых чисел за ожидаемое время O( n √ log log n ) и линейное пространство», Труды 43-го ежегодного симпозиума по основам компьютерной науки (FOCS 2002) , IEEE Computer Society, стр. 135–144, CiteSeerX 10.1.1.671.5583 , doi :10.1109/SFCS.2002.1181890, ISBN  978-0-7695-1822-0
4. Хан, Ицзе (2004), «Детерминированная сортировка за время O ( n log log n ) и в линейном пространстве», Журнал алгоритмов , 50 (1): 96–105, doi :10.1016/j.jalgor.2003.09.001, MR  2028585
5. Уиллард, Дэн Э. (1983). «Лог-логарифмические запросы в наихудшем случае возможны в пространстве Θ (N)». Information Processing Letters . 17 (2): 81–84.
6. Андерссон, Арне; Торуп, Миккель (2007). «Динамические упорядоченные множества с экспоненциальными деревьями поиска». Журнал ACM . 54 (3): 1–40. arXiv : cs/0210006 . doi :10.1145/1236457.1236460.