อ่าน 1 นาที
การเข้ารหัส CDR
ใน วิทยาการคอมพิวเตอร์ การเข้ารหัส CDR เป็นรูป แบบการแสดงข้อมูล แบบบีบอัด สำหรับ รายการเชื่อมโยงของ ภาษาลิสป์ ซึ่งได้รับการพัฒนาและจดสิทธิบัตรโดย ห้องปฏิบัติการปัญญาประดิษฐ์ของ...
การเข้ารหัส CDR
ในวิทยาการคอมพิวเตอร์การเข้ารหัส CDRเป็นรูปแบบการแสดงข้อมูลแบบบีบอัด สำหรับรายการเชื่อมโยงของภาษาลิสป์ซึ่งได้รับการพัฒนาและจดสิทธิบัตรโดยห้องปฏิบัติการปัญญาประดิษฐ์ของ MITและนำไปใช้ใน ฮาร์ดแวร์ คอมพิวเตอร์ ในเครื่องลิ ส ป์จำนวนหนึ่งที่พัฒนามาจาก MIT CADR
การเข้ารหัส CDR จริงๆ แล้วเป็นแนวคิดทั่วไป เมื่อใดก็ตามที่อ็อบเจ็กต์ข้อมูลAลงท้ายด้วยการอ้างอิงถึงโครงสร้างข้อมูลBเราสามารถวางโครงสร้างBเองลงไปแทนที่ โดยให้ทับซ้อนและต่อท้ายจากAการทำเช่นนี้จะช่วยประหยัดพื้นที่ที่จำเป็นสำหรับการอ้างอิง ซึ่งอาจเพิ่มขึ้นได้หากทำซ้ำหลายครั้ง และยังช่วยปรับปรุง ความใกล้ เคียงของการอ้างอิง (locality of reference)เพิ่มประสิทธิภาพบนเครื่องคอมพิวเตอร์สมัยใหม่ การแปลงนี้มีประสิทธิภาพเป็นพิเศษสำหรับ ลิสต์แบบ consที่สร้างขึ้นมาเพื่อใช้งาน เราจะประหยัดพื้นที่ได้ประมาณครึ่งหนึ่งสำหรับแต่ละโหนดที่เราทำการแปลงนี้
การแทนที่แบบนี้อาจทำได้ไม่เสมอไป เพราะอาจไม่มีพื้นที่ว่างเหลือมากพอหลังจากสิ้นสุดเซลล์ A ดังนั้น วัตถุบางชิ้นจะลงท้ายด้วยการอ้างอิงจริง และบางชิ้นจะลงท้ายด้วยวัตถุที่ถูกอ้างอิง และเครื่องจะต้องสามารถบอกได้โดยการอ่านเซลล์สุดท้ายว่าเป็นแบบไหน ซึ่งสามารถทำได้ในซอฟต์แวร์ด้วยการใช้พอยเตอร์แบบมีแท็ก แม้ว่าจะไม่ค่อยมีประสิทธิภาพนัก ก็ตาม โดยพอยเตอร์ในตำแหน่งสุดท้ายจะถูกระบุแท็กอย่างเฉพาะเจาะจง แต่วิธีที่ดีที่สุดคือทำในฮาร์ดแวร์
ในกรณีที่มีอ็อบเจ็กต์ที่เปลี่ยนแปลงได้การเขียนโค้ด CDR จะซับซ้อนมากขึ้น หากมีการอัปเดตการอ้างอิงให้ชี้ไปยังอ็อบเจ็กต์อื่น แต่ปัจจุบันมีอ็อบเจ็กต์เก็บอยู่ในฟิลด์นั้นอยู่แล้ว จะต้องย้ายอ็อบเจ็กต์นั้น รวมถึงตัวชี้อื่นๆ ที่ชี้ไปยังอ็อบเจ็กต์นั้นด้วย การย้ายดังกล่าวไม่เพียงแต่มีค่าใช้จ่ายสูงหรือเป็นไปไม่ได้เท่านั้น แต่ในระยะยาวจะทำให้เกิดการแตกกระจายของที่เก็บข้อมูล ปัญหานี้มักจะหลีกเลี่ยงได้โดยการใช้การเขียนโค้ด CDR เฉพาะกับโครงสร้างข้อมูล ที่ไม่เปลี่ยนแปลงได้ เท่านั้น
ลิงก์ภายนอก
- Mark Kantrowitz; Barry Margolin (บรรณาธิการ). "(2-9) การเข้ารหัส CDR คืออะไร?" . FAQ: คำถามที่พบบ่อยเกี่ยวกับ Lisp . Advameg, Inc . สืบค้นเมื่อ2011-10-09 .
- L. Peter Deutsch: เครื่อง LISP ที่มีโปรแกรมขนาดกะทัดรัดมาก IJCAI 1973, หน้า 697 - 703
- Greenblatt, R., รายงานความคืบหน้าของเครื่อง LISP, บันทึกช่วยจำ 444, AILab., MIT, เคมบริดจ์, แมสซาชูเซตส์, ส.ค. 1977
- L. Peter Deutsch: ประสบการณ์กับระบบ Interlisp ที่เขียนด้วยไมโครโปรแกรม MICRO 11: รายงานการประชุมเชิงปฏิบัติการประจำปีครั้งที่ 11 เรื่องไมโครโปรแกรมมิ่ง พฤศจิกายน 1978 หน้า 128–129
- อัลเลน, จอห์น (1978). กายวิภาคของ Lisp . แมคกรอว์-ฮิลล์.หน้า 399-401
 | บทความเกี่ยวกับการเขียนโปรแกรมคอมพิวเตอร์ชิ้นนี้ยังไม่สมบูรณ์คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มข้อมูลที่ขาดหายไป |