Упорядоченные данные

Cтраница 2

Элементы размещаются так, чтобы, во-первых, вычисления, требующие определенного порядка расположения данных, могли выполняться эффективно, во-вторых, результаты имели осмысленный вид, и в-третьих, последующие процессы имели бы пригодные исходные данные. Для человека, как правило, порядок данных весьма важен, так как позволяет подметить свой ства, имеющие решающее значение. Кроме того, современная аппаратура работает наиболее эффективно при упорядоченных данных. Понятие упорядоченности в меру интуитивно. Есть много естественных упорядочений таких, например, как упорядочение имен в списке по алфавиту или упорядочение ряда чисел по возрастанию. [16]

Итог сбалансированного слияния. [17]

Распределение новых строк происходит по тому же алгоритму, что и распределение исходных строк. Строки, слитые вместе, являются следующими строками, доступными ( в физическом смысле) для головок считывание лентопротяжных устройств. Можно построить одну строку меньше, чем за flogmSI просмотров, если максимально использовать эти способы на хорошо упорядоченных данных. На рис. 13.3 после каждого номера строки в скобках указаны первый и последний ключи этой строки. [18]

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

Однако и в анализе средней производительности существуют трудности. Во-первых, входная модель может неточно характеризовать входные данные, встречающиеся на практике, или же естественная модель входных данных может вообще не существовать. Мало кто будет возражать против использования таких моделей входных данных, как случайно упорядоченный файл, для алгоритма сортировки или случайный набор точек для геометрического алгоритма, и для таких моделей можно получить математические результаты, которые будут точными предположениями о производительности программ в реальных приложениях. Но как можно характеризовать входные данные для программы, которая обрабатывает текст на английском языке. Даже для алгоритмов сортировки в определенных приложениях рассматриваются другие модели кроме модели случайно упорядоченных данных. Во-вторых, анализ может требовать глубоких математических доказательств. Например, анализ случая средней производительности для алгоритмов union-find достаточно сложен. [20]

Обратное чтение. [21]

Результат выравнивания - све ение к минимуму копирования строк и частичного слияния за счет замены копирования и частичных слияний перемещением фиктивных величин. Предпочтение одной расстановки уровня перед другой зависит от необходимости управлять распределением фиктивных величин от уровня к уровню. Другой причиной выбора конкретной расстановки является необходимость выбора конкретной заключительной ленты вывода. Управляя распределением так, чтобы на каждом уровне на нужной ленте вывода было нечетное число строк, можно обеспечить размещение упорядоченных данных на нужной ленте. [22]

Страницы: 1 2