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