Cтраница 3
Операции над множествами и над очередями здесь не реализуются, но предполагается выполнение примитивных операций. Однако время, требуемое этими операциями, включается в оценку времени всего алгоритма. [31]
Применения примитивных функций включают ( рекурсивную) редукцию строгих аргументов примитива и проведение затем примитивной операции в соответствии с б-правилами. [32]
Этот результат является оптимальным в рамках модели алгебраических деревьев вычислений ( с некоторым набором примитивных операций) [26] для последней задачи, в то время как для первой задачи остается открытым вопрос о том, является ли Q ( / z log n) нижней оценкой. [33]
Этот результат является оптимальным в рамках модели алгебраических деревьев вычислений ( с некоторым набором примитивных операций) [26] для последней задачи, в то время как для первой задачи остается открытым вопрос о том, является ли й ( п logn) нижней оценкой. [34]
Упражнение 3.20. Программа ARCHIVE может быть проще и может обеспечивать большее быстродействие, если операционная система обеспечивает определенные примитивные операции, такие как переименование временного файла вместо копирования, определение размера файла без его чтения, перемещение к произвольной точке файла без чтения промежуточной информации и избирательная перезапись частей файла. Рассмотрите эти и другие примитивы, которые могут оказаться полезными. Есть ли они в Вашей операционной системе. [35]
Сравнения чисел - равно, не-равно, меньше-чем, больше-чем, меньше-или-равно, больше-или-равно - образуют второй набор примитивных операций, имеющихся в большинстве языков. Как и в случае арифметических операций, они могут транслироваться в специфические и универсальные версии, при этом специфические обычно в той или иной мере обеспечиваются аппаратурой. [36]
Видно, что в любом применении, в которое входит запоминание, сравнение указателей должно входить в число примитивных операций. Заметьте, что атомы также проверяются на равенство, поскольку они не имеют ассоциированного адреса; мы можем с тем же успехом считать, что каждый атом имеет уникальный ( неявный) адрес, тогда одинаковые ( равные) атомы будут идентичны согласно данному выше определению. Например, индекс хэширования может быть вычислен исходя из адреса или состояния битов указателя с помощью обычных методов. Кроме этого, подобное применение указателей для представления аргументов в мемо-таблицах облегчает сборку мусора. Мы еще встретимся с этим в разд. [37]
Другая часть памяти статически выделяется под системные программы, включая транслятор, интерпретатор, компилятор ( если он есть), примитивные операции и программы управления памятью. Третья область выделяется под стек записей активации для вызовов подпрограмм. Каждая запись активации содержит точку возврата и рабочие ячейки, используемые подпрограммой во время ее выполнения. [38]
Как упоминалось ранее, мы будем использовать алгебраическое дерево вычислений ( коротко АДВ), введенное Бен-Ором [26] в качестве нашей основной модели вычислений, возможно, дополнив ее рядом примитивных операций, таких, как проверка того, с какой стороны от направленной прямой лежит точка, в предположении, что все они выполняются за постоянное время. [39]
Примитивные операции АПЛ могут использовать в качестве аргументов массивы и результаты их также могут быть массивами. Таким образом, в АПЛ в роли основной единицы данных часто выступает весь массив, а не одиночный элемент массива, как в языках, подобных Фортрану и Алголу. Этот акцент на обработку массивов создает особый стиль программирования на АПЛ, совершенно отличный от других языков. [40]
Структурами данных этой виртуальной машины являются структуры данных, используемые во время выполнения программы. Примитивными операциями являются операции, которые действительно могут быть выполнены во время прогона программы и которые во время трансляции не были сведены к последовательностям более простых операций. [41]
Однако примитивные операции над программами совершенно отличаются от обычных операций над другими типами данных. Чаще всего к программам применяются две операции: трансляция и выполнение. Обычно трансляция и выполнение рассматриваются как мета-операции, активируемые только на уровне операционной системы. Например, для того чтобы скомпилировать и выполнить программу на Фортране, как правило, необходим запрос к операционной системе на компиляцию ( трансляцию) программы в выполняемую форму. Операционная система вызывает компилятор с Фортрана и передает ему в качестве входных данных программу, написанную на Фортране. Чтобы выполнить скомпилированную программу, необходимо еще одно обращение к операционной системе. [42]
Представив наглядным образом ситуацию в привычном для нас трехмерном пространстве, легко показать, что в пространстве произвольной размерности d соотношения (3.10) и (3.11) дают решение нашей задачи. Вычислительную сложность этой примитивной операции можно легко оценить. Следовательно, вектор а ортогонален вектору п и каждому из ( d - 2) векторов p p d l и может быть определен в результате решения системы из ( d - 2) уравнений с ( d - 1) неизвестными с последующим нормированием результата, чтобы получить вектор единичной длины. Эта процедура включает O ( dz) арифметических операций. Для вычисления каждого р / г требуется 0 ( d) арифметических операций, а выбор р - осуществляется за O ( Nd) операций. [43]
Существует ряд полезных операций, которые хотя и могут быть выражены в терминах пяти ранее упоминавшихся, но в литературе имеют специальные названия. Они используются иногда как примитивные операции. [44]
Два из этих случаев относительно просты. Смысл литералов и символов примитивных операций обычно фиксируется при определении Языка. Таким образом, обозначает ли сложение и что обозначает 10: десять ( в десятичной записи), восемь ( в восьмеричной записи) или два ( в двоичной записи) - всем этим программист не управляет. Встречаются и исключения, например функция OPSYN в языке Снобол 4 позволяет программисту переопределять символы примитивных операций. Однако эти случаи сравнительно редки, и они добавляют сравнительно мало новых понятий. Главный интерес для нас представляют оставшиеся случаи простых переменных, имен структур данных, имен подпрограмм, меток инструкций и формальных параметров. Синтаксис таких имен различен в разных языках и в разных классах одного языка. Мы будем употреблять здесь общий термин идентификатор для простого имени любого из этих типов. [45]