WikiDer > CDR кодирование

CDR coding

В Информатика CDR кодирование это сжатый представление данных для Лисп связанные списки. Он был разработан и запатентован Лаборатория искусственного интеллекта Массачусетского технологического института, и реализовано в компьютер оборудование в ряде Лисп-машины получено из MIT CADR.

Кодирование CDR на самом деле является довольно общей идеей; всякий раз, когда объект данных А заканчивается в Справка в другую структуру данных B, мы можем вместо этого разместить структуру B там, перекрываясь и сбегая с конца А. Таким образом мы освобождаем место, необходимое для ссылки, которое может увеличиться, если делать это много раз, а также улучшаем местонахождение ссылки, повышая производительность на современных машинах. Трансформация особенно эффективна для минусысписки, для которых он был создан; мы освобождаем примерно половину пространства для каждого узла, на котором выполняем это преобразование.

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

В присутствии изменяемые объекты, Кодирование CDR становится более сложным. Если ссылка обновлена, чтобы указывать на другой объект, но в настоящее время объект хранится в этом поле, объект должен быть перемещен вместе с любыми другими указателями на него. Такие действия обычно не только дороги или невозможны, но и со временем вызывают фрагментация магазина. Этой проблемы обычно удается избежать, используя кодирование CDR только на неизменный структуры данных.

Развернутые связанные списки являются более простыми и часто более производительными, чем кодирование CDR (без «тегированных указателей»; обычно меньше фрагментации).[нужна цитата] Для коротких списков кодирование CDR использует наименьшее количество места.

внешние ссылки

  • Марк Кантровиц; Барри Марголин (ред.). "(2-9) Что такое CDR-кодирование?". FAQ: Часто задаваемые вопросы по Lisp. Advameg, Inc. Получено 2011-10-09.
  • Аллен, Джон (1978). Анатомия Лиспа. Макгроу-Хилл.