อ่านบทความนี้ใน Facebook
“ณ ห้องสมุดแห่งหนึ่งมีคนมายืมหนังสือจำนวนมาก คุณจะออกแบบห้องสมุดอย่างไรเพื่อช่วยให้คนที่มายืมหนังสือสะดวกที่สุด?”
หนึ่งในวิธีการปัญหาทางก็คือการตั้งโต็ะวางหนังสือไว้ตรงทางเข้าร้านครับ
ยกตัวอย่างเช่นหนังสือที่คนยืมบ่อยที่สุด เพื่อที่ว่าเวลาคนมายืมหนังสือยอดฮิตก็จะสามารถหยิบหนังสือจากโต็ะไปยืมได้เลย โดยไม่ต้องไปเดินหาหนังสือในห้องสมุดให้เสียเวลา
สิ่งนี้เราเรียกว่าการทำ cache ครับ มันคือการเก็บข้อมูลหรืออะไรบางอย่างไว้ เพื่อที่ว่าเวลาเราเรียกหาสิ่ง ๆ นั้นเราจะได้เข้าถึงสิ่งนั้นได้ทันทีโดยไม่ต้องไปหาหรือคำนวนสิ่งนั้นใหม่แต่ต้น
แต่ทั้งนี้โต็ะของเราก็ไม่สามารถที่จะวางหนังสือจากทั้งร้านได้ (เรียกได้ว่าพื้นที่มีจำกัดนั้นหละ) ดังนั้นเลยมีเรื่องที่ต้องคิดเพิ่มก็คือว่า “แล้วหนังสือเล่มไหนควรจะอยู่บนโต็ะนี้บ้าง?”
…โดยมีเป้าหมายสูงสุดคือการ maximize hit rate หรือเมื่อมีคนเข้ามาหาหนังสือในร้าน เราจะทำยังไงให้มีโอกาสที่คนส่วนใหญ่สามารถเลือกยืมจากโต็ะได้ทันที แทนที่จะไปเสียเวลาหาหนังสือนั่นเอง
ดังนั้นเราจึงต้องมีกฏหรือนโยบายครับว่า “เราจะเก็บหนังสือเล่มไหนไว้บนโต็ะและเล่มไหนควรจะเอาออก” เมื่อมีหนังสือเล่มใหม่เพิ่มเข้ามาในร้าน และเราเรียกสิ่งนี้ว่า “cache eviction policy” นั่นเอง
ในโพสนี้เราขอมายกตัวอย่าง 2 polices ง่าย ๆ ครับคือ LFU กับ LRU
LFU ย่อมาจาก least frequently used หรือคือเมื่อมีหนังสือเล่มใหม่เข้ามา เราจะเลือกเล่มที่ “มีจำนวนคนยืมน้อยที่สุด” ออกจากโต็ะ …ส่วนหนังสือเล่มอื่น ๆ ที่มีคนมายืมมาก ๆ (หรือหนังสือยอดฮิต) ก็จะยังวางอยู่บนโต็ะต่อไปนั่นเอง
LRU ย่อมาจาก least recently used หรือคือเมื่อมีหนังสือใหม่เข้ามา เราจะเลือกหนังสือที่ “คนไม่ยืมนานสุด” ออก ส่วนหนังสือเล่มอื่นที่เหลือก็จะเป็นหนังสือที่คนมายืมล่าสุดกันนั่นเอง
และสุดท้ายนี้การจะเลือกใช้ policy ไหนนั้นขึ้นอยู่กับบริบทเลย
ยกตัวอย่างเช่นถ้าร้านหนังสือเราให้ยืมหนังสือเรียน เราก็อาจจะเลือกใช้ LFU เพราะคนที่มายืมหนังสือส่วนใหญ่ก็คงจะมายืมหนังสือยอดฮิตที่ต้องเอาไปอ่านช่วงสอบกัน
ในขณะที่ถ้าหากว่าร้านเราให้ยืมหนังสือเกี่ยวกับข่าวหรือ trend ที่เมื่อเวลาผ่านไปเนื้อหาก็คงจะ outdate เราก็อาจจะเลือกใช้ LRU นั่นเอง
