Эппель обрабатывал наиболее дорогостоящую ситуацию с близко расположенными объектами
• В разделе 6.1 Эппель обрабатывал наиболее дорогостоящую ситуацию с близко расположенными объектами со специальным уменьшенным шагом по времени, что позволило во всех остальных случаях использовать более аффективный шаг большей величины.
• Сопрограммы. Многопроходный алгоритм может быть переделан в однопроходный с помощью сопрограмм.
• В программе поиска анаграмм из раздела 2.8 используется канал, который может быть реализован как набор сопрограмм.
• Трансформация рекурсивных функций. Время выполнения рекурсивных функций может быть уменьшено применением следующих трансформаций:
• замена рекурсии итерацией, как в программах со списками и двоичными деревьями в главе 13;
• преобразование рекурсии в итерацию использованием явного стека (если функция содержит только один рекурсивный вызов себя самой, нет необходимости сохранять на стеке адрес возврата);
• если в самом конце тела функции делается вызов этой же функции, его можно заменить на безусловный переход к началу функции. Это часто называется «удалением концевой рекурсии». Код в решении 11.9 является потенциальным кандидатом на такое преобразование. Такое ветвление часто может быть преобразовано в цикл, н оптимизирующие компиляторы обычно так и поступают;
• часто оказывается более эффективным решать небольшие подзадачи внешними процедурами, а не выполнять рекурсию до задачи размером 0 или 1. Функция qsort4 из раздела 11.3 использует значение cutoff около 50.
• Параллелизм. Программа должна быть написана так, чтобы максимальным образом использовать параллелизм аппаратуры, на которой она выполняется.
Составление выражений
Главная
Каталог файлов
