Перейдем от разбора большой программы к разбору нескольких небольших функций. Каждая функция — это задача, с которой мне приходилось неоднократно сталкиваться. Каждый раз большая часть времени тратилась на выполнение зтих функций и для устранения задержек использовались стандартные методы.
Деление с остатком
В разделе 2.3 (см. главу 2) предлагается три алгоритма циклического сдвига. В решении 2.3 реализуется алгоритм «с трюком», содержащий приведенную ниже операцию во внутреннем цикле:
k = (j + rotdi st) % n.
Данные о затратах на простейшие операции из приложения 3 говорят нам, что оператор вычисления остатка от деления может быть очень ресурсоемким. Большинство арифметических операций выполняются на моем компьютере за время порядка 10 не, тогда как деление с остатком требует около 100 не. Время выполнения программы можно уменьшить, заменив приведенную выше команду на следующий текст:
k = j + rotd п s t
if (к >= n) к - = n :
Здесь мы заменяем «дорогостоящий» оператор % одной операцией сравнения и редко выполняющейся операцией вычитания. Но даст ли зто выигрыш программе в целом?
В первом эксперименте программа выполнялась со сдвигом rotdist, равным единице. Время выполнения уменьшилось со 119п не до 57п не. Программа работала быстрее в два раза, причем ускорение на 62 не было близким к предсказываемому теорией, исходя из затрат на операции.
В следующем эксперименте я сделал rotdist равным 10 и с удивлением обнаружил, что время выполнения обоих вариантов программы совпадало: 206л не. Эксперименты, в результате которых был получен график в решении задачи 4 к главе 2, привели меня к следующей мысли: при rotdist= 1 алгоритм обращался к памяти последовательно и время тратилось на операцию деления с остатком. Для rotdist = 10 мы обращались к каждой десятой ячейке памяти и затраты на копирование данных из оперативной памяти в кэш становились более существенными.
Программисты прошлого твердо знали по опыту, что не было смысла пытаться улучшить вычислительную часть программы, которая большую часть времени тратила на ввод и вывод данных. В современных архитектурах также бесполезно уменьшать затраты на вычисления, когда основное время уходит на доступ к памяти.
Опубликовал vovan666
April 17 2013 00:01:02 ·
0 Комментариев ·
3637 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
