INTECER ECeES.UICHTl1DO),NEXT,NUHUN.UNC№N;iOO) m INTEGER VERTEXI1D0)

INTEGER CdOO.tOD) .M.FROHdDO) ,T0{100j ,C0ST[10C} « I NTEGEIl «E lGHr,UEAST,{(.EWCST,NEWVTX, VTX «=c

•= с ПРОВЕРКА ВХОДНЫХ ДАННЫХ НА ДОПУСТИМЫЕ ЗНАЧЕНИЯ "С и ПРИСВОЕНИЕ НАЧАЛЬНЫХ ЗНАЧЕНИЙ {ИНИЦИАЛИЗАЦИЯ «=с

1= CALL CHECKtCH) 1" EDGES в О NEXT т Н

шнин,«м-1

4= WEIGHT-О

1» В0100 Л " 1,тт

Ч9« UNCBSN(II) » И

49=» LIGHT(II) «СШ.ШТ!

49= VERTEXCm -КЕХТ

49= 100 CONTINUE 1= СО ТО 350 sC

" С ОБНОВЛЕНИЕ ТАБЛИЦЫ РЕБЕР ШНЕНЫйЕГО ВЕСА . ССЕДИНЯ-•= С ющих КАИАУЙ НИЫБРАШУМ КРШИНУ С ЩОЙ-Н!}БУАЬ Ш* «= С FAHHOB "С

47=. 200 СО 300 13 eljUUHUM 1175=. VTX-UNCHSNII3)

1175=. KEWCST и CCVTXiNEXTj

1175=. IF[LlCHT(l3) .LE. NEWCSTJ CO TO 300

151=. VERTEX! 13) "NEXT

151- LIGHT{I3J » NEWCST

1175a 30D CONTINUE

- С СПЕКАНИЕ РЕБРА С НАИНЕНЬШИН БЕСОИ « СбЕДЛМШ НЕВЫБРАННУЮ ВЕРШИНУ С ШРАИНОЙ

«С

48=. 350 NEWVTX »1 46=. LEAST - LIGHT(I) 48=. во ЧОО 14 - Z.NUHUH 1176=. 1F[LICHT{14) .GE. LEAST) GO TO ЧСв

122» LEAST eLIGHTil4J

12?=" NEWVTX 14

1176=> 400 CONTINUE

Рис. 4.2.1. Продолжение

«с

гШЧЕИК РЕБРА Е ОДМВ

4S=» EDGES = EDGES + 1

4S=» MEXT = UNCHSNtNEWVTX}

4S=» FROMtEDGES) = NEXT

Че=г TO (EDGES) = VERTEX(NEVVTX)

48= COSKEDGES) = LEAST

Ча= VEIGHT =. WEIGHT + LEAST

«=C ИСКЛЮЧЕНИЕ ВНОВЬ ВЫБРАННОЙ ВЕРШИНЫ ИЗ СПИСКА НЕВЫБ-

=С РА ИНЫХ

48=» LICHTtNEWVTX) = LIGHT(NUMUNJ

48= UNCHSN(NEWVTX) = UNCreN(numijn)

Че= VERTEX(HEWVTX) = VERTEX(NUMUN) = с

» с ОСТАЛИСЬ ЛИ НЕВЫЕРАННЫЕ ВЕРШИНЫ

Чё=, Минин = NUMUN - 1

48= * 1F(NUMUN .GE. 2) GO TO ZOO

1= VTX = UNCIfiNd)

1= NEWCST = C(VTX,next)

4= IF[L1GHT(1) .LE. NEWCST] GO TO 5QQ

C= VERTEX (1) = NEXT

C= LIGHTd) = NEWCST

1 500 EDGES = EDGES + 1

1= FROK(EDGES) =. V-TX

1= TO(EDGES) = VERTEXd)

J- COST(EDGES) = LIGHTdJ

1= WEIGHT = WEIGHT + U16HTC1)

1 fiETURN ЕЮ

Рис. 4.2.1. Продолжение

Чтобы ВЫЯСНИТЬ, какова действительная экономия машинного времени в результате таких изменений, следовало бы несколько раз прогнать обе программы на случайных сетях различного размера.

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

Наконец, рассмотрим проблему проверки вычислительной сложности подпрограммы PRIM посредством измерения времени ее выполнения. Эта попытка окажется не такой уж сложной, но она подскажет нам некоторые идеи.

Можно зафиксировать время центрального процессора, которое потребовалось программе на данном прогоне. Мы могли бы также опрашивать часы непосредственно перед началом выполнения основной части программы и непосредственно после окончания и печатать разность времен.

Недостатком этого метода является присущая ему неточность, обусловленная неточностью измерения времени. Многие компьютеры способны выполнять тысячи команд за единичное изменение показаний часов. Например, на CDC 6400 время измеряется с точностью три десятичных знака (0.001 с), хотя время выполнения основных команд в некотором операторе может оказаться приблизительно равным 10~" с. Существуют также различия в способах изменения показаний часов, и это вносит трудиоизмеримую ошибку.

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

Непосредственно перед инициализацией переменных (перед установкой их начальных значений) в подпрограмме PRIM вставим оператор вида

TIM1N = SECOND (Т)

где SECOND (Т) - локально определенная системная функция с вещественными значениями, использующая фиктивный аргумент Т. Эта функция дает время с точностью до нескольких миллисекунд.

Так как программа завершает свою работу по отысканию ОДМВ оператором RETURN, вставим перед этим оператором еще два:

TIMOUT = SECOND (Т) Т1МЕ(1) = TIMOUT-TIMIN

которые опрашивают часы вторично и записывают разность показаний в новый массив Т1МЕ(1).

В качестве источника входных данных для тестовых прогонов воспользуемся локально определенным генератором случайных чисел RANF(O.O), генерирующим случайные полные сети с М вершинами. Это может делать следующий фрагмент программы:

00 ЮМ. мм

К=Н-1

DO 10 J = K,M

С(1. J) = C(J, I)=U INT(RANF(0.0) * 1000000.0) iO CONTINUE

Функция RANF(O.O) генерирует случайное вещественное число в пределах от 0.0 до 1.0; функция INT выделяет целую часть вещественного числа RANF(0.0)Xl 000 000.0; мы добавляем 1, чтобы гарантировать отсутствие весов, равных О, и произвольно решаем, что все веса