Входной список

Cтраница 2

Состояние счетчиков, младший разряд. [16]

Мы используем область вывода длины N и область счета, содержащую счетчик для каждого символа, который может появиться в ключе. Просмотр входного списка проверяет позицию разряда каждого ключа и подсчитывает частоту появления каждого значения. На рис. 10.9 показано состояние счетчиков после начального подсчитывающего просмотра. Таблица счетчиков заполняется сложением значения позиции разряда с базовым адресом таблицы. [17]

В данном случае входной объект представляется перечнем, включающим пять непроизводных элементов: точка ( два), окружность, квадрат и отрезок прямой. Вначале выделяются все случаи, когда элементы входного списка удовлетворяют одному из заданных предикатов. Каждый выполненный предикат образует новый элемент. Проверяется, какие новые элементы можно построить из исходных вновь образованных, затем эта процедура повторяется с очередными построенными элементами и так до тех пор, пока возможности построения новых элементов не окажутся исчерпанными. После этого удаляются все элементы, не являющиеся компонентами некоторого элемента, содержащего все непроизводные элементы входного объекта. Практически это выглядит следующим образом. [18]

Действительно, исполнимый терм будет получен лишь по завершении анализа входного списка. Многократные проходы по синтаксическому дереву Пролог заменяет последовательностью под-унификаций. [19]

При анализе алгоритма выбор входных данных может существенно повлиять на его выполнение. Скажем, некоторые алгоритмы сортировки могут работать очень быстро, если входной список уже отсортирован, тогда как другие алгоритмы покажут весьма скромный результат на таком списке. А вот на случайном списке результат может оказаться противоположным. [20]

Еще хуже то, что при каждом вызове итеративной процедуры обратить будет выполняться разложение ( при помощи процедуры склеить) тех фрагментов, которые совершенно точно так же раскладывались в результате предыдущих вызовов; таким образом, исполнение нашей программы содержит слишком много излишних действий. В результате всего этого время, требуемое для выполнения алгоритма, находится по крайней мере в квадратичной зависимости от длины входного списка. [21]

На рис. 9.15 показано прямое четырехпоточное слияние для списка из 16 элементов. В область вывода ( которая не обязательно больше, чем для двухпоточного слияния) помещаются строки, сформированные четырехпоточ-ным слиянием из исходных одноэлементных строк входного списка. Слияние четырех строк, выполненное на первом просмотре, формирует одну упорядоченную строку. Весь список, таким образом, упорядочивается за два просмотра, использующих четырехпоточное слияние. [22]

Распределение 961 - 1000 и сбор убывающей строки на Т. [23]

Если между значением ключа ( или значением разряда ключа) и некоторой частью адресного пространства машины существует взаимнооднозначное соответствие, то адрес вычисляется просто; каждый элемент перемещается только один раз ( из входного списка в список вывода), и нужно лишь достаточное количество памяти для хранения заключительного списка вывода. [24]

Часто утилита сортировки предоставляет определенные средства, не зависящие от характеристик подлежащего сортировке списка. В ряде случаев утилита оптимизирует метод сортировки в зависимости от положения и длины ключа, его сложности и других характеристик файла. Обычно входной список поступает с одного внешнего носителя ( рис. 5.5.1), однако возможно определить несколько различных входных файлов, В этом случае файлы поступают в порядке, указанном в ЯУЗ. Устройство и носители, содержащие входной файл, задаются в предложениях определения файла ЯУЗ. [25]

На этой диаграмме показан один шаг сортировки выбором связного списка. Входной список просматривается с таким расчетом, чтобы max показывал на узел, предшествующий ( a tуказывал на) узлу, содержащему максимальный элемент. С течением процесса, в конечном итоге, исчерпывается весь входной список, а в выходном списке элементы размещаются в заданном порядке. [26]

III, эти процедуры ведут себя намного эффективнее, хотя их логика более трудна для понимания. Время работы алгоритма, получающегося в результате использования указанных процедур, будет зависеть лишь линейно от длины входного списка. [27]

Стоит отметить, что ОПВ восстанавливает явно пространство, занятое ненужными ячейками управления и ячейками локальных переменных, однако никогда не приводит к сокращению глобального стека, где накапливаются структурированные данные - он сокращается лишь при выполнении возврата или сборке мусора. С другой стороны, если ОПВ запрограммирована настолько компактно, насколько это возможно для того, чтобы избежать чрезмерного потока данных между фреймами и регистрами, то ОПВ может значительно сократить время обработки, поглощаемое итеративными вычислениями. Воздействие ОПВ на исполнение этой программы заключается в том, что на месте каждого фрейма, за исключением первого, записывается его последователь, и поэтому локальный стек никогда не продолжается дальше позиции 2, тогда как прежде его длина росла пропорционально длине входного списка. Однако второе возможное улучшение - это гораздо более высокая скорость, поскольку разработчик реализации может ( после достаточного анализа и программистских усилий) стянуть унификацию и построение фрейма, возникающих при выполнении каждой операции перезаписи. Получаемое в результате поведение будет во многом подобно поведению традиционной программы, использующей деструктивное присваивание для проведения итерации над одной фиксированной областью памяти и в то же время строящей структурированные выходные данные в другой области; в логической реализации этими областями являются соответственно локальный и глобальный стеки. [28]

При просмотре входного списка ребер v - ребро ( у /, у /) заносится в РСДС только при i /, благодаря чему каждое ребро заносится в РСДС лишь однажды. Чтобы осуществить это, мы должны определить местоположение ( а /, VH) в РСДС. Предположим, что при просмотре входного списка ребер. [29]

Порядок сложности всех этих алгоритмов был полиномиален. Иногда время их работы оказывалось линейным, как при последовательном поиске: при удлинении списка вдвое алгоритм работает вдвое дольше. Нам встречались и алгоритмы сложности O ( N2) - такую сложность имеют некоторые алгоритмы сортировки: если длину входного списка удвоить, то время работы алгоритма возрастает в 4 раза. Сложность стандартного алгоритма матричного умножения равна O ( 7V3), и при увеличении размеров матриц вдвое такой алгоритм работает в 8 раз дольше. [30]

Страницы: 1 2 3