Методы программирования. Громов Ю.Ю - 87 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

87
смотре р и q пробегают по спискам, которые подвергаются слиянию;
s обычно указывает на последнюю обработанную запись текущего под-
списка, а t – на конец только что выведенного подсписка.)
L3. [Сравнение K
p
и K
q
.] Если K
p
> K
q
, то перейти к шагу L6.
L4. [Продвижение p.] Присвоить |L
s
| ← p, s ← p, p ← L
p
. Если р > 0,
то вернуться к шагу L3.
L5. [Завершение подсписка.] Присвоить L
s
← q,
s ← t. Затем при-
своить t ← q и q ← L
q
один или более раз, пока не станет q ≤ 0, после чего
перейти к шагу L8.
L6. [Продвижение q.] (Шаги L6 и L7 двойственны по отношению к
L4 и L5.) Присвоить |L
s
| ← q, s ← q, q ← L
q
. Если q > 0, вернуться к шагу L3.
L7. [Завершение подсписка.] Присвоить L
s
← p, s ← t. Затем присво-
ить t ← р и р ← L
p
один или более раз, пока не станет р ≤ 0.
L8. [Конец просмотра?] (К этому моменту р ≤ 0 и q ≤ 0, так как оба
указателя продвинулись до конца соответствующих подсписков.) При-
своить р ← – р, q ← – q. Если q = 0, то присвоить |L
s
| ← p, |L
t
| ← 0 и вер-
нуться к шагу L2; в противном случае вернуться к шагу L3. ■
Пример работы этого алгоритма иллюстрирует табл. 3, в которой
представлены значения связей L
j
к моменту непосредственно перед вы-
полнением шага L2. По окончании работы алгоритма L записи можно
переразместить так, чтобы их ключи были упорядочены.
Таблица 3
j 0 1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
17
K
j
–
503
87
512
61
908
170
897
275
653
426
154
509
612
677
765
703
–
L
j
1 –3
–4
–5
–6
–7
–8
–9
–10
–11
–12
–13
–14
–15
–16
0 0 2
L
j
2 –6
1 –8
3 –10
5 –11
7 –13
9 12
–16
14
0 0 15
4
L
j
4 3 1 –11
2 –13
8 5 7 0 12
10
9 14
16
0 15
6
L
j
4 3 6 7 2 0 8 5 1 14
12
10
13
9 16
0 15
11
L
j
4 12
11
13
2 0 8 5 10
14
1 6 3 9 16
7 15
0
Время работы алгоритма L в среднем равно приблизительно (10N log
2
N +
+ 4.92N) единиц с небольшим стандартным отклонением порядка
N
.
Таким образом, связанное распределение памяти имеет бесспорные
преимущества по сравнению с последовательным, поскольку при этом
требуется меньше памяти, а программа работает на 10% быстрее.
Упражнения
1. Слейте по алгоритму M два упорядоченных подфайла 12, 13, 14,
14, 25, 42, 47, 62 и 16, 35, 46, 52, 61, 73, 91, 103 в один файл и установите
сколько раз при этом будут выполнены шаги M3 и M5.

Страницы