Пособие по практике программирования
Стратегии ускорения
Перед тем как начинать изменять программу, чтобы сделать ее более быстрой, убедитесь, что она действительно работает слишком медленно, а затем используйте инструменты для замера времени и профилировщики для выяснения, на что именно уходит время. После того как вы получили представление о том, что происходит в действительности, можно следовать различным стратегиям ускорения. Мы перечислили некоторые из них, упорядочив их по уменьшению эффективности.
Улучшайте алгоритм и структуру данных. Наиболее важным фактором в уменьшении времени работы программы является выбор алгоритма или структуры данных — между эффективным алгоритмом и неэффективным разница может быть просто огромной. Для нашего спам-фильт-ра мы изменили структуру данных и получили выигрыш в десять раз; еще более внушительным улучшением могло стать применение нового алгоритма, который бы сократил вычисления на порядок, скажем с 0(п2) до 0(п log n). Мы уже обсуждали эту тему в главе 2, так что теперь не будем к ней возвращаться.
Убедитесь в том, что сложность такая, как надо; если она завышена, то именно в ней может крыться источник недостаточной производительности. Этот, линейный на первый взгляд, алгоритм для сканирования строки
