pdqsort是基于std::sort的改进算法，当数据量小的时候用插入排序，递归深度大的时候用heapsort，其他情况用改良的quicksort
```go
// pdqsort 对数据 data[a:b] 进行排序。
// 该算法基于 pattern-defeating quicksort (pdqsort)，但没有 BlockQuicksort 中的优化。
// pdqsort 论文：https://arxiv.org/pdf/2106.05123.pdf
// C++ 实现：https://github.com/orlp/pdqsort
// Rust 实现：https://docs.rs/pdqsort/latest/pdqsort/
// limit 是在陷入堆排序之前允许的坏（非常不平衡）枢轴的数量。
func pdqsort(data Interface, a, b, limit int) {
	const maxInsertion = 12



	var (
		wasBalanced    = true // 上次分区是否相当平衡
		wasPartitioned = true // 切片是否已分区
	)

	for {
		length := b - a

		if length <= maxInsertion {
			insertionSort(data, a, b)
			return
		}

		// 如果坏选择太多，就退回到堆排序。
		if limit == 0 {
			heapSort(data, a, b)
			return
		}

		// 如果上次分区不平衡，我们需要打破模式。
		if !wasBalanced {
			breakPatterns(data, a, b)
			limit--
		}

		// 选择枢轴和提示。
		pivot, hint := choosePivot(data, a, b)
		if hint == decreasingHint {
			// 反转范围，以便处理递增顺序的情况。
			reverseRange(data, a, b)
			// 选择的枢轴在数组开始后的 pivot-a 个元素。
			// 反转后，它在数组末尾前的 pivot-a 个元素。
			// 这个想法来自于 Rust 的实现。
			pivot = (b - 1) - (pivot - a)
			hint = increasingHint
		}

		// 如果切片可能已经排序，则尝试进行局部插入排序。
		if wasBalanced && wasPartitioned && hint == increasingHint {
			if partialInsertionSort(data, a, b) {
				return
			}
		}

		// 可能切片包含许多重复元素，将切片分为等于和大于枢轴的元素。
		if a > 0 && !data.Less(a-1, pivot) {
			// 如果前一个元素大于等于枢轴，则进行相等分区。
			mid := partitionEqual(data, a, b, pivot)
			a = mid
			continue
		}

		// 进行普通分区。
		mid, alreadyPartitioned := partition(data, a, b, pivot)
		wasPartitioned = alreadyPartitioned

		leftLen, rightLen := mid-a, b-mid
		balanceThreshold := length / 8
		if leftLen < rightLen {
			wasBalanced = leftLen >= balanceThreshold
			pdqsort(data, a, mid, limit)
			a = mid + 1
		} else {
			wasBalanced = rightLen >= balanceThreshold
			pdqsort(data, mid+1, b, limit)
			b = mid
		}
	}
}
```

heapsort
```go
// siftDown implements the heap property on data[lo:hi].
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && data.Less(first+child, first+child+1) {
			child++
		}
		if !data.Less(first+root, first+child) {
			return
		}
		data.Swap(first+root, first+child)
		root = child
	}
}

func heapSort(data Interface, a, b int) {
	first := a
	lo := 0
	hi := b - a

	// Build heap with greatest element at top.
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown(data, i, hi, first)
	}

	// Pop elements, largest first, into end of data.
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDown(data, lo, i, first)
	}
}

```

insertionsort
```go
// insertionSort sorts data[a:b] using insertion sort.
func insertionSort(data Interface, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}
```
---
参考：
https://mp.weixin.qq.com/s/8qMvwQE9p1UkEYpIR4Dg8A

pdqsort排序算法

```go
//	// INVALID: a directly-declared header will not hold Data as a reference.
//	var hdr reflect.StringHeader
//	hdr.Data = uintptr(unsafe.Pointer(p))
//	hdr.Len = n
//	s := *(*string)(unsafe.Pointer(&hdr)) // p possibly already lost
type Pointer *ArbitraryType


type ArvitraryType int

// Sizeof takes an expression x of any type and returns the size in bytes
// of a hypothetical variable v as if v was declared via var v = x.
// The size does not include any memory pos
```

指针的本质

ring实现了一个环形链表
```go
// Package ring 实现了环形链表的操作。
package ring



// Ring 是环形链表的元素。
// 环形链表没有明确定义的开头或结尾；指向环形链表的任何元素的指针都可视为对整个环形链表的引用。
// 空环形链表表示为 nil Ring 指针。Ring 的零值是一个只包含一个 nil Value 的环。
type Ring struct {
	next, prev *Ring
	Value      any // 由客户端使用；本库不会修改该值
}

// init 方法：初始化环形链表，返回链表的第一个元素。
func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

// Next 返回下一个环形链表元素。r 不能为空。
func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.next
}

// Prev 返回前一个环形链表元素。r 不能为空。
func (r *Ring) Prev() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.prev
}

// Move 将 n % r.Len() 个元素向前（n < 0）或向后（n >= 0）移动，并返回移动后的环形链表元素。r 不能为空。
func (r *Ring) Move(n int) *Ring {
	if r.next == nil {
		return r.init()
	}
	switch {
	case n < 0:
		for ; n < 0; n++ {
			r = r.prev
		}
	case n > 0:
		for ; n > 0; n-- {
			r = r.next
		}
	}
	return r
}

// New 创建包含 n 个元素的新环形链表。
func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	r := new(Ring)
	p := r
	for i := 1; i < n; i++ {
		p.next = &Ring{prev: p}
		p = p.next
	}
	p.next = r
	r.prev = p
	return r
}

// Link 连接环形链表 r 和 s，使得 r.Next() 变为 s，并返回 r.Next() 的原始值。
// r 不能为空。
//
// 如果 r 和 s 指向同一个环形链表，则连接它们将从链表中移除 r 和 s 之间的元素。
// 被移除的元素形成一个子环，结果是对该子环的引用（如果没有移除元素，则结果仍为 r.Next() 的原始值，而不是 nil）。
//
// 如果 r 和 s 指向不同的环形链表，则连接它们将创建一个单一的环形链表，其中包含 s 的元素插入到 r 之后。
// 结果指向插入后 s 的最后一个元素的下一个元素。
func (r *Ring) Link(s *Ring) *Ring {
	n := r.Next()
	if s != nil {
		p := s.Prev()
		// 注意：不能使用多重赋值，因为 LHS 的评估顺序未指定。
		r.next = s
		s.prev = r
		n.prev = p
		p.next = n
	}
	return n
}

// Unlink 从环形链表 r 中移除 n % r.Len() 个元素，从 r.Next() 开始。如果 n % r.Len() == 0，则 r 保持不变。
// 返回被移除的子环。r 不能为空。
func (r *Ring) Unlink(n int) *Ring {
	if n <= 0 {
		return nil
	}
	return r.Link(r.Move(n + 1))
}

// Len 计算环形链表 r 中的元素数量。
// 执行时间与元素数量成正比。
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		n = 1
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}

// Do 对环形链表中的每个元素调用函数 f，按照正向顺序。
// 如果 f 改变 *r，则 Do 的行为未定义。
func (r *Ring) Do(f func(any)) {
	if r != nil {
		f(r.Value)
		for p := r.Next(); p != r; p = p.next {
			f(p.Value)
		}
	}
}

```
使用示例
```go
package main

import (
	"container/ring"
	"fmt"
)

func main() {
	// 创建一个包含 3 个元素的环形链表
	r := ring.New(3)

	// 遍历环形链表并设置元素值
	for i := 1; i <= r.Len(); i++ {
		r.Value = i
		r = r.Next()
	}

	// 遍历环形链表并打印元素值
	r.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()

	// 移动环形链表的元素，使得下一个元素成为新的第一个元素
	r = r.Move(1)

	// Link 连接两个环形链表
	s := ring.New(2)
	s.Value = 4
	r.Link(s)

	// 遍历连接后的环形链表并打印元素值
	r.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()

	// Unlink 移除环形链表中的两个元素
	unlinked := r.Unlink(2)

	// 遍历被移除的子环形链表并打印元素值
	unlinked.Do(func(x interface{}) {
		fmt.Print(x, " ")
	})
	fmt.Println()
}

```

container/ring环形链表实现

container包定义了一套heap的接口，只要实现了这些接口就能作为一个heap来使用,定义如下
```go
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// heap 包为任何实现 heap.Interface 接口的类型提供堆操作。堆是一种具有以下特性的树形结构，
// 即每个节点都是其子树中值最小的节点。
//
// 树中的最小元素是根，索引为 0。
//
// 堆通常用于实现优先队列。要构建优先队列，请使用 (负) 优先级作为 Less 方法的排序，
// 这样 Push 就会添加项目，而 Pop 就会从队列中删除优先级最高的项目。
// 示例包括了这样一个实现；文件 example_pq_test.go 包含了完整的源代码。



package heap

import "sort"

// Interface 类型描述了使用此包中的例程的类型的要求。
// 任何实现此接口的类型都可用作最小堆，具有以下不变性（在调用 Init 后或数据为空或排序后）：
//
//	!h.Less(j, i) 对于 0 <= i < h.Len() 且 2*i+1 <= j <= 2*i+2 且 j < h.Len() 均成立
//
// 注意，此接口中的 Push 和 Pop 是供此包的实现调用的。
// 若要从堆中添加和删除元素，请使用 heap.Push 和 heap.Pop。

type Interface interface {
	sort.Interface
	Push(x any) // 将 x 添加为元素 Len()
	Pop() any   // 移除并返回元素 Len() - 1。
}

// Init 根据此包中的其他例程所需的堆不变性建立堆。
// 对于堆不变性来说，Init 是幂等的，可能在堆不变性可能无效时调用。
// 复杂度为 O(n)，其中 n = h.Len()。
func Init(h Interface) {
	// heapify
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

// Push 将元素 x 推入堆中。
// 复杂度为 O(log n)，其中 n = h.Len()。
func Push(h Interface, x any) {
	h.Push(x)
	up(h, h.Len()-1)
}

// Pop 从堆中移除并返回最小元素（根据 Less）。
// 复杂度为 O(log n)，其中 n = h.Len()。
// Pop 等效于 Remove(h, 0)。
func Pop(h Interface) any {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

// Remove 从堆中移除并返回索引 i 的元素。
// 复杂度为 O(log n)，其中 n = h.Len()。
func Remove(h Interface, i int) any {
	n := h.Len() - 1
	if n != i {
		h.Swap(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return h.Pop()
}

// Fix 在索引 i 的元素更改其值后重新建立堆顺序。
// 更改元素在索引 i 的值，然后调用 Fix 相当于调用 Remove(h, i)，
// 然后将新值推入堆中。复杂度为 O(log n)，其中 n = h.Len()。
func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

// up 将索引 j 处的元素向堆的根移动，直到满足堆不变性。
func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // 父节点
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

// down 将索引 i0 处的元素向堆的叶子移动，直到满足堆不变性。
// 如果 i0 已经是叶子，则返回 false。
func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // 在 int 溢出后 j1 < 0
			break
		}
		j := j1 // 左孩子
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // 右孩子
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}

```
使用实例
```go
package main

import (
	"container/heap"
	"fmt"
)

// 为整数切片实现 heap.Interface 接口
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push 将元素推入堆中
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

// Pop 从堆中弹出最小元素
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	// 初始化一个空堆
	var h IntHeap
	heap.Init(&h)

	// 将元素推入堆中
	heap.Push(&h, 3)
	heap.Push(&h, 5)
	heap.Push(&h, 1)

	// 从堆中弹出并打印最小元素
	fmt.Printf("Minimum: %d\n", heap.Pop(&h))

	// 将元素推入堆中
	heap.Push(&h, 4)

	// 打印堆中的所有元素
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(&h))
	}
}

```

![image.png](/static/img/3af3eaba973fd30e1fdc3648eade2dc4.image.webp)

go contaoner/heap实现

[cache](https://github.com/hashicorp/golang-lru)发现一个简单的cache项目，这里面有2q，arc cache实现,算法原理看末尾


下面是arc cache代码
```go
package arc



import (
	"sync"

	"github.com/hashicorp/golang-lru/v2/simplelru"
)

// ARCCache 是一个线程安全的固定大小的自适应替换缓存（ARC）。
// ARC 是对标准 LRU 缓存的增强，它同时跟踪使用的频率和最近性。
// 这样可以避免对新条目的访问的突发情况导致频繁使用的旧条目被驱逐。
// 与标准 LRU 缓存相比，它增加了一些额外的跟踪开销，计算上大约是 2 倍的成本，
// 并且额外的内存开销与缓存大小成线性关系。
// ARC 已被 IBM 专利，但类似于 TwoQueueCache（2Q），需要设置参数。
type ARCCache[K comparable, V any] struct {
	size int // Size 是缓存的总容量
	p    int // P 是对 T1 或 T2 的动态偏好

	t1 simplelru.LRUCache[K, V]        // T1 是最近访问的项目的 LRU
	b1 simplelru.LRUCache[K, struct{}] // B1 是从 T1 驱逐的项目的 LRU

	t2 simplelru.LRUCache[K, V]        // T2 是频繁访问的项目的 LRU
	b2 simplelru.LRUCache[K, struct{}] // B2 是从 T2 驱逐的项目的 LRU

	lock sync.RWMutex
}

// NewARC 创建一个给定大小的 ARC
func NewARC[K comparable, V any](size int) (*ARCCache[K, V], error) {
	// 创建子 LRUs
	b1, err := simplelru.NewLRU[K, struct{}](size, nil)
	if err != nil {
		return nil, err
	}
	b2, err := simplelru.NewLRU[K, struct{}](size, nil)
	if err != nil {
		return nil, err
	}
	t1, err := simplelru.NewLRU[K, V](size, nil)
	if err != nil {
		return nil, err
	}
	t2, err := simplelru.NewLRU[K, V](size, nil)
	if err != nil {
		return nil, err
	}

	// 初始化 ARC
	c := &ARCCache[K, V]{
		size: size,
		p:    0,
		t1:   t1,
		b1:   b1,
		t2:   t2,
		b2:   b2,
	}
	return c, nil
}

// Get 查找缓存中键的值。
func (c *ARCCache[K, V]) Get(key K) (value V, ok bool) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 如果值包含在 T1（最近）中，则提升到 T2（频繁）
	if val, ok := c.t1.Peek(key); ok {
		c.t1.Remove(key)
		c.t2.Add(key, val)
		return val, ok
	}

	// 检查值是否包含在 T2（频繁）中
	if val, ok := c.t2.Get(key); ok {
		return val, ok
	}

	// 未命中
	return
}

// Add 向缓存中添加一个值。
func (c *ARCCache[K, V]) Add(key K, value V) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 检查值是否包含在 T1（最近）中，可能提升到频繁的 T2
	if c.t1.Contains(key) {
		c.t1.Remove(key)
		c.t2.Add(key, value)
		return
	}

	// 检查值是否已经在 T2（频繁）中并更新它
	if c.t2.Contains(key) {
		c.t2.Add(key, value)
		return
	}

	// 检查该值是否最近作为最近使用列表的一部分而被驱逐
	if c.b1.Contains(key) {
		// T1 集合太小，适当地增加 P
		delta := 1
		b1Len := c.b1.Len()
		b2Len := c.b2.Len()
		if b2Len > b1Len {
			delta = b2Len / b1Len
		}
		if c.p+delta >= c.size {
			c.p = c.size
		} else {
			c.p += delta
		}

		// 可能需要在缓存中腾出空间
		if c.t1.Len()+c.t2.Len() >= c.size {
			c.replace(false)
		}

		// 从 B1 中删除
		c.b1.Remove(key)

		// 将键添加到频繁使用的列表中
		c.t2.Add(key, value)
		return
	}

	// 检查该值是否最近作为频繁使用列表的一部分而被驱逐
	if c.b2.Contains(key) {
		// T2 集合太小，适当地减小 P
		delta := 1
		b1Len := c.b1.Len()
		b2Len := c.b2.Len()
		if b1Len > b2Len {
			delta = b1Len / b2Len
		}
		if delta >= c.p {
			c.p = 0
		} else {
			c.p -= delta
		}

		// 可能需要在缓存中腾出空间
		if c.t1.Len()+c.t2.Len() >= c.size {
			c.replace(true)
		}

		// 从 B2 中删除
		c.b2.Remove(key)

		// 将键添加到频繁使用的列表中
		c.t2.Add(key, value)
		return
	}

	// 可能需要在缓存中腾出空间
	if c.t1.Len()+c.t2.Len() >= c.size {
		c.replace(false)
	}

	// 保持幽灵缓冲区的大小
	if c.b1.Len() > c.size-c.p {
		c.b1.RemoveOldest()
	}
	if c.b2.Len() > c.p {
		c.b2.RemoveOldest()
	}

	// 添加到最近看到的列表中
	c.t1.Add(key, value)
}

// replace 用于根据当前学到的 P 值自适应地从 T1 或 T2 中驱逐。
func (c *ARCCache[K, V]) replace(b2ContainsKey bool) {
	t1Len := c.t1.Len()
	if t1Len > 0 && (t1Len > c.p || (t1Len == c.p && b2ContainsKey)) {
		k, _, ok := c.t1.RemoveOldest()
		if ok {
			c.b1.Add(k, struct{}{})
		}
	} else {
		k, _, ok := c.t2.RemoveOldest()
		if ok {
			c.b2.Add(k, struct{}{})
		}
	}
}

// Len 返回缓存中条目的数量
func (c *ARCCache[K, V]) Len() int {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.t1.Len() + c.t2.Len()
}

// Keys 返回所有缓存的键
func (c *ARCCache[K, V]) Keys() []K {
	c.lock.RLock()
	defer c.lock.RUnlock()
	k1 := c.t1.Keys()
	k2 := c.t2.Keys()
	return append(k1, k2...)
}

// Values 返回所有缓存的值
func (c *ARCCache[K, V]) Values() []V {
	c.lock.RLock()
	defer c.lock.RUnlock()
	v1 := c.t1.Values()
	v2 := c.t2.Values()
	return append(v1, v2...)
}

// Remove 用于从缓存中清除键
func (c *ARCCache[K, V]) Remove(key K) {
	c.lock.Lock()
	defer c.lock.Unlock()
	if c.t1.Remove(key) {
		return
	}
	if c.t2.Remove(key) {
		return
	}
	if c.b1.Remove(key) {
		return
	}
	if c.b2.Remove(key) {
		return
	}
}

// Purge 用于清除缓存
func (c *ARCCache[K, V]) Purge() {
	c.lock.Lock()
	defer c.lock.Unlock()
	c.t1.Purge()
	c.t2.Purge()
	c.b1.Purge()
	c.b2.Purge()
}

// Contains 用于检查缓存是否包含键，而不更新最近性或频率。
func (c *ARCCache[K, V]) Contains(key K) bool {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.t1.Contains(key) || c.t2.Contains(key)
}

// Peek 用于检查键的缓存值，而不更新最近性或频率。
func (c *ARCCache[K, V]) Peek(key K) (value V, ok bool) {
	c.lock.RLock()
	defer c.lock.RUnlock()
	if val, ok := c.t1.Peek(key); ok {
		return val, ok
	}
	return c.t2.Peek(key)
}

```
接下来是2q缓存
```go

// 版权所有（c）HashiCorp，Inc。
// SPDX-License-Identifier: MPL-2.0

package lru

import (
	"errors"
	"sync"

	"github.com/hashicorp/golang-lru/v2/simplelru"
)

const (
	// Default2QRecentRatio 是 2Q 缓存中专用于最近添加的仅被访问一次的条目的比率。
	Default2QRecentRatio = 0.25

	// Default2QGhostEntries 是保存用于跟踪最近驱逐的条目的默认幽灵条目比率。
	Default2QGhostEntries = 0.50
)

// TwoQueueCache 是一个线程安全的固定大小的 2Q 缓存。
// 2Q 是对标准 LRU 缓存的增强，因为它单独跟踪频繁使用和最近使用的条目。
// 这避免了对新条目的访问的突发情况导致频繁使用的条目被驱逐。
// 它相对于标准 LRU 缓存增加了一些额外的跟踪开销，计算上大约是 2 倍的成本，并添加了一些元数据。
// ARCCache 类似，但不需要设置任何参数。
type TwoQueueCache[K comparable, V any] struct {
	size        int
	recentSize  int
	recentRatio float64
	ghostRatio  float64

	recent      simplelru.LRUCache[K, V]
	frequent    simplelru.LRUCache[K, V]
	recentEvict simplelru.LRUCache[K, struct{}]
	lock        sync.RWMutex
}

// New2Q 使用默认值为参数创建一个新的 TwoQueueCache。
func New2Q[K comparable, V any](size int) (*TwoQueueCache[K, V], error) {
	return New2QParams[K, V](size, Default2QRecentRatio, Default2QGhostEntries)
}

// New2QParams 使用提供的参数值创建一个新的 TwoQueueCache。
func New2QParams[K comparable, V any](size int, recentRatio, ghostRatio float64) (*TwoQueueCache[K, V], error) {
	if size <= 0 {
		return nil, errors.New("无效的大小")
	}
	if recentRatio < 0.0 || recentRatio > 1.0 {
		return nil, errors.New("无效的最近比率")
	}
	if ghostRatio < 0.0 || ghostRatio > 1.0 {
		return nil, errors.New("无效的幽灵比率")
	}

	// 确定子大小
	recentSize := int(float64(size) * recentRatio)
	evictSize := int(float64(size) * ghostRatio)

	// 分配 LRUs
	recent, err := simplelru.NewLRU[K, V](size, nil)
	if err != nil {
		return nil, err
	}
	frequent, err := simplelru.NewLRU[K, V](size, nil)
	if err != nil {
		return nil, err
	}
	recentEvict, err := simplelru.NewLRU[K, struct{}](evictSize, nil)
	if err != nil {
		return nil, err
	}

	// 初始化缓存
	c := &TwoQueueCache[K, V]{
		size:        size,
		recentSize:  recentSize,
		recentRatio: recentRatio,
		ghostRatio:  ghostRatio,
		recent:      recent,
		frequent:    frequent,
		recentEvict: recentEvict,
	}
	return c, nil
}

// Get 从缓存中查找键的值。
func (c *TwoQueueCache[K, V]) Get(key K) (value V, ok bool) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 检查这是否是一个频繁使用的值
	if val, ok := c.frequent.Get(key); ok {
		return val, ok
	}

	// 如果值包含在 recent 中，那么我们提升它到 frequent 中
	if val, ok := c.recent.Peek(key); ok {
		c.recent.Remove(key)
		c.frequent.Add(key, val)
		return val, ok
	}

	// 未命中
	return
}

// Add 向缓存中添加一个值。
func (c *TwoQueueCache[K, V]) Add(key K, value V) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 检查值是否已经频繁使用，并只更新值
	if c.frequent.Contains(key) {
		c.frequent.Add(key, value)
		return
	}

	// 检查值是否最近使用，并将值提升到频繁列表中
	if c.recent.Contains(key) {
		c.recent.Remove(key)
		c.frequent.Add(key, value)
		return
	}

	// 如果值最近被驱逐，将其添加到频繁使用的列表中
	if c.recentEvict.Contains(key) {
		c.ensureSpace(true)
		c.recentEvict.Remove(key)
		c.frequent.Add(key, value)
		return
	}

	// 添加到最近看到的列表中
	c.ensureSpace(false)
	c.recent.Add(key, value)
}

// ensureSpace 用于确保我们在缓存中有空间
func (c *TwoQueueCache[K, V]) ensureSpace(recentEvict bool) {
	// 如果我们有空间，什么也不做
	recentLen := c.recent.Len()
	freqLen := c.frequent.Len()
	if recentLen+freqLen < c.size {
		return
	}

	// 如果 recent 缓冲区比目标大，从那里驱逐
	if recentLen > 0 && (recentLen > c.recentSize || (recentLen == c.recentSize && !recentEvict)) {
		k, _, _ := c.recent.RemoveOldest()
		c.recentEvict.Add(k, struct{}{})
		return
	}

	// 否则从频繁列表中移除
	c.frequent.RemoveOldest()
}

// Len 返回缓存中的条目数。
func (c *TwoQueueCache[K, V]) Len() int {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.recent.Len() + c.frequent.Len()
}

// Resize 更改缓存大小。
func (c *TwoQueueCache[K, V]) Resize(size int) (evicted int) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// 重新计算子大小
	recentSize := int(float64(size) * c.recentRatio)
	evictSize := int(float64(size) * c.ghostRatio)
	c.size = size
	c.recentSize = recentSize

	// ensureSpace
	diff := c.recent.Len() + c.frequent.Len() - size
	if diff < 0 {
		diff = 0
	}
	for i := 0; i < diff; i++ {
		c.ensureSpace(true)
	}

	// 重新分配 LRUs
	c.recent.Resize(size)
	c.frequent.Resize(size)
	c.recentEvict.Resize(evictSize)

	return diff
}

// Keys 返回缓存中键的切片。
// 频繁使用的键在返回的切片中排在前面。
func (c *TwoQueueCache[K, V]) Keys() []K {
	c.lock.RLock()
	defer c.lock.RUnlock()
	k1 := c.frequent.Keys()
	k2 := c.recent.Keys()
	return append(k1, k2...)
}

// Values 返回缓存中值的切片。
// 频繁使用的值在返回的切片中排在前面。
func (c *TwoQueueCache[K, V]) Values() []V {
	c.lock.RLock()
	defer c.lock.RUnlock()
	v1 := c.frequent.Values()
	v2 := c.recent.Values()
	return append(v1, v2...)
}

// Remove 从缓存中移除提供的键。
func (c *TwoQueueCache[K, V]) Remove(key K) {
	c.lock.Lock()
	defer c.lock.Unlock()
	if c.frequent.Remove(key) {
		return
	}
	if c.recent.Remove(key) {
		return
	}
	if c.recentEvict.Remove(key) {
		return
	}
}

// Purge 用于完全清除缓存。
func (c *TwoQueueCache[K, V]) Purge() {
	c.lock.Lock()
	defer c.lock.Unlock()
	c.recent.Purge()
	c.frequent.Purge()
	c.recentEvict.Purge()
}

// Contains 用于检查缓存是否包含键，而不更新最近性或频率。
func (c *TwoQueueCache[K, V]) Contains(key K) bool {
	c.lock.RLock()
	defer c.lock.RUnlock()
	return c.frequent.Contains(key) || c.recent.Contains(key)
}

// Peek 用于检查键的缓存值，而不更新最近性或频率。
func (c *TwoQueueCache[K, V]) Peek(key K) (value V, ok bool) {
	c.lock.RLock()
	defer c.lock.RUnlock()
	if val, ok := c.frequent.Peek(key); ok {
		return val, ok
	}
	return c.recent.Peek(key)
}

```
---

1. [图解 LRU LFU ARC FIFO 缓存淘汰算法 - 掘金](https://juejin.cn/post/6923510255154528263)
2. [缓存淘汰算法（LFU、LRU、ARC、FIFO、2Q）分析 - 知乎](https://zhuanlan.zhihu.com/p/352910565)
3. [Adaptive Replacement Cache(ARC) 缓存淘汰算法 - 知乎](https://zhuanlan.zhihu.com/p/522306900)