Многопроходные алгоритмы. Эти алгоритмы совершают несколько проходов по входным данным, продвигаясь каждый раз немного вперед. Ранее мы рассмотрели 27-проходный алгоритм. В задаче 1 требуется разработка 2-проходного алгоритма.
Компромисс "память-время" и случай невыполнения. Программистский фольклор и теория о компромиссе "память-время" сообщают следующее: дольше работающей программе может потребоваться меньший объем памяти. Например, в 2-проходном алгоритме, приведенном в решении задачи 1, удваивается время работы, чтобы вдвое сократить занимаемую память. Однако, как показывает мой опыт, гораздо чаще при уменьшении объема памяти, требующейся программе, уменьшается и время ее работы1. Эффективная по объему занимаемой памяти побитовая структура существенно сокращает время сортировки. В данной задаче уменьшение объема памяти привело к сокращению времени по двум причинам: меньший объем данных, которые надо обработать, приводит к сокращению времени обработки, а хранение данных в ОЗУ, а не на диске, устраняет накладные расходы на доступ к диску. Конечно, улучшение обоих параметров стало возможным только потому, что исходный вариант программы был далеко не оптимальным.
Простота замысла. Антуан де Сент-Экзюпери, французский писатель и авиатор, говорил: "Конструктор знает, что он достиг совершенства не тогда, когда нечего больше добавить, а тогда, когда нечего больше убрать". Многие программисты должны оценить свою работу по этому критерию. Простые программы обычно более надежны, "здравомыслящи", эффективны, чем их сложные родственники, их намного проще создавать и сопровождать.
Этапы разработки программы. Рассмотренный пример иллюстрирует процесс разработки, подробно описанный в разд. 11.4.
1.6. ЗАДАЧИ
Подсказки и решения для некоторых задач можно найти в конце книги. 1. Мой собеседник - программист - сказал, что в его распоряжении есть
около 1000 свободных слов в памяти, но в рассмотренном фрагменте
