Кодирование CDR - CDR coding
В информатике кодирование CDR - это сжатое представление данных для связанных списков Лиспа . Он был разработан и запатентован Лабораторией искусственного интеллекта Массачусетского технологического института и реализован в компьютерном оборудовании в ряде машин Lisp, созданных на основе MIT CADR .
Кодирование CDR на самом деле является довольно общей идеей; всякий раз , когда объект данных А заканчивается в качестве ссылки на другую структуру данных B , мы можем вместо того, чтобы поместить структуру B непосредственно там, перекрывающиеся и работают от конца A . Делая это, мы освобождаем пространство, необходимое для ссылки, которое может увеличиться, если делать много раз, а также улучшаем локальность ссылки , повышая производительность на современных машинах. Преобразование особенно эффективно для списков на основе cons- списка, для которых оно было создано; мы освобождаем примерно половину пространства для каждого узла, на котором выполняем это преобразование.
Не всегда возможно выполнить эту замену, потому что может не оказаться достаточно большого фрагмента свободного пространства за концом A. Таким образом, некоторые объекты будут заканчиваться реальной ссылкой, а некоторые - объектом ссылки, и машина должна быть в состоянии определить, прочитав последнюю ячейку, что это за ячейка. Это может быть достигнуто с некоторой неэффективностью в программном обеспечении за счет использования помеченных указателей , которые позволяют специально пометить указатель в конечной позиции как таковой, но лучше всего это сделать аппаратно.
При наличии изменяемых объектов кодирование CDR становится более сложным. Если ссылка обновлена, чтобы указывать на другой объект, но в настоящее время объект хранится в этом поле, объект должен быть перемещен вместе с любыми другими указателями на него. Такие действия обычно не только дороги или невозможны, но и со временем вызывают фрагментацию магазина. Этой проблемы обычно удается избежать, используя кодирование CDR только для неизменяемых структур данных.
Внешние ссылки
- Марк Кантровиц; Барри Марголин (ред.). "(2-9) Что такое CDR-кодирование?" . FAQ: Часто задаваемые вопросы по Lisp . Advameg, Inc . Проверено 9 октября 2011 .
- Аллен, Джон (1978). Анатомия Лиспа . Макгроу-Хилл.
 |
Эта статья о компьютерном программировании - незавершенная . Вы можете помочь Википедии, расширив ее . |