Kodowanie CDR - CDR coding
W informatyce kodowanie CDR jest skompresowaną reprezentacją danych dla list połączonych Lisp . Został opracowany i opatentowany przez Laboratorium Sztucznej Inteligencji MIT i wdrożony w sprzęcie komputerowym w wielu maszynach Lisp wywodzących się z MIT CADR .
Kodowanie CDR jest w rzeczywistości dość ogólną ideą; gdy obiekt danych A końce w odniesieniu do innej struktury danych B , można zamiast tego umieścić strukturę B sam tam i nakładania działa w kierunku jej końca A . W ten sposób zwalniamy miejsce wymagane przez odniesienie, które może się sumować, jeśli jest wykonywane wiele razy, a także poprawiamy lokalność odniesienia , zwiększając wydajność na nowoczesnych maszynach. Transformacja jest szczególnie skuteczna w przypadku list opartych na cons , dla których została utworzona; zwalniamy około połowy miejsca dla każdego węzła, na którym wykonujemy tę transformację.
Nie zawsze jest możliwe wykonanie tej zamiany, ponieważ może nie być wystarczająco dużego kawałka wolnego miejsca poza końcem A. W związku z tym niektóre obiekty kończą się rzeczywistym odniesieniem, a inne obiektem, do którego się odwołuje, a maszyna musi być w stanie stwierdzić, czytając ostatnią komórkę, która to jest. Można to osiągnąć przy pewnej nieefektywności oprogramowania przez użycie oznaczonych wskaźników , które umożliwiają oznaczenie wskaźnika w końcowej pozycji jako takie, ale najlepiej jest to zrobić sprzętowo.
W obecności zmiennych obiektów kodowanie CDR staje się bardziej złożone. Jeśli odniesienie jest aktualizowane tak, aby wskazywało na inny obiekt, ale obecnie ma obiekt przechowywany w tym polu, obiekt musi zostać przeniesiony wraz z innymi wskaźnikami do niego. Takie posunięcia są nie tylko zazwyczaj drogie lub niemożliwe, ale z czasem powodują fragmentację sklepu. Tego problemu można zwykle uniknąć, stosując kodowanie CDR tylko w niezmiennych strukturach danych.
Linki zewnętrzne
- Mark Kantrowitz; Barry Margolin (red.). „(2-9) Co to jest kodowanie CDR?” . FAQ: Często zadawane pytania dotyczące Lisp . Advameg, Inc . Źródło 2011-10-09 .
- Allen, John (1978). Anatomia Lispa . McGraw-Hill.
 |
Ten komputer programowania artykuł związane z modelem jest en . Możesz pomóc Wikipedii, rozbudowując ją . |