Здравствуйте! Начал читать книгу "Основы современных алгоритмов" и наткнулся на такой отрывок вначале первой главы.
Вобщем есть псевдокод какого-то алгоритма
| Код |
Рассмотрим, например, алгоритм подсчета числа вхождений различных символов в файл.
Алгоритм для решения такой задачи мог бы выглядеть примерно так:
for all 256 символов do
обнулить счетчик
end for
while в файле еще остались символы do
ввести очередной символ
увеличить счетчик вхождений прочитанного символа на единицу
end while
|
и есть разбор этого алгоритма, с которым я в принципе согласен
| Код |
Посмотрим на этот алгоритм. Он делает 256 проходов в цикле инициализации. Если во
входном файле N символов, то втором цикле N проходов. Возникает вопрос «Что же считать?».
В цикле for сначала инициализируется переменная цикла, затем в каждом проходе проверяется,
что переменная не выходит за границы выполнения цикла, и переменная получает приращение.
Это означает, что цикл инициализации делает 257 присваиваний (одно для переменной цикла
и 256 для счетчика), 256 приращений переменной цикла, и 257 проверок того,
что эта переменная находится в пределах границ цикла (одна дополнительная для остановки цикла).
Во втором цикле нужно сделать N + 1 раз проверку условия (+1 для последней проверки, когда файл пуст),
и N приращений счетчика.
Всего операций:
Приращения N + 256
Присваивания 257
Проверки условий N + 258
Таким образом, при размере входного файла в 500 символов в алгоритме делается 1771 операция,
из которых 770 приходится на инициализацию (43%). Теперь посмотрим, что происходит при
увеличении величины N. Если файл содержит 50 000 символов,
то алгоритм сделает 100 771 операцию, из которых только 770 связаны с инициализацией
(что составляет менее 1% общего числа операций).
Число операций инициализации не изменилось, но в процентном отношении
при увеличении N их становится значительно меньше.
|
Далее идёт такой текст:
| Код |
Теперь взглянем с другой стороны.
Данные в компьютере организованы таким образом,
что копирование больших блоков данных происходит с той же скоростью,
что и присваивание. Мы могли бы сначала присвоить 16 счетчикам начальное значение,
равное 0, а затем скопировать этот блок 15 раз, чтобы заполнить остальные счетчики.
Это приведет к тому, что в циклах инициализации число проверок уменьшится до 33,
присваиваний до 33 и приращений до 31. Количество операций инициализации
уменьшается с 770 до 97, то есть на 87%. Если же мы сравним полученный выигрыш
с числом операций по обработке файла в 50 000 символов, экономия составит менее 0.7%
(вместо 100 771 операций мы затратим 100 098). Заметим, что экономия по времени
могла бы быть даже больше, если бы мы сделали все эти инициализации без циклов,
поскольку понадобилось бы только 31 простое присваивание, но этот дополнительный
выигрыш дает лишь 0.07% экономии. Овчинка не стоит выделки.
|
В строках 2-5 написано то, что я собственно не понял. А именно: допустим мы
присвоили 16-ти счётчикам (16 разных переменных) начальное значение 0. Если я правильно понял,
это происходит перед циклом с 15-тью итерациями (который "копирует блок, чтобы заполнить остальные счётчики").
Не пойму, как это может происходить? Какой блок? Как этот блок копировать, да ещё и в цикле? |
