白筱汐

想都是问题,做都是答案

0%

前言

冒泡排序是十大经典排序之一,它的时间复杂度为O(n^2),在最好的情况下能达到O(n)。

基本思想:

  1. 从数组的第一个元素开始,依次比较相邻的两个元素,如果它们的顺序错误(升序为左大于右,降序为左小于右),则进行交换。
  2. 经过一轮遍历后,最大(或最小)的元素会被交换到数组的末尾(或开头)。
  3. 对除了已排好序的部分外的所有元素重复执行步骤 1 和步骤 2,直到整个数组有序。

js代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bubbleSort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
let hasSort = true // 外循环,引入标志位
// 找到最大的元素放置到数组的尾部
for (var j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
hasSort = false // 满足交换条件,更改标志位
}
}
if (hasSort) break; // 已经排序完成,退出循环
}
return arr
}

// 交换元素的位置
function swap(arr, i, j) {
const temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}

代码解析:冒泡排序的代码比较简单,这里我们加入了标志位 hasSort 默认为 true,代表是否已经完成了排序。每次外循环开始的时候我们都默认已经完成了排序,如果内部循环满足交换两个元素的条件,则将它设置为 false,需要继续比较元素,进行排序。如果外循环的标志没有动过,说明它的子数组是有序的,无须交换,那么下次外循环就不需要进行。

其实这代代码还可以继续优化,我们留意到操作步骤的最后一步,每次排序结束,最后一个元素总是最大的,即大数下沉策略。当交换时,可以利用变量 swapPos 记录交换的位置。在内部循环结束后,将最后一个交换元素的位置赋值给k,这样就可以节省一下轮内循环时,从位置k到n-1的比较“开销”,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbleSort2(arr) {
let n = arr.length, k = n - 1, swapPos = 0
for (let i = 0; i < n; i++) {
let hasSort = true
for (let j = 0; j < k; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1)
swapPos = j // 记录交换位置,下一次内循环只用比较索引从 j 到 k -1 的元素
}
}
if (hasSort) break
k = swapPos
}
return arr
}

鸡尾酒排序,也称为双向冒泡排序(Cocktail Sort),是对冒泡排序的一种改进。它通过在每一轮遍历时交替地进行从左到右和从右到左的扫描和比较,来实现元素的排序。类似于“摇晃”一杯鸡尾酒的过程,因此得名为鸡尾酒排序。

基本思想:

  1. 首先,从左到右遍历数组,比较相邻的两个元素,如果它们的顺序错误,则进行交换,将较大的元素移到右侧。
  2. 然后,从右到左遍历数组,比较相邻的两个元素,如果它们的顺序错误,则进行交换,将较小的元素移到左侧。
  3. 重复以上步骤,直到没有发生交换为止。这意味着数组已经排序完成。

同样的,如果我们需要优化代码,需要加入标志位判断是否已经完成排序,同时记录满足交换条件时的索引,下次内循环就可以排除那些不需要比较的元素了。

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
function cocktailSort(array) {
let left,right,index,i
left = 0 // 数组的起始索引
right = array.length - 1 // 数组索引的最大值
index = left // 临时变量

// 判断数组中是否有多个元素
while (left < right) {
let isSorted = false
// 每一次进入while循环,都会找出相应范围内最大最小的元素并分别放到相应的位置
// 大的排到后面
for (let i = left; i < right; i++) { // 从左到右扫描,找出较大的元素
if (array[i] > array[i + 1]) {
swap(array, i, i + 1)
index = i // 记录当前索引
isSorted = true
}
}
right = index // 记录最后一个交换的位置
// 小的排到前面
for (let i = right; i > left; i--) {
if (array[i] < array[i - 1]) { // 从右到左扫描,找出较小的元素
swap(array, i, i - 1)
index = i
isSorted = true
}
}
left = index // 记录最后一个交换的位置
if (!isSorted) { // 没有需要排序的元素了,退出循环
break
}
}
return arr
}

我们可以这样理解,有left、right两个指针,分别指向数组的起点和终点。第一步的时候,从左往右扫描,如果找到较大的元素,将元素的索引赋值给right,相当于right指针左移到满足交换条件的元素索引处。第二步的时候,从右往左扫描,如果找到较小的元素,将元素的索引赋值给left,相当于left指针右移到满足交换的元素的索引处。当左右两个指针碰撞(数组中只有一个元素),排序结束,左边都是排序好的较小的元素,右边都排序好的较大的元素。这样整个数组就排序完成了。

go代码演示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 冒泡排序
func bubbleSort2(arr []int) []int {
n, k, swapPos := len(arr), len(arr)-1, 0
for i := 0; i < n; i++ {
hasSort := true // 外循环,引入标志位
for j := 0; j < k; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
hasSort = false // 满足交换条件,更改标志位
swapPos = j
}
}
if hasSort { // 已经排序完,退出循环
break
}
k = swapPos
}
return arr
}
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
// 鸡尾酒排序
func cocktailSort(arr []int) []int {
var i int
left, right := 0, len(arr)-1
index := left // 临时变量
// 判断数组中是否有多个元素
for left < right {
isSort := false // 标志位,如果内循环没有发生交换元素,退出循环
for i = left; i < right; i++ { // 从左往右扫描,找出较大的元素
if arr[i] > arr[i+1] {
arr[i], arr[i+1] = arr[i+1], arr[i]
isSort = true
index = i
}
}
right = index
for i = right; i > left; i++ { // 从右向左扫描,找出较小的元素
if arr[i] < arr[i-1] {
arr[i], arr[i-1] = arr[i-1], arr[i]
isSort = true
index = i
}
}
left = index
if !isSort {
break
}
}
return arr
}

介绍

分布式锁是一种用于协调分布式系统中多个进程或线程之间访问共享资源的机制。在分布式环境中,由于多个进程或服务可能并发地访问共享资源,如果没有一种机制来同步它们的访问,可能会引发数据不一致或竞态条件等问题。

分布式锁可以保证在同一时间只有一个进程或服务能够获得对共享资源的访问权,从而避免了并发访问带来的问题。

本文将介绍三种分布式锁的实现方式:

  1. mysql悲观锁
  2. mysql乐观锁
  3. redis分布式锁

Mysql悲观锁

当我们要对数据库中的一条数据进行修改的时候,为了避免同时被其他人修改,最好的办法就是直接对该数据进行加锁以防止并发。这种借助数据库锁机制在修改数据之前锁定,再修改的方式被称为悲观并发控制(PCC)。

这也就是这种锁被称为 “悲观” 的原因,它会以悲观的态度去对待并发的数据控制,认为共享数据被并发修改的可能性较高,在修改之前先去加锁。在实现效率上,处理加锁的过程会让数据库产生额外的开销,降低并发度,同时,还可能会有死锁的可能。

悲观锁的实现,依赖于数据库提供的锁机制(行级锁、表级锁)。它的工作流程可以总结如下:

  • 对数据操作之前,尝试获取锁
  • 获取锁成功,对数据进行修改、提交事务,最后释放锁
  • 获取锁失败,则锁正在被占用,等待或抛出异常

在 MySQL 中使用悲观锁,必须关闭 MySQL 的自动提交(MySQL 默认使用自动提交模式,即执行 INSERT、UPDATE、DELETE 时,结果自动生效)

1
2
3
4
-- 关闭自动提交
SET autocommit = 0;
-- 校验自动提交是否关闭
SHOW VARIABLES LIKE 'autocommit';

MySQL 提供的悲观锁实现方式是:SELECT … FOR UPDATE

1
2
-- 通过悲观锁语法锁住 id 为 1 的记录
SELECT * FROM goods WHERE id = 1 FOR UPDATE;

SELECT … FOR UPDATE 只允许一个事务获取到锁,其他的事务只能等待或者超时
但是,在使用悲观锁的时候,一定需要注意使用索引,否则行锁将会上升为表锁,引起系统问题

go伪代码事例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 开启事务
tx := db.Begin()

// 通过悲观锁语法锁住 id 为 1 的记录
tx.Clauses(clause.Locking{Strength: "UPDATE"}).Where(&Goods{ID:1}).First(&user)

// 业务操作
...

// 遇到错误时回滚事务
tx.Rollback()

// 提交事务
tx.Commit()

Mysql乐观锁

乐观锁其实是对 CAS(compare-and-swap)的实现:在做修改时,检查当前的环境是否与预定义的一致,如果一致则可以提交;否则,重试或抛异常。

可以想办法加入一个不会重复修改的值数据来作为版本号,即 version 参数,version 只能增加,不能减少。乐观锁在每次执行数据修改时,都需要去比对 version,如果一致,则更新数据的同时,也要更新 version。

1
2
3
4
5
6
7
8
-- 给 worker 表添加 version 列
ALTER TABLE `worker` ADD COLUMN `version` BIGINT(20) NOT NULL DEFAULT '0' COMMENT '乐观锁版本号';
-- 读取数据,记录 version 的值
SELECT * FROM worker WHERE id = 1;
-- 比对 version 是否符合预期,更新数据和 version
UPDATE worker SET salary = 2000, version = version + 1 WHERE id = 1 AND version = 0;
-- 再次读取数据,校验是否符合预期
SELECT * FROM worker WHERE id = 1;

乐观锁同样可以使用时间戳来实现,一样的道理.

go伪代码事例

1
2
3
4
5
6
7
8
9
10
11
for {
// 强制更新 Stock、Version字段,并时Version + 1
result := tx.Model(&model.Inventory{}).Select("Stocks", "Version").Where("goods = ? and version = ?", goodInfo.GoodsId, inv.Version).Updates(model.Inventory{Stocks: inv.Stocks, Version: inv.Version + 1})
if result.RowAffected == 0 {
// 更新失败重试
log.Printf()("更新失败")
} else {
// 退出循环
break
}
}

Redis分布式锁

Redis分布式锁是一种使用Redis实现的分布式协调机制,用于在分布式系统中控制多个节点对共享资源的并发访问。它通过利用Redis的原子性操作和特定的指令来实现同步和互斥,确保在任意时刻只有一个进程或线程能够持有锁.

  1. 锁的获取:在尝试获取锁时,可以使用Redis的SETNX命令(SET if Not eXists)设置一个特定的键值对,如果键不存在则成功获取锁。这一步是一个原子操作,确保只有一个客户端能够成功创建该键值对,从而获得锁.
  2. 锁的过期时间:为了避免死锁和进程崩溃导致的锁无法释放,需要为锁设置合理的过期时间。可以使用Redis的EXPIRE命令为键设置一个过期时间,在超过该时间后,Redis会自动删除该键,实现锁的自动释放。
  3. 锁的释放:当持有锁的进程完成对共享资源的操作后,需要显式地释放锁。可以通过使用Redis的DEL命令删除键来释放锁。释放锁的过程也需要是一个原子操作,以确保在同一时间只有一个进程持有锁。
  4. 避免误删其他进程的锁:为了避免出现误删其他进程的锁的情况,可以为每个客户端生成一个唯一的标识符作为锁的值,并且在释放锁时检查该标识符是否匹配,以确保只有获得锁的客户端才能释放锁。
  5. 防止锁过期时间过短导致的问题:为了避免锁的过期时间过短导致其他进程过早地获取了锁,可以使用轮询机制在锁即将过期时进行续约。具体做法是在获取锁后,为该锁设置一个适当的续约时间,确保在共享资源操作完成前不会过期。

需要强调的是,Redis分布式锁虽然在很多场景下是有效的,但并不是完全解决所有分布式环境中的同步问题的银弹。

使用插件redsync可以帮助我们快速实现基于go语言的Redis分布式锁。

以下是官方案例:

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
package main

import (
"github.com/go-redsync/redsync/v4"
"github.com/go-redsync/redsync/v4/redis/goredis/v9"
goredislib "github.com/redis/go-redis/v9"
)

func main() {
// 连接redis
client := goredislib.NewClient(&goredislib.Options{
Addr: "localhost:6379",
})
pool := goredis.NewPool(client) // 新建连接池

// 创建一个redsync实例,用来获取互斥锁
rs := redsync.New(pool)

// 创建命名互斥锁
mutexname := "my-global-mutex"
mutex := rs.NewMutex(mutexname)

//获取给定互斥对象的锁。在此操作成功后,没有其他人可以获得相同的锁(相同的互斥锁名称),直到我们解锁它
if err := mutex.Lock(); err != nil {
panic(err)
}

// 你的代码逻辑

// 释放锁,以便其他进程或线程可以获得锁
if ok, err := mutex.Unlock(); !ok || err != nil {
panic("unlock failed")
}
}

我们已经完成了基于Redis分布式锁的基本操作,但是仍有一些问题需要处理。比如:redis锁没有设置过期时间,也没有错误处理,另外在分布式系统中,可能有多个应用基于类似商品id做为分布式锁的名称,会出现锁重名现象。因为,我们可以使用uuid + goodsId 来生产唯一标识。

优化之后的代码大概如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
client := goredislib.NewClient(&goredislib.Options{
Addr: "localhost:6379",
})
pool := goredis.NewPool(client) // 新建连接池

// 创建一个redsync实例,用来获取互斥锁
rs := redsync.New(pool)

// 创建命名互斥锁
mutexname := "<uuid + goodsId>"
mutex := rs.NewMutex(mutexname)
// 尝试获取锁,最多等待 2 秒
if err := mutex.LockEx(time.Second * 2); err != nil {
fmt.Println("未能获得锁:", err)
return
}
defer func() {
// 通过 recover 捕获异常,确保释放锁
if r := recover(); r != nil {
fmt.Println("发生异常:", r)
}
mutex.Unlock()
}()

前言

图的广度优先遍历(Breadth-First Search,BFS)是一种用于遍历或搜索图的算法。它从图中的某个节点开始,按照广度优先的顺序逐层遍历图的节点,直到遍历完所有可达节点为止。

本案例介绍的是”非加权图“的广度优先遍历。一般用来解决两类问题:

1、从节点A出发,有前往节点B的路径吗?

2、从节点A出发,前往节点B的哪条路径最短

队列是一种先进先出的数据结构(First In First Out,FIFO),队列只有两种操作,入队和出队。

为了方便展示节点之间的关系,案例中使用“邻接表”的方式展示图。

1
2
3
4
5
6
7
8
9
// 示例图的邻接表
let graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
};

基本步骤

1.选择一个起始节点,并将其标记为已访问

2.将起始节点加入队列

3.重复以下步骤直到队列为空:

  • 从队列中取出一个节点,作为当前节点。
  • 遍历当前节点的所有相邻节点(未访问过的节点),并将它们标记为已访问。
  • 将这些相邻节点加入队列。

4.当队列为空时,遍历结束。

js代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bfs(graph, startNode) {
let queue = [startNode] // 使用队列保存待访问的节点
let visited = new Set() // 使用 Set 数据结构记录已访问的节点
visited.add(startNode)
while (queue.length > 0) {
const n = queue.shift() // 出队一个节点
graph[n].forEach(c => {
// (未访问过的)将相邻节点设置为已访问并加入队列
if (!visited.has(c)) {
visited.add(c)
queue.push(c);
}
})
}
return Array.from(visited)
}

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package main

import "fmt"

// GraphNode 定义图的结构
type GraphNode struct {
value int
adjacent []*GraphNode
visited bool
}

func NewGraphNode(value int) *GraphNode {
return &GraphNode{
value: value,
adjacent: make([]*GraphNode, 0),
visited: false,
}
}

func BFS(startNode *GraphNode) {
var queue []*GraphNode // 待访问的节点队列
queue = append(queue, startNode) // 将初始节点加入队列
startNode.visited = true // 将初始节点设置为已访问

for len(queue) > 0 {
node := queue[0] // 出队一个节点,作为当前节点
queue = queue[1:]
fmt.Println("当前节点:", node.value)
for _, graphNode := range node.adjacent {
// (未访问过的)将相邻节点设置为已访问并加入队列
if !graphNode.visited {
graphNode.visited = true
queue = append(queue, graphNode)
}
}
}
}

func main() {
// 创建图节点
node1 := NewGraphNode(1)
node2 := NewGraphNode(2)
node3 := NewGraphNode(3)
node4 := NewGraphNode(4)
node5 := NewGraphNode(5)

// 构建图的邻接关系
node1.adjacent = append(node1.adjacent, node2, node3)
node2.adjacent = append(node2.adjacent, node1, node4, node5)
node3.adjacent = append(node3.adjacent, node1)
node4.adjacent = append(node4.adjacent, node2)
node5.adjacent = append(node5.adjacent, node2)

// 从节点1开始进行BFS
BFS(node1)
}

前言

快速排序,是十大经典排序之一。它的时间复杂度为O(nlogn)。快速排序使用了“分而治之”的思想,使用这种思想的算法有二分查找、归并排序等。

“分而治之”是一种算法或问题解决策略,它将一个复杂的问题划分为更小、更简单的子问题,然后逐个解决这些子问题,最后将它们的解合并起来,得到原始问题的解。

解题思路

我们随机选取数组中的一个元素作为基准值,小于等于基准值的元素放到一个小数组,大于基准值的元素放到另一个小数组。然后再对小数组重复上面的操作,当小数组的元素只有一个时,我们认为它是已经排序的。

快速排序使用“递归”来实现。所以我们需要寻找“基准条件”和“递归条件”。
(ps:关键名词可以通过谷歌搜索或阅读《图解算法》来了解具体含义)

  • 第一步: 完成递归函数的整体思路代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function quickSort(arr,low,high) {
    // 数组长度必须大于1,否则认为数组已经排序好了
    if (low < high) {
    // 获取基准值的索引
    const povitIndex = partiton(arr,low,high);
    // 对分割后的左右子数组继续划分
    quickSort(arr, low, povitIndex - 1);
    quickSort(arr, povitIndex + 1,high);
    }
    return arr
    }
  • 第二步:完成划分函数的具体代码,这一步是解决问题的关键步骤

假设数组的最后一个元素为基准值povit,设置一个指针为i,它从数组的最左边开始。遍历数组,当元素小于等于基准值时,把当前遍历到的元素与指针i对应的元素交换位置,之后指针后移一步。当遍历到数组的倒数第二个元素时,循环结束。此时所有索引小于i的元素都小于基准值,也就是指针左侧的元素都是小于基准值的,交换povit与指针i对应元素的值。最后返回的i就是下一次分割的基准值索引。

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
function partiton(arr, low, high) {
// 设置指针i来寻找下次分割的基准值索引,它从最左边开始
let i = low
// 假设数组最后一个元素是基准值
let povit = arr(high)
for (let j = i; j < arr.length - 1; j++) {
// 小于等于基准值的元素放在前面
if (arr[j] <= povit) {
// 交换元素的位置
swap(arr,i,j)
i++
}
}
// 交换指针i对应元素和基准值的位置
// 指针i左侧的元素总是小于等于基准值,右侧的元素总是大于基准值
swap(arr,i,high)
// 分割完成,返回基准值的索引
return i
}

function swap(arr,i,j) {
const temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}

go语言完整代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func quickSort(arr []int, low, high int) []int {
if low < high {
pivotIndex := partition(arr, low, high)
quickSort(arr, low, pivotIndex-1)
quickSort(arr, pivotIndex+1, high)
}
return arr
}

func partition(arr []int, low, high int) int {
i := low
pivot := arr[high]
for j := i; j < high; j++ {
if arr[j] <= pivot {
arr[j], arr[i] = arr[i], arr[j]
i++
}
}
arr[i], arr[high] = arr[high], arr[i]
return i
}

前言

二分查找是力扣上的一道简单题,题号704。评论里面有人戏称这题这叫做算法第一题。
也许是因为它是《图解算法》上的第一道题目吧,这本书对于新人确实是比较友好。

题目描述:
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

解题思路:
定义两个指针,一个在数组的最左侧,一个在数组的最右侧。当左指针小于等于右指针,每次取数组的中间那个元素,将目标值与中间元素对比。如果目标值大于中间元素,则将左指针移到中间值索引 + 1的位置。如果目标值小于中间元素,则将右指针移动到中间值索引 - 1的位置。如果目标值等于中间元素则返回索引。

javascript代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const search = (nums, target) => {
// 定义左指针在数组最左侧,右指针在数组最右侧
let left = 0, right = nums.length - 1
while(left <= right) {
let mid = Math.floor((left + right)/2) // 中间元素的索引
let num = nums[mid] // 中间值
if (target === num) { // 找到目标值,返回索引
return mid
} else if (target > num ) {
left = mid + 1
} else {
right = mid - 1
}
}
return -1 // 没有找到返回 -1
}

go代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func search(nums []int,target int) int {
left,right := 0,len(nums) - 1
for left <= right {
mid := (left + right)/2
num := nums[mid]
if target == num {
return mid
} else if target > num {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}

介绍

LRU(Least Recently Used)和LFU(Least Frequently Used)是两种常见的缓存淘汰算法, 用于在缓存空间有限的情况下选择合适的缓存对象进行淘汰,以提高缓存的利用效率。

LRU算法基于”最近最少使用”的原则进行淘汰。它维护一个缓存的访问顺序链表,当有新的数据被访问时,如果数据已经在缓存中,则将其移到链表头部;如果数据不在缓存中,则将其添加到链表头部。当需要淘汰数据时,选择链表尾部的数据进行淘汰,因为尾部的数据是最近最少被访问的数据。

LFU算法基于”最不经常使用”的原则进行淘汰。它维护一个缓存对象的访问频次,对于每个访问到的对象,增加其访问频次。当需要淘汰数据时,选择访问频次最低的数据进行淘汰。

LRU和LFU算法都有各自的优势和适用场景:

  • LRU算法适用于访问具有时间局部性的数据,即最近被访问的数据可能在将来一段时间内仍然会被访问。LRU算法相对较简单,容易实现,适用于大多数场景。但是,当存在”热点数据”(被频繁访问的数据)时,LRU算法可能无法有效地保证缓存的命中率。
  • LFU算法适用于访问具有访问频次局部性的数据,即访问频次高的数据很可能在将来一段时间内仍然会被频繁访问。LFU算法需要维护每个对象的访问频次计数,相对于LRU算法来说更加复杂。LFU算法在面对热点数据的场景下表现较好,但在某些场景下可能存在”频次突变”的问题,即频次高的数据突然不再被访问,但因为频次计数较高而长时间无法被淘汰。

在实际应用中,我们可以根据具体的场景和需求选择合适的缓存淘汰策略,或者结合两种算法进行混合使用,以达到更好的缓存性能。

146. LRU 缓存 中等

下面用javascript代码演示一下LRU缓存:

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
// 最近最少使用
// 定义LRU缓存类
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}

get (key) {
if (this.cache.has(key)) {
const value = this.cache.get(key);
this.cache.delete(key); // 删除key在Map中的位置
this.cache.set(key, value); // 重新设置key对在Map的最后(最近使用,也就是设置为最新的)
return value;
}
return -1;
}

put (key, value) {
if (this.cache.has(key)) {
this.cache.delete(key); // 删除key在Map中的位置
} else if (this.cache.size >= this.capacity) {
// 缓存容量不够了
const oldestKey = this.cache.keys().next().value;
this.cache.delete(oldestKey); // 删除最旧的key
}
this.cache.set(key, value);
}
}

// 示例用法
const cache = new LRUCache(2); // 创建容量为2的LRU缓存

cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 输出 1

cache.put(3, 3);
console.log(cache.get(2)); // 输出 -1
console.log(cache.get(3)); // 输出 3

cache.put(4, 4);
console.log(cache.get(1)); // 输出 -1
console.log(cache.get(3)); // 输出 3
console.log(cache.get(4)); // 输出 4

这段代码的技巧就在于使用了ES6的Map和迭代器的功能。Map 的遍历顺序就是插入顺序,使用Map.prototype.keys():返回键名的遍历器。然后我们使用迭代器的 next() 方法获取数据结构的第一个成员,也就是最旧的。然后通过 value 属性来获取它的值。拿到最旧的key就可以删除它,最后重新设置key。(Map具有LRU特性)

460. LFU 缓存 困难

javascript代码实现LFU:

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
// 最不经常使用
// 最不经常使用
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
// 每个访问次数都对应存储一个 Set,里面包含 cache 里面的 Map 的 key
this.frequency = new Map();
this.minFrequency = 0;
}

get(key) {
if (this.cache.has(key)) {
const { value, freq } = this.cache.get(key);
this.updateFrequency(key, freq); // 更新访问次数
return value;
}
return -1;
}

put(key, value) {
if (this.capacity === 0) return;

if (this.cache.has(key)) {
const { freq } = this.cache.get(key); // 获取当前元素旧的访问次数
this.cache.set(key, { value, freq }); // 更新当前 key 对应的元素
this.updateFrequency(key, freq); // 更新当前的访问次数
} else {
if (this.cache.size >= this.capacity) {
// 获取访问次数最少的 key 组成的 Set
const leastFreq = this.frequency.get(this.minFrequency);
// 根据 Set 的 LRU 特性,返回最久未被访问的元素(如果访问次数最少的元素有多个,最久未被访问的元素会被删除)
const deleteKey = leastFreq.keys().next().value;
leastFreq.delete(deleteKey);
this.cache.delete(deleteKey);
}
// 新添加元素时设置元素的访问次数为 1
this.cache.set(key,{value,freq: 1});
if (!this.frequency.has(1)) {
// 新添加元素时,如果不存在访问次数为1对应的 Set,设置访问次数为 1 的 Set 为空
this.frequency.set(1,new Set())
}
// 设置访问次数为1的 Set 中添加当前的key
this.frequency.get(1).add(key);
this.minFrequency = 1; // 新添加元素时最小访问次数更新为 1
}
}

updateFrequency(key, freq) {
// 从当前访问次数 freq 对应的 Set中,删除当前的 key
const freqList = this.frequency.get(freq);
freqList.delete(key);

// 当前元素旧的访问次数等于最小访问次数并且当前访问次数 freq 组成的 Set 为空
//(元素旧的访问次数等于最小访问次数,并且最小访问次数对应的 Set 为空的情况)
// 如果某个元素它之前的访问次数为最小访问次数,而且没有其他元素与该元素的访问次数相同
if (freq === this.minFrequency && freqList.size === 0) {
this.minFrequency++; // 更新最小访问次数
}

if (!this.frequency.has(freq + 1)) {
this.frequency.set(freq + 1, new Set());
}
// 在更新后的访问次数对应的 Set 里面添加当前元素对应的 key
this.frequency.get(freq + 1).add(key);
this.cache.get(key).freq = freq + 1; // 更新当前元素的访问次数 + 1
}
}

// 示例用法
const cache = new LFUCache(2); // 创建容量为2的LFU缓存

cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 输出 1

cache.put(3, 3); // 删除 1
console.log(cache.get(2)); // 输出 2

console.log(cache.get(3)); // 输出 3

cache.put(4, 4); // 删除 2
console.log(cache.get(2)); // 输出 -1
console.log(cache.get(3)); // 输出 3
console.log(cache.get(4)); // 输出 4

同样这里使用了 Set 数据结构的 LRU 特性,在 frequency 对应的 Map 里面放在着每种访问次数对应的 key 组成的 Set。也就是说,访问次数相同的元素所对应的 key 存放在同一个 Set 中。这里要注意的就是新增元素时,设置访问次数为1的 Set为空,并且添加访问该元素的 key,同时设置最小访问次数为1。如果某个元素它之前的访问次数为最小访问次数,而且没有其他元素与该元素的访问次数相同,同时更新最小访问次数和该元素的访问次数,也就是该元素的访问次数 + 1,并且设置对应的 Set 数据结构为空,把当前访问的 key 添加进去。

go代码演示LRU缓存:

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package main

import "fmt"

// LRUCache 最近最少使用
type LRUCache struct {
size int
capacity int
cache map[int]*DoubleLinkNode
head, tail *DoubleLinkNode
}

// DoubleLinkNode 双向链表
type DoubleLinkNode struct {
key, value int
prev, next *DoubleLinkNode
}

// 初始化双向链表
func initDoubleLinkNode(key, value int) *DoubleLinkNode {
return &DoubleLinkNode{
key: key,
value: value,
}
}

// Constructor 初始化LRU缓存
func Constructor(capacity int) LRUCache {
l := LRUCache{
capacity: capacity,
cache: map[int]*DoubleLinkNode{},
head: initDoubleLinkNode(0, 0),
tail: initDoubleLinkNode(0, 0),
}
l.head.next = l.tail
l.tail.prev = l.head
return l
}

func (l *LRUCache) Get(key int) int {
if _, ok := l.cache[key]; !ok {
return -1
}
node := l.cache[key]
l.moveToHead(node)
return node.value
}

func (l *LRUCache) Put(key, value int) {
// 新增元素 放在链表头部
if _, ok := l.cache[key]; !ok {
node := initDoubleLinkNode(key, value)
l.cache[key] = node
l.addToHead(node)
l.size++
// 超出容量 删除最后一个元素
if l.size > l.capacity {
removed := l.removeTail()
delete(l.cache, removed.key)
l.size--
}
} else {
// 更新元素 放在链表头部
node := l.cache[key]
node.value = value
l.moveToHead(node)
}
}

func (l *LRUCache) addToHead(node *DoubleLinkNode) {
node.prev = l.head
node.next = l.head.next
l.head.next.prev = node
l.head.next = node
}

func (l *LRUCache) removeNode(node *DoubleLinkNode) {
node.prev.next = node.next
node.next.prev = node.prev
}

func (l *LRUCache) moveToHead(node *DoubleLinkNode) {
l.removeNode(node)
l.addToHead(node)
}

func (l *LRUCache) removeTail() *DoubleLinkNode {
node := l.tail.prev
l.removeNode(node)
return node
}

func main() {
cache := Constructor(2)

cache.Put(1, 1)
cache.Put(2, 2)

fmt.Println(cache.Get(1)) //删除2 输出 1

cache.Put(3, 3)

fmt.Println(cache.Get(2)) // 输出 -1

cache.Put(4, 4) // 删除 1

fmt.Println(cache.Get(1)) // 输出 -1
fmt.Println(cache.Get(3)) // 输出 3
fmt.Println(cache.Get(4)) // 输出 4
}

代码使用了双向链表 + map实现了LRU数据结构。代码中采用了首尾虚拟节点,访问到的节点移动到头部,超出容量时删除尾部的节点。

go代码实现LFU数据结构:

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package main

import "fmt"

// LFUCache 最不经常使用
type LFUCache struct {
size int // 大小
capacity int // 容量
minFreq int // 最小访问次数
cache map[int]*Node
freq map[int]*DLinkedList
}

type Node struct {
key int
value int
freq int // 访问次数
prev, next *Node
}

// DLinkedList 访问次数为n的元素组成的双向链表(LRU特性)
type DLinkedList struct {
head, tail *Node
}

func Constructor(capacity int) LFUCache {
return LFUCache{
capacity: capacity,
cache: make(map[int]*Node),
freq: make(map[int]*DLinkedList),
}
}

func InitDLinkedList() *DLinkedList {
head, tail := &Node{}, &Node{}
head.next = tail
tail.prev = head
return &DLinkedList{
head: head,
tail: tail,
}
}

func (d *DLinkedList) AddToHead(node *Node) {
node.prev = d.head
node.next = d.head.next

d.head.next.prev = node
d.head.next = node
}

func (d *DLinkedList) Remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev

node.prev = nil
node.next = nil
}

func (d *DLinkedList) RemoveTail() *Node {
// 空链表
if d.IsEmpty() {
return nil
}
last := d.tail.prev
d.Remove(last)
return last
}

func (d *DLinkedList) IsEmpty() bool {
return d.head.next == d.tail
}

func (l *LFUCache) Get(key int) int {
if node, ok := l.cache[key]; ok {
l.addFreq(node)
return node.value
}
return -1
}

func (l *LFUCache) Put(key, value int) {
if l.capacity == 0 {
return
}
// 更新
if node, ok := l.cache[key]; ok {
node.value = value
l.addFreq(node)
} else {
// 超出容量,删除访问次数最低的对应数据链表的最旧的元素
if l.size >= l.capacity {
node := l.freq[l.minFreq].RemoveTail()
delete(l.cache, node.key)
l.size--
}
node := &Node{key: key, value: value, freq: 1}
l.cache[key] = node // 储存新节点

if l.freq[1] == nil {
l.freq[1] = InitDLinkedList()
}
l.freq[1].AddToHead(node)

l.minFreq = 1
l.size++
}
}

func (l *LFUCache) addFreq(node *Node) {
n := node.freq
l.freq[n].Remove(node)

if l.minFreq == n && l.freq[n].IsEmpty() {
l.minFreq++
delete(l.freq, n)
}

node.freq++
if l.freq[node.freq] == nil {
l.freq[node.freq] = InitDLinkedList()
}
l.freq[node.freq].AddToHead(node)
}

func main() {
cache := Constructor(2)
cache.Put(1, 1)
cache.Put(2, 2)

fmt.Println(cache.Get(1)) // 1
cache.Put(3, 3) // 删除2

fmt.Println(cache.Get(2)) // -1
fmt.Println(cache.Get(3)) // 3

cache.Put(4, 4) // key2被淘汰

fmt.Println(cache.Get(1)) // -1
fmt.Println(cache.Get(3)) // 3
fmt.Println(cache.Get(4)) // 4
}

cache存储对应的数据节点,但是可能会出现节点访问次数相同的情况。对应访问次数相同的节点,我们把放在一个双向链表中,然后根据LRU最近最少使用,超过容量的时候删除双向链表尾部的节点。拿到节点的key,之后就能从map中删除储存的节点了。

Linux shell基础命令

最近在学习Linux,写几篇文章来记录一下我的学习过程。

shell提示符

默认的bash shell提示符是美元符($),这个符号表明shell在等待用户输入命令。

浏览文件系统

Linux将文件存储在名为虚拟目录的单个目录结构中。
虚拟目录会将计算机中所有存储设备的文件路径都纳入单个目录结构。
Linux使用正斜线(\)来分隔文件路径中的目录。反斜线在Linux中用作转义字符。

系统文件通常存储在根驱动器中,而用户文件则存储在其他驱动器中。

路径本身并没有提供任何有关文件究竟放在哪个物理磁盘中的信息。
我们称在linux系统中安装的第一块硬盘为根驱动器
根驱动器包含了虚拟目录的核心,其他目录都是从那里构建的。

man 查看命令所有可用选项,例如:

1
man ls

遍历目录

进入到桌面目录

1
cd desktop

cd 目标参数可以是绝对路径也可以是相对路径。

1.绝对路径

绝对路径总是以正斜线(/)作为起始,以指明虚拟文件系统的根目录。
例如:

1
cd /usr/bin

2.相对路径

相对路径允许你指定一个基于当前位置的目标路径。相对路径不以代表根目录的正斜线(/)开头,
而是以目录名或是一个特殊字符开始。例如:

1
cd Documents

有两个特殊字符可用于相对路径:

  • 单点号(.),表示当前目录。
  • 双点号(..),表示当前目录的父目录。

双点号非常便利,例如:

1
cd ../Downloads

pwd命令可以显示出shell对话的当前目录。

1
pwd

显示基本列表

ls命令会显示当前目录下的文件和目录。

1
ls

ls -F 可以区分显示文件和目录,目录名之后会添加正斜线(/)展示,可执行文件后会加上星号(*)。

1
ls -F

Linux经常使用隐藏文件来保存配置信息。在Linux中隐藏文件通常是文件名以点号(.)开始的文件。
这些文件并不会在ls命令的默认输出中出现。因此,我们称其为隐藏文件。

ls -a 显示隐藏文件

1
ls -a

-R是ls命令的另一个选项,称作递归选项,可以列出当前目录所包含的子目录中的文件。
-F选项用于帮助分辨文件类型。

1
ls -F -R

或者 ls -FR。

-l选项会产生长列表格式的输出,提供目录中各个文件的详细信息。

1
ls -l

每一行都包含另关于文件(或目录)的下列信息。
·文件类型,比如目录(d)、文件(-)、链接文件(l)、字符设备(c)或块设备(b)。

  • 文件的权限
  • 文件的硬链接数
  • 文件属主
  • 文件属组
  • 文件大小(以字节为单位)
  • 文件的上次修改时间
  • 文件名或目录名

如果只想查看单个文件的长列表,可以用 ls -l 文件名。
如果想查看目录的相关信息,而非目录所包含的内容,可以用 ls -l 目录名。

ls -l 过滤器就是一个字符串,可做简单的文本匹配。
例如:

1
ls -l my_script

当指定特点的文件名作为过滤器时,ls命令只会显示该文件的信息。

ls命令也能识别标准通配符,并在过滤器中用其进行匹配模式:

  • 问号(?)代表任意单个字符。
  • 星号(*)代表零个或多个字符。

例如:

1
ls -l my_scr?pt
1
ls -l my*

方括号:代表单个字符位置并给出了该位置上的多个可能的选择。
例如:

1
ls f[a-z]ll

使用感叹号(!)将不需要的内容排除在外。

1
ls -l f[!a]ll

创建文件

touch命令会创建好指定的文件并将你的用户名作为该文件的属主。

1
touch test.txt

touch命令还可用来改变文件的修改时间。该操作不会修改文件。

复制文件

复制源对象到目标对象:
cp source destination

1
cp test_one test_two

加上-i选项,强制shell询问是否需要覆盖已有文件。

1
cp -i test_one test_two

将文件复制到现有目录中

1
cp -i test_two Document/

将源文件复制到当前工作目录中

1
cp /etc/nginx.conf .

cp -R 递归地复制整个目录的内容

1
cp -R Documents/ newDocuments/

也可以使用通配符

1
cp my* newDocuments/

命令行补全

制表键补全允许你在输入文件名或目录名的时候,按一下制表符,让shell帮你将内容补全完整。

链接文件

链接是目录中指向文件真实位置的占位符。在Linux中有两种类型的文件链接:

  • 符号链接
  • 硬链接

符号链接(也称为软链接)是一个实实在在的文件,该文件指向存放在虚拟目录中某个地方的另一个文件。
这两个以符号方式链接在一起的文件彼此的内容并不相同。

使用ln命令以及-s选项来创建符号链接:

1
ln -s test_file slink_test_file

长列表(ls -l)中显示的符号文件名后的 - > 符号表明该文件是链接文件test_file的
一个符号链接。
符号链接仅仅只是指向test_file而已,它的文件大小很小。

另一种证明链接文件是一个独立的文件的方法是查看inode编号。文件或目录的inode编号是内核
分配给文件系统中的每一个对象的唯一标识。要查看文件的inode编号,可以使用ls命令的-i选项:

1
ln -i 文件路径

硬链接创建的是一个独立的虚拟文件,其中包含了原始文件的信息以及位置。
但是 两者就根本而言是同一个文件。创建硬链接操作:

1
ls test_one hlink_test_one

注意:硬链接不能跨文件系统,软链接可以跨文件系统。

文件重命名

在Linux中,重命名文件称为移动
mv命令可以将文件和目录移动到另一个位置或是重新命名。

重命名文件

1
mv fall fzll

移动文件并重命名

1
mv fall download/fzll

使用-i选项,在mv试图覆盖已有文件时会发出询问。

移动文件不会改变文件的inode编号和时间戳。

移动整个目录及其内容:

1
mv olddir newdir

删除文件

询问是否真的要删除文件

1
rm -i fall

使用通配符元字符删除一组文件

1
rm -i f?ll

管理目录

创建目录

1
mkdir files

批量的创建目录和子目录

1
mkdir -p files/logs

删除目录

1
rmdir dir

rmdir 命令只会删除空目录。
对于rm命令,-r选项可以递归的删除目录中的文件。

直接删除整个目录树的最终解决方案时使用 rm -rf 命令。
注意:该操作十分的危险,请明确了解自己在做什么。

查看文件类型

file命令能够探测文件的内部并判断文件类型:

1
file .base

也可以用来区分目录,file命令后面跟上一个目录

1
file Documents

file命令后面接符号链接文件,能告诉你它链接到了哪个文件:

1
2
3
4
5
6
7
file slink_test_file

### 查看整个文件

cat 命令会显示文本文件中的所有数据
```shell
cat test_file

-n 选项会给所有的行加上行号

-b 选项给有文本的的行加上行号

more 命令支持分页查看文件

1
more /etc/profile

less 命令可以在完成整个文件的读取之前显示文件的内容,它能够识别上下箭头键以及上下翻页键。

查看部分文件

tail 命令会显示文件最后几行的内容,默认展示10行。

1
tail log_file

显示最后2行的数据

1
2
tail -n 2 log_file

head 命令会显示文件开头的若干行,默认显示10行。
这里表示显示头部3行

1
head -3 log_file