การแลกเปลี่ยนระหว่างกาลอวกาศ
ในวิทยาการคอมพิวเตอร์ การแลกเปลี่ยนระหว่าง พื้นที่จัดเก็บข้อมูลและเวลา (หรือที่รู้จักกันในชื่อการแลกเปลี่ยนระหว่างเวลาและหน่วยความจำหรือความต่อเนื่องของพื้นที่และเวลาเชิงอัลกอริทึม ) คือการแลกเปลี่ยนที่อัลกอริทึมหรือโปรแกรมใช้พื้นที่จัดเก็บข้อมูลมากขึ้น แต่ใช้เวลาน้อยลง โดยที่พื้นที่จัดเก็บข้อมูล ในที่นี้ หมายถึง พื้นที่จัดเก็บข้อมูล ที่ใช้ในการทำงาน ( เช่น RAM , HDDเป็นต้น) และเวลาหมายถึงเวลาที่ใช้ในการทำงาน (เช่น เวลา ในการคำนวณหรือเวลาตอบสนอง )
ประโยชน์ของการแลกเปลี่ยนระหว่างพื้นที่และเวลาที่กำหนดไว้จะได้รับผลกระทบจาก ต้นทุน คงที่และต้นทุนผันแปร ที่เกี่ยวข้อง (เช่น ความเร็ว ของ CPUพื้นที่จัดเก็บข้อมูล) และมีแนวโน้มที่จะลดลงตามผลตอบแทนที่ลดลง
ประวัติศาสตร์
การใช้ประโยชน์ทางชีววิทยาจากการแลกเปลี่ยนระหว่างเวลาและความทรงจำสามารถพบได้ในพฤติกรรมของสัตว์ ในระยะแรกเริ่ม การใช้ความรู้ที่เก็บไว้หรือการเข้ารหัสปฏิกิริยาต่อสิ่งเร้าเป็น "สัญชาตญาณ" ในดีเอ็นเอช่วยหลีกเลี่ยงความจำเป็นในการ "คำนวณ" ในสถานการณ์ที่สำคัญต่อเวลา สำหรับคอมพิวเตอร์นั้นตารางค้นหา (lookup table)ได้ถูกนำมาใช้ตั้งแต่ระบบปฏิบัติการรุ่นแรกๆ แล้ว
ในปี พ.ศ. 2523 Martin Hellmanเสนอให้ใช้การแลกเปลี่ยนระหว่างเวลาและหน่วยความจำสำหรับ การ วิเคราะห์การเข้ารหัส เป็นครั้งแรก [ 1 ]
ประเภทของการแลกเปลี่ยน
ตารางค้นหาเทียบกับการคำนวณใหม่
สถานการณ์ทั่วไปอย่างหนึ่งคืออัลกอริทึมที่เกี่ยวข้องกับตารางค้นหา : การใช้งานอาจรวมถึงตารางทั้งหมด ซึ่งช่วยลดเวลาในการคำนวณ แต่เพิ่มปริมาณหน่วยความจำที่ต้องการ หรืออาจคำนวณรายการในตารางตามที่ต้องการ ซึ่งจะเพิ่มเวลาในการคำนวณ แต่ลดความต้องการหน่วยความจำลง
ดัชนีฐานข้อมูลเทียบกับการสแกนตาราง
ระบบจัดการฐานข้อมูล (Database Management Systems) มีความสามารถในการสร้าง โครงสร้างข้อมูล ดัชนีฐานข้อมูล ดัชนีช่วยเพิ่มความเร็วในการค้นหาข้อมูล แต่ต้องใช้พื้นที่จัดเก็บเพิ่มเติม หากไม่มีดัชนีการค้นหาข้อมูลที่ต้องการอาจต้อง ใช้เวลานาน โดยการสแกนทั้งตาราง
ข้อมูลที่ถูกบีบอัดเทียบกับข้อมูลที่ไม่ได้บีบอัด
หลักการแลกเปลี่ยนระหว่างพื้นที่จัดเก็บและเวลาสามารถนำมาใช้กับปัญหาการจัดเก็บข้อมูลได้ หากจัดเก็บข้อมูลโดยไม่บีบอัด จะใช้พื้นที่มากกว่า แต่การเข้าถึงจะใช้เวลาน้อยกว่าหากจัดเก็บข้อมูลแบบบีบอัด (เนื่องจากการบีบอัดข้อมูลช่วยลดปริมาณพื้นที่ที่ใช้ แต่ต้องใช้เวลาในการทำงานของอัลกอริทึมการคลายการบีบอัด ) ขึ้นอยู่กับกรณีเฉพาะของปัญหา วิธีการใดวิธีการหนึ่งก็สามารถใช้งานได้จริง นอกจากนี้ยังมีบางกรณีที่สามารถทำงานกับข้อมูลที่บีบอัดได้โดยตรง เช่น ในกรณีของดัชนีบิตแมป ที่บีบอัด ซึ่งการทำงานกับข้อมูลที่บีบอัดจะเร็วกว่าการทำงานโดยไม่บีบอัด
การเรนเดอร์ภาพใหม่เทียบกับการบันทึกภาพ
การเก็บเฉพาะ ซอร์สโค้ด SVGของภาพเวกเตอร์แล้วแสดงผลเป็นภาพบิตแมปทุกครั้งที่มีการร้องขอหน้าเว็บนั้นเป็นการแลกเปลี่ยนเวลาเพื่อพื้นที่จัดเก็บ กล่าวคือ ใช้เวลามากขึ้น แต่ใช้พื้นที่น้อยลง ในทางกลับกัน การแสดงผลภาพเมื่อมีการเปลี่ยนหน้าเว็บและเก็บภาพที่แสดงผลแล้วไว้นั้นเป็นการแลกเปลี่ยนพื้นที่จัดเก็บเพื่อเวลา กล่าวคือ ใช้พื้นที่มากขึ้น แต่ใช้เวลาน้อยลง เทคนิคนี้โดยทั่วไปเรียกว่าการแคช (caching )
โค้ดที่สั้นกว่าเมื่อเทียบกับการคลายลูป
การใช้เทคนิคการ คลายลูป (loop unrolling ) อาจแลกเปลี่ยนขนาดโค้ดที่ใหญ่ขึ้นกับความเร็วของโปรแกรมที่สูงขึ้นได้เทคนิคนี้ทำให้โค้ดในแต่ละรอบของลูปยาวขึ้น แต่ช่วยประหยัดเวลาในการคำนวณที่จำเป็นสำหรับการย้อนกลับไปยังจุดเริ่มต้นของลูปในตอนท้ายของแต่ละรอบ
ตัวอย่างอื่นๆ
อัลกอริทึมที่ใช้ประโยชน์จากการแลกเปลี่ยนระหว่างพื้นที่และเวลา ได้แก่:
- อัลกอริทึม แบบก้าวเล็กก้าวใหญ่สำหรับการคำนวณลอการิทึมแบบไม่ต่อเนื่อง
- ตารางเรนโบว์ในวิทยาการเข้ารหัสลับ คือวิธีการที่ผู้โจมตีพยายามเอาชนะเวลาที่ใช้ในการโจมตีแบบเดาสุ่ม (brute-force attack ) ซึ่งใช้เวลานานมาก ตารางเรนโบว์ใช้ค่าที่คำนวณไว้ล่วงหน้าบางส่วนในพื้นที่แฮชของฟังก์ชันแฮชเข้ารหัสลับเพื่อถอดรหัสผ่านได้ภายในไม่กี่นาที แทนที่จะเป็นหลายสัปดาห์ การลดขนาดของตารางเรนโบว์จะเพิ่มเวลาที่ใช้ในการวนซ้ำในพื้นที่แฮช
- การโจมตี แบบ Meet -in-the-Middleใช้การแลกเปลี่ยนระหว่างพื้นที่และเวลาเพื่อค้นหากุญแจเข้ารหัสลับได้ภายในเวลาอันสั้นการเข้ารหัส (และพื้นที่) เมื่อเทียบกับที่คาดไว้การเข้ารหัส (แต่เท่านั้น)พื้นที่) ของการโจมตีที่ไร้เดียงสา
- การเขียนโปรแกรมแบบไดนามิกซึ่งสามารถลดความซับซ้อนเชิงเวลาของปัญหาได้อย่างมากโดยการใช้หน่วยความจำมากขึ้น
- การโจมตีแบบแลกเปลี่ยนเวลา/หน่วยความจำ/ข้อมูลซึ่งใช้การแลกเปลี่ยนระหว่างพื้นที่และเวลา โดยมีพารามิเตอร์เพิ่มเติมคือข้อมูล
ดูเพิ่มเติม
- ประสิทธิภาพของอัลกอริทึม
- ทฤษฎีการเร่งความเร็วของบลัม– ตัดความเป็นไปได้ในการกำหนดความซับซ้อนในการคำนวณให้กับฟังก์ชันใดๆ โดยพลการ
- ความซับซ้อนในการคำนวณ– ปริมาณทรัพยากรที่จำเป็นในการดำเนินการอัลกอริทึม
- ทรัพยากรการคำนวณ– แง่มุมหนึ่งของทฤษฎีความซับซ้อนในการคำนวณ
- ทฤษฎีบทของ Savitch – ความสัมพันธ์ระหว่างความซับซ้อนของพื้นที่แบบกำหนดได้และแบบไม่กำหนดได้
ลิงก์ภายนอก
- Philippe Oechslin: การสร้างความสมดุลระหว่างเวลาในการประมวลผลรหัสลับที่รวดเร็วยิ่งขึ้น
- กาลครั้งหนึ่งนานมาแล้ว - การแลกเปลี่ยนระหว่างความทรงจำ