กลับไปหน้าบทความ

อ่าน 2 นาที

การแลกเปลี่ยนระหว่างกาลอวกาศ

ใน วิทยาการคอมพิวเตอร์ การแลกเปลี่ยนระหว่าง พื้นที่ จัดเก็บข้อมูลและเวลา (หรือที่รู้จักกันในชื่อ การแลกเปลี่ยนระหว่างเวลาและหน่วยความจำ หรือ...

การแลกเปลี่ยนระหว่างกาลอวกาศ

ในวิทยาการคอมพิวเตอร์ การแลกเปลี่ยนระหว่าง พื้นที่จัดเก็บข้อมูลและเวลา (หรือที่รู้จักกันในชื่อการแลกเปลี่ยนระหว่างเวลาและหน่วยความจำหรือความต่อเนื่องของพื้นที่และเวลาเชิงอัลกอริทึม ) คือการแลกเปลี่ยนที่อัลกอริทึมหรือโปรแกรมใช้พื้นที่จัดเก็บข้อมูลมากขึ้น แต่ใช้เวลาน้อยลง โดยที่พื้นที่จัดเก็บข้อมูล ในที่นี้ หมายถึง พื้นที่จัดเก็บข้อมูล ที่ใช้ในการทำงาน ( เช่น RAM , HDDเป็นต้น) และเวลาหมายถึงเวลาที่ใช้ในการทำงาน (เช่น เวลา ในการคำนวณหรือเวลาตอบสนอง )

ประโยชน์ของการแลกเปลี่ยนระหว่างพื้นที่และเวลาที่กำหนดไว้จะได้รับผลกระทบจาก ต้นทุน คงที่และต้นทุนผันแปร ที่เกี่ยวข้อง (เช่น ความเร็ว ของ CPUพื้นที่จัดเก็บข้อมูล) และมีแนวโน้มที่จะลดลงตามผลตอบแทนที่ลดลง

ประวัติศาสตร์

การใช้ประโยชน์ทางชีววิทยาจากการแลกเปลี่ยนระหว่างเวลาและความทรงจำสามารถพบได้ในพฤติกรรมของสัตว์ ในระยะแรกเริ่ม การใช้ความรู้ที่เก็บไว้หรือการเข้ารหัสปฏิกิริยาต่อสิ่งเร้าเป็น "สัญชาตญาณ" ในดีเอ็นเอช่วยหลีกเลี่ยงความจำเป็นในการ "คำนวณ" ในสถานการณ์ที่สำคัญต่อเวลา สำหรับคอมพิวเตอร์นั้นตารางค้นหา (lookup table)ได้ถูกนำมาใช้ตั้งแต่ระบบปฏิบัติการรุ่นแรกๆ แล้ว

ในปี พ.ศ. 2523 Martin Hellmanเสนอให้ใช้การแลกเปลี่ยนระหว่างเวลาและหน่วยความจำสำหรับ การ วิเคราะห์การเข้ารหัส เป็นครั้งแรก [ 1 ]

ประเภทของการแลกเปลี่ยน

ตารางค้นหาเทียบกับการคำนวณใหม่

สถานการณ์ทั่วไปอย่างหนึ่งคืออัลกอริทึมที่เกี่ยวข้องกับตารางค้นหา : การใช้งานอาจรวมถึงตารางทั้งหมด ซึ่งช่วยลดเวลาในการคำนวณ แต่เพิ่มปริมาณหน่วยความจำที่ต้องการ หรืออาจคำนวณรายการในตารางตามที่ต้องการ ซึ่งจะเพิ่มเวลาในการคำนวณ แต่ลดความต้องการหน่วยความจำลง

ดัชนีฐานข้อมูลเทียบกับการสแกนตาราง

ระบบจัดการฐานข้อมูล (Database Management Systems) มีความสามารถในการสร้าง โครงสร้างข้อมูล ดัชนีฐานข้อมูล ดัชนีช่วยเพิ่มความเร็วในการค้นหาข้อมูล แต่ต้องใช้พื้นที่จัดเก็บเพิ่มเติม หากไม่มีดัชนีการค้นหาข้อมูลที่ต้องการอาจต้อง ใช้เวลานาน โดยการสแกนทั้งตาราง

ข้อมูลที่ถูกบีบอัดเทียบกับข้อมูลที่ไม่ได้บีบอัด

หลักการแลกเปลี่ยนระหว่างพื้นที่จัดเก็บและเวลาสามารถนำมาใช้กับปัญหาการจัดเก็บข้อมูลได้ หากจัดเก็บข้อมูลโดยไม่บีบอัด จะใช้พื้นที่มากกว่า แต่การเข้าถึงจะใช้เวลาน้อยกว่าหากจัดเก็บข้อมูลแบบบีบอัด (เนื่องจากการบีบอัดข้อมูลช่วยลดปริมาณพื้นที่ที่ใช้ แต่ต้องใช้เวลาในการทำงานของอัลกอริทึมการคลายการบีบอัด ) ขึ้นอยู่กับกรณีเฉพาะของปัญหา วิธีการใดวิธีการหนึ่งก็สามารถใช้งานได้จริง นอกจากนี้ยังมีบางกรณีที่สามารถทำงานกับข้อมูลที่บีบอัดได้โดยตรง เช่น ในกรณีของดัชนีบิตแมป ที่บีบอัด ซึ่งการทำงานกับข้อมูลที่บีบอัดจะเร็วกว่าการทำงานโดยไม่บีบอัด

การเรนเดอร์ภาพใหม่เทียบกับการบันทึกภาพ

การเก็บเฉพาะ ซอร์สโค้ด SVGของภาพเวกเตอร์แล้วแสดงผลเป็นภาพบิตแมปทุกครั้งที่มีการร้องขอหน้าเว็บนั้นเป็นการแลกเปลี่ยนเวลาเพื่อพื้นที่จัดเก็บ กล่าวคือ ใช้เวลามากขึ้น แต่ใช้พื้นที่น้อยลง ในทางกลับกัน การแสดงผลภาพเมื่อมีการเปลี่ยนหน้าเว็บและเก็บภาพที่แสดงผลแล้วไว้นั้นเป็นการแลกเปลี่ยนพื้นที่จัดเก็บเพื่อเวลา กล่าวคือ ใช้พื้นที่มากขึ้น แต่ใช้เวลาน้อยลง เทคนิคนี้โดยทั่วไปเรียกว่าการแคช (caching )

โค้ดที่สั้นกว่าเมื่อเทียบกับการคลายลูป

การใช้เทคนิคการ คลายลูป (loop unrolling ) อาจแลกเปลี่ยนขนาดโค้ดที่ใหญ่ขึ้นกับความเร็วของโปรแกรมที่สูงขึ้นได้เทคนิคนี้ทำให้โค้ดในแต่ละรอบของลูปยาวขึ้น แต่ช่วยประหยัดเวลาในการคำนวณที่จำเป็นสำหรับการย้อนกลับไปยังจุดเริ่มต้นของลูปในตอนท้ายของแต่ละรอบ

ตัวอย่างอื่นๆ

อัลกอริทึมที่ใช้ประโยชน์จากการแลกเปลี่ยนระหว่างพื้นที่และเวลา ได้แก่:

ดูเพิ่มเติม

  • Philippe Oechslin: การสร้างความสมดุลระหว่างเวลาในการประมวลผลรหัสลับที่รวดเร็วยิ่งขึ้น
  • กาลครั้งหนึ่งนานมาแล้ว - การแลกเปลี่ยนระหว่างความทรงจำ

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ การแลกเปลี่ยนระหว่างกาลอวกาศ

ใน วิทยาการคอมพิวเตอร์ การแลกเปลี่ยนระหว่าง พื้นที่ จัดเก็บข้อมูลและเวลา (หรือที่รู้จักกันในชื่อ การแลกเปลี่ยนระหว่างเวลาและหน่วยความจำ หรือ...

ประวัติศาสตร์

การใช้ประโยชน์ทางชีววิทยาจากการแลกเปลี่ยนระหว่างเวลาและความทรงจำสามารถพบได้ใน พฤติกรรมของสัตว์ ในระยะแรกเริ่ม การใช้ความรู้ที่เก็บไว้หรือการเข้ารหัสปฏิกิริยาต่อสิ่งเร้าเป็น "สัญชาตญาณ" ในดีเอ็นเอช่วยหลีกเลี่ยงความจำเป็นในการ "คำนวณ" ในสถานการณ์ที่สำคัญต่อเวลา...

ตารางค้นหาเทียบกับการคำนวณใหม่

สถานการณ์ทั่วไปอย่างหนึ่งคืออัลกอริทึมที่เกี่ยวข้องกับ ตารางค้นหา : การใช้งานอาจรวมถึงตารางทั้งหมด ซึ่งช่วยลดเวลาในการคำนวณ แต่เพิ่มปริมาณหน่วยความจำที่ต้องการ หรืออาจคำนวณรายการในตารางตามที่ต้องการ ซึ่งจะเพิ่มเวลาในการคำนวณ แต่ลดความต้องการหน่วยความจำลง

ดัชนีฐานข้อมูลเทียบกับการสแกนตาราง

ระบบจัดการฐานข้อมูล (Database Management Systems) มีความสามารถในการสร้าง โครงสร้างข้อมูล ดัชนีฐาน ข้อมูล ดัชนีช่วยเพิ่มความเร็วในการค้นหาข้อมูล แต่ต้องใช้พื้นที่จัดเก็บเพิ่มเติม หากไม่มีดัชนีการค้นหาข้อมูลที่ต้องการอาจต้อง ใช้เวลานาน โดยการสแกนทั้งตาราง