Пособие по практике программирования
Если эти функции окажутся слишком
Если эти функции окажутся слишком медленными, их можно улучшить с помощью технологий, описанных ранее. В C++ переопределение операторов позволяет сделать доступ к битам похожим на простое индексирование.
Не храните то, что можете без труда вычислить. Надо сказать, что подобные изменения — не самые эффективные; они похожи на тонкую настройку кода. Глобальные улучшения, как правило, достигаются только подбором более удачной структуры данных и соответствующим изменением алгоритма. Приведем пример. Много лет назад к одному из нас обратился за помощью наш коллега: он пытался производить некоторые вычисления над матрицей, которая была так велика, что для того, чтобы она уместилась в памяти, приходилось перезагружать компьютер, сильно урезая операционную систему. Очень хотелось найти какую-нибудь альтернативу, потому что работать в подобном режиме было ужасно неудобно. Мы сразу попросили рассказать, что же представляет собой эта матрица, и выяснили, что она содержала целые числа, большая часть из которых была нулями' . И лишь менее 5 % элементов матрицы были отличны от нуля. Подобная структура тут же навела нас на мысль о представлении, в котором хранились бы только ненулевые элементы матрицы, а доступ к каждому элементу m[i][j] заменялся бы вызовом функции m(i, j ). Существует несколько способов хранить данные. Наверное, самый простой из них — это массив указателей, по одному на столбец, каждый из которых указывает на компактный массив номеров строк и соответствующих значений. При такой организации на каждый ненулевой элемент тратится больше места, однако суммарное место все же экономится; доступ к каждому элементу получается более медленным, но это все равно быстрее, чем перезагружать машину. Наш коллега принял наше предложение и был вполне доволен результатом.
Аналогичный подход мы использовали и при решении современного варианта этой проблемы. Некая система проектирования должна была представлять данные о виде поверхности и силе радиосигнала, относящиеся к достаточно большим площадям (от 100 до 200 километров в поперечнике), с разрешением в 100 метров. Сохранение этих данных в одном большом прямоугольном массиве неизбежно привело бы к переполнению памяти на машинах, для которых эта система разрабатывалась, и, соответственно, к активному дисковому обмену. Однако было ясно, что для достаточно больших территорий данные о поверхности Земли и о силе сигнала будут одинаковы, так что для решения проблемы можно было применить иерархическое представление данных, при котором регионы с одинаковыми параметрами хранились в одном элементе.
Вариации на эту тему встречаются на практике достаточно часто, и их проявления различны, но для решения можно применять один и тот же подход: храните одинаковые значения в неявном виде или просто в компактной форме, а время и пространство тратьте на оставшиеся значения. Если одинаковые данные действительно встречаются в вашей задаче достаточно часто, вы сможете добиться впечатляющих результатов.
Программа должна быть организована таким образом, чтобы специфическое представление данных сложного типа было спрятано в классе или в наборе функций, оперирующих внутренними типами данных. Подобная предосторожность даст гарантию, что возможные изменения в представлении данных не затронут остальную часть программы.
Проблемы эффективного использования места иногда проявляются и по отношению к внешнему представлению информации — и к преобразованию, и к хранению. В общем и целом, всегда, когда это возможно, информацию лучше хранить в текстовом виде, а не в каком-то двоичном представлении. Текст хорошо переносится, удобно читается; для его обработки создано великое множество инструментов; двоичное же представление лишено этих преимуществ. Аргументом в защиту двоичных данных служит обычно "скорость", однако к нему стоит относиться с изрядной долей скептицизма, поскольку различия между текстовой и двоичной формой, как правило, не столь глобальны.
Более эффективное распределение пространства зачастую покупается ценой увеличения времени исполнения программы. Некое приложение должно было передавать большой рисунок из одной программы в другую. Рисунки в достаточно простом формате РРМ занимали, как правило, около мегабайта, так что мы подумали, что было бы гораздо быстрее кодировать их для передачи в сжатом формате GIF, — тогда файлы получались бы размером примерно 50 килобайтов. Однако кодирование и декодирование GIF занимало столько времени, что это сводило на нет всю экономию от передачи файла меньшего размера, то есть мы ничего не выгадывали. Код для обработки формата GIF состоял примерно из 500 строк, а для РРМ — из 10. Таким образом, для облегчения поддержки кода мы отказались от преобразования в GIF, и программа до сих пор работает с форматом РРМ. Естественно, если бы речь шла о передаче файлов по сети, то предпочтение было бы отдано формату GIF.
<
