LIFO Cache: สาระสำคัญ, อัลกอริทึมสแต็ก และวิธีการทำงาน

LIFO Cache คืออะไร?

LIFO Cache (Last In First Out Cache) คือแคชขนาดคงที่ที่ทำงานบนสแต็ก เมื่อเพิ่มองค์ประกอบใหม่ในแคชที่เต็ม องค์ประกอบล่าสุด (ยอด) จะถูกลบออกและองค์ประกอบใหม่จะเข้ามาแทนที่ ชื่อ “Last In First Out” หมายถึงองค์ประกอบที่เข้าแคชทีหลังจะถูกขับออกก่อน

นโยบายนี้แตกต่างอย่างสิ้นเชิงจาก LRU และ FIFO ในขณะที่ LRU พยายามเก็บข้อมูลที่เกี่ยวข้องมากที่สุด (ตามเวลาการเข้าถึงล่าสุด) และ FIFO รักษา “อายุ” ของข้อมูล LIFO จงใจเสียสละข้อมูลใหม่ สิ่งนี้อาจดูขัดกับสัญชาตญาณสำหรับแคช แต่สำหรับ สถานการณ์ บางอย่าง LIFO กลับเป็นทางออกที่ดีที่สุด

การใช้งาน LIFO Cache แบบดั้งเดิมใช้สแต็กที่ใช้อาร์เรย์หรือลิสต์เชื่อมโยง อาร์เรย์ให้พื้นที่จัดเก็บที่กะทัดรัดและตำแหน่งของแคช แต่ต้องจัดสรรหน่วยความจำล่วงหน้าสำหรับ maxSize ลิสต์เชื่อมโยงมีความยืดหยุ่นมากกว่า แต่แต่ละองค์ประกอบต้องใช้หน่วยความจำเพิ่มเติมสำหรับพอยน์เตอร์ (8–16 ไบต์ต่อองค์ประกอบ)

การดำเนินการพื้นฐานของ LIFO Cache

การดำเนินการ push(value) เพิ่มองค์ประกอบที่ยอดสแต็ก หากขนาดถึง maxSize ยอดจะถูกลบออกก่อนการแทรก การดำเนินการ pop() จะลบและส่งคืนองค์ประกอบบนสุด — มีประโยชน์สำหรับสถานการณ์ “เลิกทำการกระทำล่าสุด” การดำเนินการ peek() จะส่งคืนองค์ประกอบบนสุดโดยไม่ลบ — สำหรับดูสถานะที่บันทึกไว้ล่าสุดโดยไม่เปลี่ยนแปลงสแต็ก

LIFO Cache ทำงานอย่างไร

หลักการทำงานของ LIFO Cache นั้นง่ายมาก: การดำเนินการทั้งหมดทำที่ปลายด้านหนึ่งของโครงสร้าง — ยอดสแต็ก เมื่อเพิ่มองค์ประกอบใหม่ มันจะถูกวางไว้บนยอด หากสแต็กเต็ม องค์ประกอบบนสุดจะถูกนำออก (ลบ) และองค์ประกอบใหม่จะเข้ามาแทนที่ การขับออก จะส่งผลต่อองค์ประกอบเดียวเท่านั้น — ยอด — ดังนั้นอัลกอริทึมจึงไม่ต้องวนซ้ำหรือค้นหา

คุณสมบัตินี้ทำให้ LIFO Cache เร็วที่สุดในบรรดานโยบายการขับออกทั้งหมด: การดำเนินการทั้งหมดทำงานใน O(1) โดยไม่ต้องใช้โครงสร้างข้อมูลเพิ่มเติม ไม่ต้องใช้ตารางแฮชสำหรับการค้นหา ไม่ต้องใช้ลิสต์เชื่อมโยงสองทิศทางสำหรับการจัดเรียงใหม่ — แค่พอยน์เตอร์ธรรมดาไปยังยอดสแต็ก การใช้หน่วยความจำ น้อยที่สุด: เพียงแค่จัดเก็บองค์ประกอบเท่านั้น

อย่างไรก็ตาม ความเรียบง่ายมีข้อเสีย: LIFO Cache ไม่พิจารณาความถี่หรือเวลาการเข้าถึงล่าสุดของข้อมูล หากแอปพลิเคชันร้องขอข้อมูล A, B, C ก่อนแล้วจึงร้องขอ A อีกครั้ง C (ที่เพิ่มล่าสุด) จะถูกขับออกเมื่อแคชเต็ม แม้ว่า A จะไม่เกี่ยวข้องอีกแล้ว สำหรับ สถานการณ์แคชทั่วไป สิ่งนี้ทำให้ LIFO เป็นตัวเลือกที่แย่ที่สุด เนื่องจากข้อมูลใหม่มักมีค่าที่สุด

ขนาดสแต็กและการจัดการหน่วยความจำ

สำหรับ LIFO Cache ที่ใช้อาร์เรย์ ขนาดจะถูกกำหนดเมื่อสร้างและไม่เปลี่ยนแปลงแบบไดนามิก หากสแต็กเต็มและมีการ push เกิดขึ้น องค์ประกอบบนสุดจะถูกเขียนทับ สำหรับการใช้งานแบบลิสต์เชื่อมโยง หน่วยความจำจะถูกจัดสรรต่อองค์ประกอบตามต้องการ แต่เมื่อถึงขีดจำกัด โหนดเก่าจะถูกตัดออกและสามารถถูกเก็บโดยตัวเก็บขยะ ใน แอปพลิเคชันมือถือ แนะนำให้ใช้อาร์เรย์สำหรับ LIFO Cache เพราะมันไม่สร้างภาระเพิ่มเติมให้กับ GC

LIFO เทียบกับ LRU และ FIFO: เปรียบเทียบกลยุทธ์

การเลือกกลยุทธ์การขับออกส่งผลโดยตรงต่อประสิทธิภาพของแคช LIFO, LRU และ FIFO แสดงถึงวิธีการที่แตกต่างกันสำหรับคำถามเดียวกัน: ควรลบองค์ประกอบใดเมื่อแคชเต็ม แต่ละวิธีเหมาะสมที่สุดสำหรับงานประเภทของตัวเอง

LRU โดยทั่วไปให้อัตราการชนที่ดีที่สุด แต่ต้องใช้หน่วยความจำมากกว่าและซับซ้อนกว่าในการใช้งาน FIFO เป็นการประนีประนอมระหว่างประสิทธิภาพและอัตราการชน มีประโยชน์สำหรับข้อมูลสตรีมมิ่ง LIFO ง่ายที่สุดแต่อัตราการชนต่ำ: ควรใช้เมื่อความหมาย “เข้าทีหลังออกก่อน” สอดคล้องกับตรรกะทางธุรกิจ (การนำทาง การเลิกทำ)

LIFO Cache ใช้ที่ไหน

แม้จะมีความเหมาะสมจำกัดสำหรับแคชทั่วไป LIFO Cache ถูกใช้ในสถานการณ์เฉพาะที่ลำดับการประมวลผลข้อมูลกลับกับลำดับการมาถึง ลองพิจารณากรณีหลัก

สแตกการนำทาง

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

สแตกเลิกทำ/ทำซ้ำ

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

บัฟเฟอร์การคำนวณชั่วคราว

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

ตัวอย่างโค้ด LIFO Cache

มาดูการใช้งาน LIFO Cache ใน Kotlin โดยใช้อาร์เรย์ขนาดคงที่ อาร์เรย์ให้ประสิทธิภาพดีที่สุดและการใช้หน่วยความจำน้อยที่สุดสำหรับอุปกรณ์มือถือ

class LifoCache<V>(
    private val maxSize: Int
) {
    private val array = arrayOfNulls<V>(maxSize)
    private var top = -1

    fun push(value: V) {
        if (top == maxSize - 1) {
            top--  // discard oldest when full
        }
        array[++top] = value
    }

    fun pop(): V? {
        if (top == -1) return null
        val result = array[top]
        array[top--] = null
        return result
    }

    fun peek(): V? {
        return array[top]
    }
}

ดัชนี top ชี้ไปที่ยอดสแต็ก push เพิ่ม top และเขียนค่า หากอาร์เรย์เต็ม (top == maxSize - 1) top จะลดลงก่อนเขียน — ยอดสแต็กถูกเขียนทับ ซึ่งเป็นการขับออกแบบ LIFO เมธอด pop ส่งคืนองค์ประกอบและลด top ในขณะที่ peek อ่านองค์ประกอบบนสุดโดยไม่เปลี่ยนสแต็ก

ตัวอย่าง: สแตกการนำทางกับ LIFO Cache

พิจารณาการใช้ LIFO Cache เพื่อจำกัดความลึกของการนำทางใน Jetpack Compose เมื่อเปิดหน้าจอใหม่ มันจะถูกเพิ่มในสแต็ก และเมื่อเกินขีดจำกัด หน้าจอล่าสุดจะถูกขับออก

class NavigationStack(maxDepth: Int = 10) {
    private val cache = LifoCache<Screen>(maxDepth)

    fun navigateTo(screen: Screen) {
        cache.push(screen)
    }

    fun goBack(): Screen? {
        return cache.pop()
    }

    fun currentScreen(): Screen? {
        return cache.peek()
    }
}

ในตัวอย่างนี้ NavigationStack ใช้ LIFO Cache เพื่อเก็บประวัติหน้าจอ เมื่อเรียก navigateTo หน้าจอจะถูกเพิ่มในสแต็ก เมื่อเรียก goBack หน้าจอล่าสุดจะถูกลบ หากผู้ใช้เปิด 11 หน้าจอด้วยขีดจำกัด 10 หน้าจอล่าสุด (ที่ 11) จะขับหน้าจอก่อนหน้า (ที่ 10) ออก — หน้าจอแรกยังคงอยู่ในสแต็ก ซึ่งตรงกับความคาดหวังของผู้ใช้เมื่อนำทางกลับ กลยุทธ์นี้มีประสิทธิภาพกว่า LRU สำหรับการนำทาง: การลบหน้าจอที่เปิดไว้นาน (“หน้าแรก” “โปรไฟล์”) จะทำให้เกิดพฤติกรรมที่ไม่คาดคิด