Последовательность - сравнение
Cтраница 2
Третий и наиболее специфический уровень требует очень детального сравнения между выходом программы и последовательным поведением испытуемых при решении задач. Одно из преимуществ того обстоятельства, что модели информационных процессов выражены в виде программ, состоит в том, что, когда такая программа, как GPS, просчитывается на машине, мы можем дать вычислительной машине инструкцию проследить и отпечатать настолько детально, насколько это нам необходимо, вырабатываемую программой последовательность сравнений, оценок, манипуляций и решений. Это позволяет нам сравнить почти слово в слово все, что рассматривает, испытывает или отвергает программа, с текущими сообщениями испытуемого о его собственных действиях. Ньюэлл и Саймон приводят три десятка строк протокола поведения человека и соответствующего отрезка программы, отмечая как многочисленные и довольно неожиданные аналогии, так и определенные различия между этими двумя записями. [16]
 |
Минимальная по памяти турнирная сортировка, начало просмотра 3. [17] |
В этом дереве вершина каждой тройки содержит наибольший в тройке ключ. На рис. 5.18 показаны сравнения и обмены первого просмотра. Последовательность сравнений обрабатывает список снизу вверх, двигаясь вдоль по дереву от уровня к уровню. [18]
В данном случае структура управления значительно сложнее, чем в сортировке Шелла. Основное различие заключается в количестве этапов и расстоянии между элементами, управление которыми осуществляется при помощи отдельных переменных. Третья переменная нужна для определения последовательностей сравнения на этапе. Четвертая переменная используется для управления переходом от этапа к этапу и от просмотра к просмотру. [19]
На рис. 7.1 изображена специальная расстановка обычного списка чисел. Некоторый механизм выбора основы ( объясняемый в разделе 7.5) выбирает ключ 6 из позиции 3 и помещают его в рабочую память, именуемую PIVOT. Первая позиция теперь свободна и получает значение из восходящей последовательности сравнений. Указатель BEG изначально устанавливается на первую позицию списка, указатель END - на последнюю. [20]
Метод просеивания ( также называемый линейной вставкой с обменом или челночной сортировкой) является самым лучшим из этих методов. Он отличается от других методов обмена тем, что не сохраняет фиксированной последовательности сравнений. Кроме этого, исчезает разделение - на отдельные просмотры как следствие схемы последовательностей сравнений. [21]
Обменом называется перестановка позиций двух записей в списке в зависимости от результата проверки их относительной величины. Если в списке встречается запись с ключом, меньшим, чем у предыдущей, то эти записи меняются местами. Производительность методов обмена зависит от сложности определения последовательности сравнений и обменов. Часто число обменов сокращают, откладывая обмен до конца каждого просмотра. Этот прием, в частности, используется в методе, который сейчас будет описан. [22]
Эта теорема доставляет наиболее употребительный критерий для решения вопроса о том, суммируема ли в R последовательность положительных чисел ( хп) или нет; ее стараются сравнить с более простой последовательностью ( уп), относительно которой уже известно, суммируема она или нет; если существует конечное число а 0 такое, что хп ауп для каждого ге, начиная с некоторого, и если ( у) суммируема, то ( г) тоже суммируема; напротив, если существует конечное число Ъ 0 такое, что хп - Ьуп Дотя каждого п, начиная с. Мы увидим впоследствии ( Книга IV, гл. V, § 4), каким образом разыскиваются последовательности сравнения в наиболее часто встречающихся случаях. [23]
В наших реализациях входные данные определяют разве что порядок, в котором элементы обрабатываются во время слияний. Каждый проход требует пространства памяти и числа шагов, пропорциональных размеру подфайла, что обусловливается необходимостью затрат на перемещение данных во вспомогательный файл. Соответствующие две ветви оператора if могут потребовать слегка отличающихся значений времени для выполнения компиляции, что в свою очередь приводит к некоторой зависимости времени выполнения от характера входных данных, однако число сравнений и других операций не зависит от того, как упорядочен входной файл. Обратите внимание на то, что это отнюдь не эквивалентно утверждению, что алгоритм не адаптивный ( см. раздел 6.1) - последовательность сравнений не зависит от упорядоченности входных данных. [24]
 |
Организация сортировок различных высоких степеней. [25] |
Основой процесса слияния является фундаментальная идея упорядочения данных путем чередования элементов из двух или более упорядоченных списков. На рис. 9.1 показаны две упорядоченные части списка из десяти элементов. Упорядоченное объединение этих частей представляет собой окончательный упорядоченный список из десяти элементов. Процесс достижения этого упорядочения называется двухпоточным) слиянием - двухпоточным, потому что есть два входных списка. Последовательность сравнений показана на рис. 9.1, упорядоченный список дан в виде исходных позиций элементов. Поле памяти, необходимое для данных, включает, помимо поля для S1 и S2, поле для списка вывода. [26]
Страницы: 1 2