Cтраница 4
Использование абстрактных типов данных в языках программирования как функциональных, так и императивных стало обычным явлением, поскольку обеспечивает программиста более мощными выразительными средствами, разрешая описывать объекты, с которыми работает программа, наиболее естественным для решаемой задачи способом. Эти преимущества хорошо известны, и, в частности, в первой части книги были разъяснены достоинства сильно типизированного функционального языка. Здесь мы не повторяем этих аргументов. К сожалению, присущие абстрактным типам структуры редко соотносятся с обычно очень ограниченной структурой областей хранения в памяти ма-шины, поэтому реализация их неэффективна как по объему памяти, необходимому для объектов этих типов, так и по времени выборки элементов из таких объектов. Неоптимизированное представление составных объектов данных в памяти просто связывает ячейки памяти в точном соответствии со структурой типа объекта с использованием указателей и кучи, как обсуждалось в гл. Однако в некоторых структурах данных имеется определенное упорядочение объектов и доступ к структурам осуществляется в соответствии с этим упорядочением - самым очевидным примером являются списки. В таких случаях, очевидно, было бы наиболее эффективным применение естественного порядка элементов памяти путем занесения последовательных абстрактных объектов в смежные блоки памяти, что ускоряет и операцию запоминания, обычно реализуемую машинной операцией MOVE, и операцию выборки элемента, использующей индексацию. Конечно, не для всех компьютеров смежное размещение элементов хранения является обязательно оптимальным. Для машин с параллельной архитектурой, например, более подходящей структурой для динамических объектов может быть бинарное, дерево, с которым стал бы возможен независимый, одновременный доступ к его компонентам со стороны нескольких процессоров. Для структурированных данных с компонентами, которые можно обрабатывать в любом порядке, такое решение было бы действительно оптимальным, и поэтому можно было бы список представить подобным деревом. [46]