发表algorithm / data structure / cache / lru5 分钟读完 (大约702个字)

LRU 缓存

背景

内存空间是有限的，当数据量超过空间的时候就得考虑淘汰哪部分数据，那按什么规则淘汰呢？

把最久没用到的数据淘汰了不就行了，最久没用的数据直觉上不就是不太会被访问的数据吗，既然不会被访问，那就先淘汰呗，LRU 算法就是这么来的

LRU（Least Recently Used）按字面意思理解就是最近最少使用，那该怎么知道哪个数据是最近最少使用的呢？

LRU 的数据结构

用链表实现！

用链表是个很自然就可以想到的办法。每次数据块在存取完后将其重新排到头节点上，这样当数据在头节点说明它最近才被使用过

数据块在尾节点说明它是最久没被用到的，当数据超出内存限制时将尾节点的数据块删掉就行了

但链表有个缺点

就是链表查询、更新、删除操作的时间复杂度都是 O(n)，只有在头尾新增数据时才是 O(1)，要是能把 O(n) 复杂度都降到 O(1) 岂不妙哉？

用哈希表呀！

哈希表查询数据的复杂度不就是 O(1) 嘛！

那我们该怎么把哈希表用进去呢？

首先数据在查询时肯定需要从哈希表查，这样才能发挥出哈希表查得快的作用

其次要把数据被使用的信息体现到链表里（也就是把刚用过的数据提到头节点），这样才可以在数据溢出时知道去淘汰哪个

话不多说，3，2，1，上代码！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package problems

type LRUCache struct {
	LinkedList    *DoubleLinkedList
	LinkedNodeMap map[int]*DoubleLinkedNode
	capacity      int
}

func Constructor(capacity int) LRUCache {
	if capacity == 0 {
		panic("capacity should not be zero")
	}
	return LRUCache{
		LinkedList:    ConstructDoubleLinkedList(),
		LinkedNodeMap: map[int]*DoubleLinkedNode{},
		capacity:      capacity,
	}
}

func (cache *LRUCache) Get(key int) int {
	node, ok := cache.LinkedNodeMap[key]
	if !ok {
		return -1
	}
	cache.LinkedList.MoveToTop(node)
	return node.Value.(CacheNode).Value
}

func (cache *LRUCache) Put(key int, value int) {
	newCacheNode := CacheNode{key, value}
	node, ok := cache.LinkedNodeMap[key]

	if ok {
		node.Value = newCacheNode
		cache.LinkedList.MoveToTop(node)
		return
	}

	if len(cache.LinkedNodeMap) == cache.capacity {
		delete(cache.LinkedNodeMap, cache.LinkedList.Tail.Pre.Value.(CacheNode).Key)
		cache.LinkedList.Remove(cache.LinkedList.Tail.Pre)
	}

	newLinkedNode := &DoubleLinkedNode{Value: newCacheNode}
	cache.LinkedNodeMap[key] = newLinkedNode
	cache.LinkedList.AddToTop(newLinkedNode)
}

type DoubleLinkedList struct {
	Head *DoubleLinkedNode
	Tail *DoubleLinkedNode
}

func ConstructDoubleLinkedList() *DoubleLinkedList {
	tail := &DoubleLinkedNode{}
	head := &DoubleLinkedNode{}
	tail.Pre = head
	head.Next = tail
	return &DoubleLinkedList{
		Head: head,
		Tail: tail,
	}
}

func (list *DoubleLinkedList) MoveToTop(node *DoubleLinkedNode) {
	list.Remove(node)
	list.AddToTop(node)
}

func (list *DoubleLinkedList) Remove(node *DoubleLinkedNode) {
	node.Pre.Next = node.Next
	node.Next.Pre = node.Pre
}

func (list *DoubleLinkedList) AddToTop(node *DoubleLinkedNode) {
	list.Head.Next.Pre = node
	node.Next = list.Head.Next
	node.Pre = list.Head
	list.Head.Next = node
}

type CacheNode struct {
	Key   int
	Value int
}

I have a 链表～, I have a 哈希表～, 嗯！？LRU Cache ！

怎么样，是不是很好玩呀

发表algorithm / string / KMP3 分钟读完 (大约520个字)

深入浅出图解 KMP 算法思想

维基百科介绍

在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。这个算法由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。

核心思想

利用最长相等前后缀跳过相等字符，避免多余计算

核心步骤

  1. 计算模式串的最长相等前后缀数组（next 数组）
  2. 利用 next 数组在匹配字符串时跳过相等的字符，直到匹配结束

图解

Go 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package problems

func strStr(haystack string, needle string) int {
	if len(needle) == 0 || len(haystack) == 0 {
		return -1
	}
	j := 0
	next := getNext(needle)
	for i := 0; i < len(haystack); i++ {
		for j > 0 && haystack[i] != needle[j] {
			j = next[j-1]
		}
		if haystack[i] == needle[j] {
			j++
		}
		if j == len(needle) {
			return i - len(needle) + 1
		}
	}
	return -1
}

func getNext(s string) []int {
	j := 0
	next := make([]int, len(s))
	next[0] = 0
	for i := 1; i < len(s); i++ {
		for j > 0 && s[j] != s[i] {
			j = next[j-1]
		}
		if s[j] == s[i] {
			j++
		}
		next[i] = j
	}
	return next
}

测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package problems

import (
	"reflect"
	"testing"
)

func Test_getNext(t *testing.T) {
	type args struct {
		s string
	}
	tests := []struct {
		name string
		args args
		want []int
	}{
		{
			name: "",
			args: args{
				s: "benbenw",
			},
			want: []int{0, 0, 0, 1, 2, 3, 0},
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := getNext(tt.args.s); !reflect.DeepEqual(got, tt.want) {
				t.Errorf("getNext() = %v, want %v", got, tt.want)
			}
		})
	}
}

func Test_strStr(t *testing.T) {
	type args struct {
		haystack string
		needle   string
	}
	tests := []struct {
		name string
		args args
		want int
	}{
		{
			name: "",
			args: args{
				haystack: "benbenbenw",
				needle:   "benbenw",
			},
			want: 3,
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := strStr(tt.args.haystack, tt.args.needle); got != tt.want {
				t.Errorf("strStr() = %v, want %v", got, tt.want)
			}
		})
	}
}

力扣相关题目

力扣 28 题：找出字符串中第一个匹配项的下标
力扣 459 题：重复的子字符串

发表algorithm / sort / quicksort3 分钟读完 (大约483个字)

图解快速排序

维基百科介绍

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），是一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n 个项目要 O(nlogn) 次比较。在最坏状况下则需要 O(n2) 次比较，但这种状况并不常见。事实上，快速排序 Θ(nlog⁡n) 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

核心步骤

  1. 选择基准：选择待排序数组中的一个数字作为基准
  2. 按基准分组：遍历数组元素，将小于基准值的数字移动到基准值左侧，大于的则移到右侧
  3. 递归：在基准值左侧与右侧数组重复 1、2、3 步，直到所有数据排序完成

核心步骤图解

C 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>

void EXCHANGE(int *left, int *right)
{
  if (left == right)
    return;
  *left ^= *right;
  *right ^= *left;
  *left ^= *right;
}

int PARTITION(int A[], int left, int right)
{
  int pivotValue = A[right];
  int pivotDest = left;
  for (int i = left; i < right; i++)
  {
    if (A[i] <= pivotValue)
    {
      EXCHANGE(&A[pivotDest], &A[i]);
      pivotDest++;
    }
  }
  EXCHANGE(&A[pivotDest], &A[right]);
  return pivotDest;
}

void QUICKSORT(int A[], int left, int right)
{
  if (left < right)
  {
    int pivot = PARTITION(A, left, right);
    QUICKSORT(A, left, pivot - 1);
    QUICKSORT(A, pivot + 1, right);
  }
}

int main(int argc, char const *argv[])
{
  int A[] = {7, 3, 9, 5, 8, 4, 2};
  QUICKSORT(A, 0, 7);
  for (int i = 0; i <= 7; i++)
  {
    printf("%d ", A[i]);
  }
  printf("\n");
  return 0;
}

Go 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package sort

func QuickSort(a []int) []int {
	partition := func(a []int, lo, hi int) int {
		i, j := lo+1, hi
		for {
			for ; i < hi && a[i] <= a[lo]; i++ {
			}
			for ; j > lo && a[j] >= a[lo]; j-- {
			}
			if j <= i {
				break
			}
			a[i], a[j] = a[j], a[i]
		}
		a[i-1], a[lo] = a[lo], a[i-1]
		return i - 1
	}

	var sort func(a []int, lo, hi int)
	sort = func(a []int, lo, hi int) {
		if lo >= hi {
			return
		}
		j := partition(a, lo, hi)
		sort(a, lo, j-1)
		sort(a, j+1, hi)
	}
	sort(a, 0, len(a)-1)
	return a
}

改进

数组偏小时改用插入排序

1
2
3
4
if lo+M >= hi {
	InsertionSort(a, lo, hi)
	return
}
关注我

分类

标签

Go1
Hash Table1
KMP1
Source Code1
algorithm3
cache1
data structure1
lru1
mac1
nginx1
quicksort1
sort1
string1
tips1
tutorial1

最新文章

归档

×