เมื่อใดและเพราะเหตุใดจึงควรใช้แคชที่ใช้น้อยที่สุด (LFU) พร้อมการใช้งานใน Golang

ในช่วงหลายปีที่ผ่านมา ผู้ที่เกี่ยวข้องกับวิทยาการคอมพิวเตอร์และวิศวกรรมศาสตร์ได้ทำงานอย่างหนักเพื่อเพิ่มประสิทธิภาพในลักษณะต่างๆ เนื่องจากเราอาศัยอยู่ในโลกที่มีทรัพยากรจำกัด มนุษยชาติจึงพยายามหาทางลดต้นทุนให้เหมาะสมและเร่งความเร็วให้กับทุกสิ่งอยู่เสมอ

ในด้านวิศวกรรมซอฟต์แวร์ ฉันขอยืนยันว่าแนวทางที่ได้รับความนิยมมากที่สุดในการปรับปรุงประสิทธิภาพคือการแคช แม้ว่าการแคชจะมีแอปพลิเคชันต่างๆ มากมาย ขึ้นอยู่กับสาขาวิศวกรรมซอฟต์แวร์ แนวคิดเบื้องหลังการแคชนั้นค่อนข้างง่าย: จัดเก็บข้อมูลที่มักจำเป็น/ใช้ในโครงสร้าง/พื้นที่จัดเก็บที่รวดเร็ว เพื่อให้สามารถเรียกค้นได้เร็วมาก

ที่จริงแล้ว แคชจะต้องรวดเร็วในสองมิติ:

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

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

พื้นฐาน

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

หากคุณเคยใช้แคช LFU คุณอาจเคยลองใช้โครงสร้างข้อมูล min-heap เนื่องจากโครงสร้างดังกล่าวจัดการการแทรก การลบ และการอัปเดตในความซับซ้อนของเวลาลอการิทึม ในบทความนี้ เราจะดูแนวทางอื่นในการนำไปปฏิบัติ

แต่ก่อนที่เราจะนำไปใช้จริง เรามาดูกันว่ากรณีใดที่ LFU ดีกว่าทางเลือกอื่น

ที่ที่ LFU ส่องแสง

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

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

แคชเนื้อหาดังกล่าวเป็นกรณีการใช้งานที่สมบูรณ์แบบสำหรับแคช LFU อัลกอริธึมการลบแคช LFU จะไม่ลบเนื้อหาที่มีการเข้าถึงบ่อยครั้ง ในความเป็นจริง ในแคชดังกล่าว โลโก้ของ Google จะถูกแคชตลอดไป ในทางตรงกันข้าม หากมีรูปภาพใดที่จะเข้าถึงได้เนื่องจากหน้า Landing Page ใหม่ของผลิตภัณฑ์ใหม่ที่อยู่หน้าแรกของ Reddit, Slashdot & Hackernews เมื่อพายุกระแสเกินผ่านไป เนื้อหาจะถูกไล่ออกเร็วขึ้นเนื่องจากการเข้าถึง ความถี่จะลดลงอย่างมาก แม้ว่าในช่วงไม่กี่วันที่ผ่านมาจะมีการเข้าถึงหลายครั้งก็ตาม

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

การใช้แคช LFU

ตอนนี้เรามาดูเนื้อของมันกันดีกว่า ดังที่เราได้กล่าวไว้ก่อนหน้านี้ แทนที่จะมองว่า min-heap เป็นโครงสร้างข้อมูลที่เป็นไปได้ที่จะสำรองแคช LFU ของเรา เราจะพิจารณาแนวทางที่ดีกว่า

ในความเป็นจริง ในปี 2010 กลุ่มนักวิจัย Prof. Ketan Shah, Anirban Mitra และ Dhruv Matani ตีพิมพ์บทความชื่อ “อัลกอริทึม O(1) สำหรับการนำโครงการกำจัดแคช LFU ไปใช้” (คุณสามารถตรวจสอบได้ ที่นี่) ซึ่ง พวกเขาอธิบายการใช้งานแคช LFU ที่มีความซับซ้อนรันไทม์ O(1) สำหรับการดำเนินการทั้งหมด ซึ่งรวมถึงการแทรก การเข้าถึง และการลบ (การขับไล่)

ที่นี่ ฉันจะแสดงให้คุณเห็นว่าเราสามารถนำแคชนี้ไปใช้ได้อย่างไร และแนะนำคุณตลอดขั้นตอนการใช้งาน

โครงสร้างข้อมูล

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

เพื่อให้เข้าใจพื้นฐานของการนำ LFU ไปใช้นี้ ลองดูที่รายการที่เชื่อมโยงและตารางแฮชเป็นกราฟิก ก่อนที่เราจะดูกราฟิกจริง เราต้องเข้าใจว่าตารางแฮชและรายการลิงก์จะถูกนำไปใช้อย่างไร

ตารางแฮชจะจัดเก็บรายการทั้งหมดด้วยคีย์ที่ได้รับการประมวลผลผ่านอัลกอริธึมการแฮช (สำหรับจุดประสงค์ของเราเราสามารถทำให้มันง่ายได้) และค่าจะเป็นรายการจริง:

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

หากเราดูตัวอย่างกราฟิกของเราด้านบน เราจะสังเกตเห็นว่ามีการเข้าถึงรายการ A, B, C และ D 1 ครั้ง มีการเข้าถึงรายการ E และ F 4 ครั้งและต่อๆ ไป เส้นสีน้ำเงินคือตัวชี้ที่แต่ละรายการในรายการมีถึงบรรพบุรุษในรายการความถี่

แล้วจะเกิดอะไรขึ้นหากรายการ E เข้าถึงได้อีกครั้ง? มาดูขั้นตอนกัน: 1. การดึงไอเท็มจากตารางแฮชเป็นเรื่องง่าย (และปรับขนาดได้ดี O(1)) 2. เราจะเข้าถึงตัวชี้ frequencyParent ของไอเท็ม ซึ่งเราจะสามารถตรวจสอบความถี่ถัดไปในรายการได้ 3. ถ้า มีความถี่ใหม่อยู่ (เช่น 8) เราจะพุชให้เป็นรายการแรกของรายการภายใต้โหนดความถี่ 8 4. หากไม่มีความถี่ใหม่ เราจะสร้างโหนดความถี่ 8 และจะเพิ่ม E ลงในรายการ

แค่นั้นแหละ. การดึงข้อมูลรายการและการรีเฟรชความถี่ของรายการคือ O(1) ก่อนที่เราจะใช้งานอัลกอริธึมการเข้าถึง เรามาสร้างประเภทพื้นฐานที่เราต้องใช้เพื่อให้งานนี้ใช้งานได้ก่อน

ประเภท

ดังที่เราได้กล่าวไว้ก่อนหน้านี้ เราจำเป็นต้องจำลองประเภทที่จำเป็นซึ่งจะเป็นแกนหลักของแคชของเรา

struct ตัวแรกจะเป็น CacheItem นี่จะเป็นรายการจริงที่จะถูกเก็บไว้ในแคช:

type CacheItem struct {
	key      	string        // Key of entry
	value    	interface{}   // Value of item
	frequencyParent *list.Element // Pointer to parent in cacheList
}

ประกอบด้วย key ซึ่งเราสามารถค้นหาได้ในตารางแฮช value ซึ่งเป็นรายการแคชจริง และตัวชี้ frequencyParent ไปยังตัวชี้ในรายการความถี่

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

type FrequencyItem struct {
	entries map[*CacheItem]byte // Set of entries
	freq    int                  // Access frequency
}

struct สุดท้ายที่เราจะต้องมีเพื่อให้แคชทำงานได้อย่างราบรื่นก็คือ Cache นั่นเอง:

type Cache struct {
	bykey       map[string]*CacheItem // Hashmap containing *CacheItems for O(1) access
	freqs       *list.List            // Linked list of frequencies
	capacity    int                   // Max number of items
	size        int                   // Current size of cache
}

Cache จะมีแฮชแมปที่เรียกว่า bykey (การตั้งชื่อมาจากกระดาษที่ลิงก์ด้านบน) รายการความถี่ที่เรียกว่า freqs ความจุสูงสุดของแคชที่เรียกว่า capacity และ size ของแคชซึ่งแสดงถึงจำนวนรายการที่แคชไว้ที่ใดก็ตาม ช่วงเวลา.

ใหม่ ตั้งค่าและรับ

มาดูฟังก์ชันสามประการแรกที่จำเป็นในการทำให้แคชของเราทำงานได้ อันแรกคือฟังก์ชันคอนสตรัคเตอร์เล็กน้อย:

func New() *Cache {
	cache := new(Cache)
	cache.bykey = make(map[string]*CacheItem)
	cache.freqs = list.New()
	cache.size = 0
	cache.capacity = 100

	return &c
}

ตัวสร้าง New จะสร้างโครงสร้าง Cache ใหม่และจะตั้งค่าเริ่มต้นทั้งหมดให้กับมัน ในกรณีที่คุณสงสัยว่า list.New() ทำงานอย่างไร: สำหรับรายการความถี่ เราจะใช้แพ็คเกจ container/list ของ Go ซึ่งมีการใช้งานรายการลิงก์ที่เรียบร้อย คุณสามารถตรวจสอบ "เอกสารประกอบ" เพื่อดูรายละเอียดเพิ่มเติมได้

ฟังก์ชันที่สองซึ่งจะนำไปใช้กับ Cache คือฟังก์ชัน Set:

func (cache *Cache) Set(key string, value interface{}) {
	if item, ok := cache.bykey[key]; ok {
		item.value = value
		// Increment item access frequency here
	} else {
		item := new(CacheItem)
		item.key = key
		item.value = value
		cache.bykey[key] = item
		cache.size++
		// Eviction, if needed
		// Increment item access frequency
	}
}

ฟังก์ชันจะใช้คีย์แคชและค่า/รายการจริงที่จะแคชเป็นอาร์กิวเมนต์ จากนั้นจะตรวจสอบว่ารายการนั้นถูกแคชไว้แล้วหรือไม่ หากถูกแคชไว้ ระบบจะอัปเดตค่าในรายการ มิฉะนั้น มันจะสร้าง CacheItem ใหม่ซึ่งจะห่อหุ้มค่าจริง มันจะตั้งค่า key มันจะเพิ่มรายการในแฮช bykey และจะเพิ่ม size ของแคช

ตอนนี้ ในตรรกะทั้งสองสาขา ฉันได้เพิ่มความคิดเห็นสำหรับส่วนที่ขาดหายไป: 1. Cache จะต้องรู้วิธีเพิ่มความถี่ในการเข้าถึงสำหรับ aCacheItem แต่เรายังไม่ได้ดำเนินการดังกล่าว 2. Cache จะต้องรู้วิธียกเลิกรายการตามความถี่ในการเข้าถึง หาก size ถึง capacity

เราจะเก็บความคิดเห็นเหล่านี้ไว้จนกว่าเราจะใช้ฟังก์ชัน increment และ evict

ฟังก์ชันที่สามที่ Cache จะได้รับคือ Get - เข้าถึงรายการด้วยคีย์จาก hashtable และส่งคืน:

func (cache *Cache) Get(key string) interface{} {
	if e, ok := cache.bykey[key]; ok {
		// Increment acess frequency here
		return e.value
	}

	return nil
}

ไม่มีเวทย์มนตร์ที่นี่เช่นกัน เราจะตรวจสอบว่า bykey hashtable มีค่าที่มีอาร์กิวเมนต์ key หรือไม่ และเราจะส่งคืนค่านั้นหากมี มิฉะนั้นเราจะส่งคืน nil ที่นี่ เช่นเดียวกับใน Set เราจะทิ้งความคิดเห็นตัวยึดตำแหน่งไว้ โดยที่เราต้องเพิ่มการเรียกใช้ฟังก์ชันการเพิ่มความถี่เมื่อเรานำไปใช้

กำลังอัปเดตความถี่ในการเข้าถึง

ดังที่เราเห็นแล้วว่า ทุกครั้งที่ดำเนินการเข้าถึงไปยังแคช เราจะต้องอัปเดตความถี่ในการเข้าถึงของรายการที่เข้าถึง

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

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

ประการที่สาม เมื่อเราตรวจพบ FrequencyParent แล้ว ฟังก์ชันของเราจะต้องตั้งค่าพาเรนต์ใหม่เป็น item ที่กำลังเพิ่มขึ้น และเพิ่มลงในรายการพาเรนต์ที่ entries

ในขั้นตอนสุดท้าย ฟังก์ชัน increment จะลบรายการออกจาก entries ของโหนดความถี่เก่า (frequencyParent)

นี่คือรหัสใน Golang:

func (cache *Cache) increment(item *CacheItem) {
	currentFrequency := item.frequencyParent
	var nextFrequencyAmount int
	var nextFrequency *list.Element

	if currentFrequency == nil {
		nextFrequencyAmount = 1
		nextFrequency = cache.freqs.Front()
	} else {
		nextFrequencyAmount = currentFrequency.Value.(*FrequencyItem).freq + 1
		nextFrequency = currentFrequency.Next()
	}

	if nextFrequency == nil || nextFrequency.Value.(*FrequencyItem).freq != nextFrequencyAmount {
		newFrequencyItem := new(FrequencyItem)
		newFrequencyItem.freq = nextFrequencyAmount
		newFrequencyItem.entries = make(map[*CacheItem]byte)
		if currentFrequency == nil {
			nextFrequency = cache.freqs.PushFront(newFrequencyItem)
		} else {
			nextFrequency = cache.freqs.InsertAfter(newFrequencyItem, currentFrequency)
		}
	}

	item.frequencyParent = nextFrequency
	nextFrequency.Value.(*FrequencyItem).entries[item] = 1
	if currentFrequency != nil {
		cache.remove(currentFrequency, item)
	}
}

ย้อนกลับไปที่แผนภาพดั้งเดิมของเราของรายการความถี่และรายการ และดำเนินการผ่านการเพิ่มรายการ E

ขั้นตอนแรกที่ฟังก์ชัน increment ของเราจะดำเนินการคือการจัดสรรตัวชี้ไปยังโหนด 4 (frequencyParent) และ value (ซึ่งก็คือ 4) เนื่องจากโหนด 4 มีอยู่ในรายการ มันจะค้นหาโหนดถัดไปในรายการความถี่ ซึ่งในกรณีของเราคือโหนด 7

เมื่อทราบแล้วว่าความถี่ใหม่สำหรับโหนด E ควรเป็น 5 ไม่ใช่ 7 ความถี่ดังกล่าวจะเพิ่มโหนดความถี่ใหม่ในรายการ ระหว่างโหนด 4 และ 7:

เมื่อเพิ่มโหนด 5 ลงในรายการแล้ว ฟังก์ชันจะตั้งค่าเริ่มต้นที่จำเป็นสำหรับโหนดเพื่อให้ทำงานได้อย่างถูกต้อง จากนั้นจะตั้งค่าตัวชี้ของ E เป็น frequencyParent ใหม่ (โหนด 5):

ในขั้นตอนสุดท้าย จะใช้ item ซึ่งมีประเภท *CacheItem และจะเพิ่มลงในรายการ entries ในขณะที่ลบออกจากรายการ entries จาก frequencyParent ก่อนหน้า:

มาดูขั้นตอนในการลบ CacheItem ออกจากรายการ entries ของ FrequencyItem

กำลังลบรายการ

เมื่อเราทราบโหนดในรายการที่เราต้องการลบออก เราก็สามารถลบรายการออกจากรายการ entries และลบ FrequencyItem ออกจากรายการความถี่โดยสมบูรณ์หาก entries ว่างเปล่า:

func (cache *Cache) Remove(listItem *list.Element, item *CacheItem) {
	frequencyItem := listItem.Value.(*FrequencyItem)
	delete(frequencyItem.entries, item)
	if len(frequencyItem.entries) == 0 {
		cache.freqs.Remove(listItem)
	}
}

การขับไล่

ชิ้นส่วนสุดท้ายของปริศนาคือการขับไล่ หรืออีกนัยหนึ่งคือ การลบรายการที่ใช้บ่อยน้อยที่สุดออกเมื่อแคชถึงความจุสูงสุด

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

ฟังก์ชั่นจะเริ่ม “เดินผ่าน” รายการความถี่ตั้งแต่ต้นจนจบ เนื่องจากรายการความถี่เรียงลำดับจากน้อยไปหามาก จึงจะเริ่มลบ entries ออกจากโหนดความถี่แรกเป็นต้นไป จนกว่าจะลบรายการได้มากเท่ากับจำนวนที่ส่งผ่านเข้ามา

หากโหนดความถี่ไม่มี entries เนื่องจากการไล่ออก ฟังก์ชัน Evict จะต้องลบโหนดความถี่ออกจากรายการความถี่ด้วย มันจะทำเช่นนั้นโดยการเรียกใช้ฟังก์ชัน Remove ด้วยวิธีนี้การขับไล่จะไม่ทิ้งขยะไว้ข้างหลัง

นี่คือรหัสของสิ่งที่เราอธิบายไว้ข้างต้น:

func (cache *Cache) Evict(count int) {
	for i := 0; i < count; {
		if item := cache.freqs.Front(); item != nil {
			for entry, _ := range item.Value.(*FrequencyItem).entries {
				if i < count {
					delete(cache.bykey, entry.key)
					cache.Remove(item, entry)
					cache.size--
					i++
				}
			}
		}
	}
}

กลับไปที่การตั้งค่าและรับ

ในตอนต้นของบทความนี้ เราได้ใช้ฟังก์ชัน Set และ Get สิ่งหนึ่งที่เรายังไม่มีในตอนนั้นคือฟังก์ชัน Evict และ increment ดังนั้นเราจึงสามารถใช้ฟังก์ชันเหล่านี้ได้ตามนั้น มาเพิ่มการร้องขอของพวกเขากัน

ความถี่ในการเข้าถึงที่เพิ่มขึ้น

ในฟังก์ชัน Get หากเราพบรายการในตารางแฮช bykey เราจำเป็นต้องเพิ่มความถี่ในการเข้าถึงรายการนั้นก่อนที่เราจะดำเนินการส่งคืน value:

func (cache *Cache) Get(key string) interface{} {
	if e, ok := cache.bykey[key]; ok {
		cache.increment(e)
		return e.value
	}

	return nil
}

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

func (cache *Cache) Set(key string, value interface{}) {
	if item, ok := cache.bykey[key]; ok {
		item.value = value
                cache.increment(item)
	} else {
		item := new(CacheItem)
		item.key = key
		item.value = value
		cache.bykey[key] = item
		cache.size++
		// Eviction, if needed
                cache.increment(item)
	}
}

การขับไล่ภายหลังการบวก

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

ก่อนอื่นมาเพิ่มฟังก์ชันที่จะส่งคืน bool หากแคชถึงความจุสูงสุดแล้ว:

func (cache *Cache) atCapacity() bool {
	return cache.size >= cache.capacity
}

ฟังก์ชันนี้เรียบง่าย: ตรวจสอบว่า size ปัจจุบันของ Cache นั้นใหญ่กว่าหรือเท่ากับ capacity หรือไม่

ตอนนี้ เรามาลองใช้ฟังก์ชัน Set กันดีกว่า เมื่อเราตั้งค่ารายการใหม่ในแคชแล้ว เราจะต้องตรวจสอบว่าแคชถึงความจุแล้วหรือไม่ จากนั้นจึงกำจัดรายการจำนวนหนึ่งออกจากแคช

เพื่อความง่าย เราจะลบออกเพียง 10 รายการทุกครั้งที่ใช้ความจุสูงสุด:

func (cache *Cache) Set(key string, value interface{}) {
	if item, ok := cache.bykey[key]; ok {
		item.value = value
		cache.increment(item)
	} else {
		item := new(CacheItem)
		item.key = key
		item.value = value
		cache.bykey[key] = item
		cache.size++
		if cache.atCapacity() {
			cache.Evict(10)
		}
		cache.increment(item)
	}
}

ด้วยการเปลี่ยนแปลงนี้ หาก ณ จุดใดก็ตามการเพิ่มรายการถึงความจุของแคช แคชจะลบรายการที่ใช้บ่อยน้อยที่สุด

หากคุณต้องการดูโค้ดทั้งหมดของบทความนี้ คุณสามารถดู ส่วนสำคัญนี้

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

หากเรากลับมาดู บทความ ที่เรากล่าวถึงในตอนต้นของบทความ เราจะเห็นว่าแม้ว่า LFU จะไม่ใช่ข่าว แต่เดิมมีการใช้ min-heap ซึ่งมีเวลาลอการิทึมสำหรับการแทรก การค้นหา และการลบ สิ่งที่น่าสนใจในบทความนี้ ผู้เขียนอธิบายว่าแนวทางที่พวกเขาเสนอมีความซับซ้อนของเวลา O(1) สำหรับการดำเนินการแต่ละรายการ (การแทรก การค้นหา และการลบ) เนื่องจากการดำเนินการจะขึ้นอยู่กับตารางแฮช นอกจากนี้ รายการที่เชื่อมโยงไม่ได้เพิ่มความซับซ้อนของเวลาใดๆ เนื่องจากเราไม่ได้สำรวจรายการ ณ จุดใดๆ - เราเพียงแค่เพิ่มหรือลบโหนดในรายการเหล่านั้นหากจำเป็น (ซึ่งเป็นการดำเนินการ O (1))

ในการปิด

ในบทความนี้ เราได้อธิบายพื้นฐานของแคช LFU แล้ว เราได้กำหนดเกณฑ์ชี้วัดประสิทธิภาพที่สำคัญที่สุด (อัตราส่วนการเข้าชมต่อพลาด สมาชิกภาพ และความเร็วในการไล่ออก) เราพบว่าแม้ว่าจะไม่ใช่รูปแบบการแคชที่ใช้กันอย่างแพร่หลาย แต่ก็มีประสิทธิภาพมากในบางกรณี

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

เผยแพร่ครั้งแรกที่ ieftimov.com เมื่อวันที่ 27 กุมภาพันธ์ 2019