АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Примеры адресной арифметики

Пример 3.19. Треугольная матрица содержит элементы, расположенные выше главной диагонали квадратной матрицы размером N*N, включая диагональ, и хранится по строкам в виде вектора. Выразить индекс элемента в векторе в зависимости от его индексов в матрице.

Решение. Матрица содержит элементы:

Если считать от нуля, порядковый номер k элемента x[i,j] в памяти равен количеству расположенных до него элементов:

k = длина 0-й строки +... + длина (i-1)-й строки + j - i =

= N + N-1 + N-2 +... + N-(i-1) + j - i

Поскольку сумма арифметической прогрессии a₁ +... + a_n равна

(a₁ + a_n) * n / 2,

получим

k = (N + (N-i+1)) * i / 2 + j - i = (2*N-i+1)*i/2 +j-i.

Пример 3.20. Упакованный вектор. Написать выражения, определяющие адрес элемента вектора V[J] и его сдвиг S от начала ячейки в зависимости от индекса элемента J, адреса B начала вектора и длины D его элементов в битах для случая, когда в одной ячейке размещается целое число K элементов (K ³ 1).

Решение. На рис. 3.13 а показано размещение элементов вектора V в ячейках памяти. Допустим, элемент V[J] находится в ячейке B+L. Из рис. 3.13 а получена таблица зависимости L и S от J (рис.3.13 б). Из этой таблицы видно, что L=J / K и искомые зависимости выражаются формулами:

Адрес V[J] = B + J / K, S = J % K * D (3.11)

а) Размещение элементов б) Зависимость L и S от J

Адрес	Содержимое ячейки		J	L	S
В	V[K-1]	...	V[1]	V[0]				D
В+1	V[2*K-1]	...	V[K+1]	V[K]				2*D
.	D		D	D		...	...	...
.		...				K-1		(K-1)*D
.						K
В+L	...	V[J]	...			K+1		D
						K+2		2*D
					...	...	...
			S		2*K-1		(K-1)*D
						...	...	...

Рис. 3.13. Хранение упакованного вектора

Пример 3.21. Упаковка и распаковка. В каждом из двухбайтовых элементов массива упакованы несколько целых чисел, имеющих значения от 2000 до 2007. Составить фрагменты программы

- упаковки числа: присвоения данного значения числу с указанным номером;

- распаковки числа: получения значения числа по его номеру.

Решение. Диапазон от 2000 до 2007 содержит 8 значений. Такое число можно разместить в 3 бита, если хранить его уменьшенным на 2000. Тогда в каждом двухбайтовом элементе массива будут храниться по 5 трехбитовых чисел.

Воспользовавшись формулами (3.11), получим фрагменты программы:

#define N 100 /* Количество чисел / 3 */

unsigned x[N], /* x содержит 3*N чисел v[i] */

z, /* Значение числа (в 3 младших битах) */

m, /* Заданный номер числа */

j, /* x[j] содержит v[m] */

s; /* Расстояние v[m] от правого края x[j] */

...

/* а) Упаковка: v[m] = z */

j = m/5; s = m%5*3;

x[j]=x[j] &!(07 << s); /* Очистка в x[j] места для v[m] */

x[j]=x[j] | (z-2000)<<s; /* Запись z в x[j] на место v[m] */

...

/* б) Распаковка: z = v[m] */

j = m/5; s = m%5*3;

z = (x[j]>>s & 07) + 2000; /* Получение числа v[m] */

Пример 3.22. Быстрый поиск минимума. Требуется реализовать массив X из n элементов с быстрым получением минимального элемента, т.е. структуру данных с операциями:

- подготовка к работе за время O(n),

- присвоить j-му элементу заданное число за время O(log n),

- получить значение j-го элемента за время O(log n),

- получить номер минимального элемента

(или одного из минимальных элементов) за время O(log n).

Решение. Надстроим над элементами массива как над листьями бинарное дерево. В каждой вершине дерева хранится меньшее из значений ее сыновей, которое является также минимальным элементом соответствующего поддерева (рис. 3.14).

Корректировка этой информации при изменении значения какого-либо элемента массива, а также прослеживание пути из корня к минимальному элементу требуют числа действий порядка log n. Это быстрее, чем обычный последовательный поиск минимума в массиве за время O(n). Аналогично определяется максимум.

а) Исходное состояние б) Этапы присваивания X[3]=5

(подчеркнуты изменяемые числа)

1) 2) 3)

2 2 2 3

Дерево / \ / \ / \ / \

над X 3 2 3 2 3 4. 3 4

/ \ / \ / \ / \ / \ / \ / \ / \

Массив X: 8 3 2 4 8 3 5 4 8 3 5 4 8 3 5 4

индексы для X= 1 2 3 4 j = 1 2 3 4 5 6 7

j = 1 2 3 4 5 6 7 1) t[j]= 2 3 2 8 3 5 4 X[3]=5

t[j]= 2 3 2 8 3 2 4 2) t[j]= 2 3 4 8 3 5 4 min(5,4)=4

3) t[j]= 3 3 4 8 3 5 4 min(3,4)=3

Массив X

Рис. 3.14. Массив X с быстрым поиском минимального элемента

Бинарное дерево (вместе с листьями - массивом X) хранится в векторе t с помощью адресной арифметики: сыновья вершины с индексом j имеют индексы 2*j и 2*j+1, а ее отец имеет индекс j/2. Корень дерева t[1] равен меньшему из своих сыновей t[2] и t[3] (и минимальному значению массива), t[2] равен меньшему из своих сыновей t[4] и t[5] и т.д. Вектор t содержит 2*n-1 элементов: t[1]..t[n-1] - внутренние вершины дерева (не листья), а t[n]..t[2*n-1] играют роль элементов массива X (X[i] отображается в t[i+n-1]). Реализация операций - в алг. 3.1.

Алгоритм 3.1. Операции над массивом с быстрым поиском

минимального элемента

/* Подготовка к работе */

t[n]..t[2*n-1] = X[1]..X[n]; /* Запись исходного массива */

/* Надстройка дерева над массивом */

for (j=2*n-1; j>1; j=j-2)

{

if (t[j] < t[j-1]) t[j/2]=t[j];

else t[j/2]=t[j-1];

}

/* Присвоить i-му элементу заданное число */

t[i+n-1] = заданное число;

for (j=i+n-1; j>1; j=j/2)

{ /* отцу t[j] присвоить min (t[j], брат t[j]) */

if (j%2) k=j-1; else k=j+1; /* индекс брата t[j] */

if (k<2*n && t[k]<t[j]) t[j/2]=t[k];

else t[j/2]=t[j];

}

/* Получить номер минимального элемента */

j=1;

while (j < n)

if (t[j]==t[2*j]) j=2*j; else j=2*j+1;

результат = j-n+1;

Примечание.В языках, где это возможно, в том числе C, умножение и деление на 2 быстрее выполнять сдвигом, т.е. заменить:

2*n на n<<1; j / 2 на j >> 1.

Проверка if (j % 2) быстрее выполнится в виде if (j & 1).

Пример 3.23. Очередь с приоритетами. Требуется реализовать структуру данных для запоминания и удаления элементов с информацией о времени некоторых событий. Элементы поступают в любом порядке, а удаляются в хронологическом порядке по времени событий. Время события считать целым числом.

Решение. Реализуемую структуру данных можно рассматривать как очередь с приоритетами. В приоритетной очереди указывается приоритет поступающего элемента. При удалении из очереди выбирается элемент с наивысшим приоритетом (или один из таких элементов), а не тот, который поступил первым.В данной задаче приоритетом служит время события, высшим считается меньшее значение приоритета.

Если хранить приоритетную очередь в виде списка из n элементов, упорядоченных по возрастанию приоритета, то время включения элемента пропорционально n, время исключения из начала списка фиксировано: O(1) (не зависит от n) и суммарное время обработки элемента О(n). Приоритетную очередь можно реализовать так, чтобы добавление и удаление элемента для больших очередей происходило быстрее, за время О(log n). Для этого используется идея пирамидальной сортировки (ее также называют "сортировка деревом"), описанной в первой части учебника [67].

Под пирамидой будем понимать (полностью сбалансированное) бинарное дерево, каждая вершина которого (элемент очереди) содержит значение (приоритет элемента), причем значение вершины не больше значений всех ее потомков (рис. 3.15).

Сбалансированное дерево удобно представлять в векторе q[1]..q[k] с помощью адресной арифметики: сыновьями вершины q[j] являются вершины q[2*j] и q[2*j+1], отцом вершины q[j] будет q[j/2]. (При целочисленном делении дробная часть результата отбрасывается.) Корнем дерева является q[1].

Примечание. В отличие от элементов массива примера 3.21 элементы очереди можно переставлять. Поэтому здесь внутренние вершины дерева (не листья) вместе с листьями содержат основную информацию, а не дублируют значения листьев, т.е. память используется экономно.

Будем размещать элементы очереди в векторе q[1],..., q[k], (где k - количество элементов очереди), поддерживая свойство,пирамиды: q[j] не больше своих сыновей q[2*j] и q[2*j+1], если таковые существуют, и, следовательно, всякий элемент не больше своих потомков. На рис. 3.15 очередь содержит 6 элементов, в векторе q показаны только значения их приоритетов.

а) Элементы очереди (могут поступать в любом порядке):

3, 4, 5, 6, 7, 9

б) Исходное состояние в) Добавление в очередь числа 2

(подчеркнуты изменяемые числа)

Запись 2 Обмен 4 «2 Обмен 3 «2

3 3 3 2

/ \ / \ / \ / \

5 4 5 4 5 2 5 3

/ \ / \ / \ / \ / \ / \ / \ / \

9 6 7 9 6 7 2 9 6 7 4 9 6 7 4

j = 1 2 3 4 5 6 7 j = 1 2 3 4 5 6 7

q[j]= 3 5 4 9 6 7 - q[j] = 3 5 4 9 6 7 2 Запись 2

q[j] = 3 5 2 9 6 7 4 Обмен 4 «2

q[j] = 2 5 3 9 6 7 4 Обмен 3 «2

Рис. 3.15. Очередь с приоритетами в виде пирамиды

Новый элемент добавляется в конец занятой части вектора, затем восстанавливается пирамидальность дерева (алг. 3.2).

Алгоритм 3.2. Включение нового элемента в очередь

с приоритетами (Очередь <== новый элемент)

k++; q[k]= новый элемент; j=k;

while (q[j] - не корень и q[j] меньше своего отца)

{ /* инвариант: в дереве любой предок не больше потомка,

если этот потомок - не q[j] */

Обменять q[j] с его отцом;

}

Очередь образуют элементы, стоящие в вершинах дерева. За каждым элементом стоят двое, а перед каждым (кроме первого) - один. Встав в конец очереди, приоритетный элемент пробирается к началу, вытесняя впереди стоящих, пока не встретит более приоритетного элемента (рис. 3.15).

Алгоритм 3.3. Удаление элемента из очереди с приоритетами

и присваивание его величине x (Очередь ==> x)

x=q[1]; q[1]=q[k]; k--; t=1;

/* Восстановление пирамиды из дерева c корнем t, */

/* поддеревья которого являются пирамидами */

while (минимальное число не в t, а в одном из ее сыновей)

{ /* Все вершины не больше потомков, кроме, быть может t */

if (минимальное число в правом сыне)

{ Обмен t с ее правым сыном; t = правый сын; }

else /* минимальное число - в левом сыне */

{ Обмен t с ее левым сыном; t = левый сын; }

}

При удалении элемента q[1] на его место в корень дерева переписывается q[k] - последний элемент занятой части вектора. Пирамидальность дерева нарушается в его корне, но оба поддерева корня сохраняют пирамидальность (алг. 3.3).

Для восстановления пирамидальности всего дерева его корень сравнивается с меньшим из сыновей. Если корень меньше, дерево уже является пирамидой; а если корень больше, он меняется местами с меньшим сыном и затем таким же образом восстанавливается нарушенная пирамидальность поддерева с замененным корнем.

Процесс оканчивается когда восстанавливаемое поддерево состоит из одной вершины-листа. Заметим, что q[j] является листом тогда и только тогда, когда 2*j > k.

Дата добавления: 2015-09-27 | Просмотры: 438 | Нарушение авторских прав