Основы объектно-ориентированного проектирования


Слияние списка и стражей


(Этот раздел описывает улучшенную оптимизацию и может быть опущен при первом чтении.)

Пример связного списка со стражами может быть улучшен благодаря еще одной оптимизации, которая реально используется в последней версии библиотек ISE. Мы бегло ее рассмотрим, поскольку она достаточно специфична и не носит общего характера. Такие оптимизации, тщательно выполняемые, должны осуществляться только для широко используемых компонентов повторного использования. Другими словами, они не для домашних разработок.

Можно ли получить преимущества от стражей без соответствующих потерь памяти? При рассмотрении их концепции отмечалось, что их можно рассматривать фиктивно, но тогда мы потеряем критически важную оптимизацию, позволившую нам написать тело forth следующим образом:

index := index + 1 previous := active active := active.right

без дорогих проверок предыдущей версии. Мы избежали тестов, будучи уверенными, что active не равно Void, когда список не находится в состоянии after. Это следствие утверждения инварианта (active = Void) = after; верного потому, что у нас есть настоящее звено - страж, доступный как active, даже если список пуст.

Для других программ, отличных от forth, оптимизация не столь существенна. Но forth, как отмечалось, - насущная потребность, "хлеб и масло" клиентов, обрабатывающих списки. Из-за последовательной природы списков типичное использование имеет вид:

from your_list.start until your_list.after loop ...; your_list.forth end

Нет ничего необычного, если при построении профиля, измеряя, как выполняются вычисления, вы обнаружите, что большая доля времени приходится на работу forth. Так что стоило заплатить за ее оптимизацию, поскольку она обеспечивает кардинальное улучшение производительности, будучи свободной от тестов.

За выигрыш во времени мы заплатили, как обычно, проигрышем в памяти, - теперь каждый список имеет дополнительный элемент, не хранящий информации. Это кажется проблемой лишь в случае большого числа коротких списков, иначе относительные потери несущественны.


Начало  Назад  Вперед



Книжный магазин