bc's club

This is Bc's club

操作系统

一、并发#

1 协程、线程、进程#

  • 进程是资源分配和拥有的基本单位。运行一个可执行程序会创建一个或多个进程,进程就是运行起来的可执行程序
  • 线程是程序执行的基本单位,是轻量级的进程。每个进程都有唯一的主线程,且只能有一个,主线程和进程是相互依存的关系,主线程结束进程也会结束。
  • 协程是用户态的轻量级线程,是线程内部调度的基本单位。

2 进程调度算法#

  • 先到先服务:FCFS
  • 短作业优先
  • 最短剩余时间优先
  • 时间片轮转
    • 所有进程按到达时间排队,每次分配一个时间片给队首进程,执行完放到队尾。
    • 时间片太小,会导致进程切换得太频繁,在进程切换上就会花过多时间。
    • 时间片太长,实时性不能得到保证
  • 优先级调度
    • 每个进程分配一个优先级,按优先级进行调度。
    • 为了防止饿死,随着时间的推移增加等待进程的优先级
  • 多级反馈队列
    • 多个队列,1,2,4,8,…个时间片。进程在第一个队列没执行完,就会被移到下一个队列。
    • 最上面的优先权最高。因此只有上一个队列没有进程在排队,才能调度当前队列上的进程。
    • 能解决时间片多的进程的切换成本。

3 阻塞IO、非阻塞IO、多路复用IO。#

blog.csdn.net/Chen4852010…

  • 阻塞IO
    • 当用户线程发出IO请求后,内核会去查看数据是否就绪,未就绪的话就会等待。用户线程处于阻塞状态,用户线程交出CPU。
  • 非阻塞IO
    • 用户线程不断询问内核,数据是否就绪,不会交出CPU,而是一直占用CPU
  • 多路复用IO
    • 单个线程就可以同时处理多个IO请求,单个线程可以监视多个文件句柄,一旦某个文件句柄就绪,就能够通知应用程序进行相应的读写操作。没有文件句柄就绪时,会阻塞应用程序,交出cpu。
  • 如何实现多路复用IO
    • 在linux中有三种机制可以实现多路复用IO,select,poll,epoll

4 select、poll、epoll#

blog.csdn.net/dolly_baby/…

  • select
    1. 会修改传入的参数数组。
    2. 扫描是轮询
    3. 非线程安全。
  • poll
    1. 不修改传入数组;
    2. 扫描也是轮询
    3. 非线程安全
    4. 如果报告了fd后,没有被处理,那么下次poll时会再次报告这个fd。
  • epoll
    1. 仅支持linux
    2. 支持边缘触发和水平触发
    3. 底层的红黑树用于查找,底层的双向链表用于就绪事件的通知
  • epoll的水平触发和边缘触发的区别
    • 边沿触发:
      1. socket的接收缓冲区状态变化时触发读事件,即空的接收缓冲区刚接收到数据时触发读事件
      2. socket的发送缓冲区状态变化时触发写事件,即满的缓冲区刚空出空间时触发读事件
      3. 仅在缓冲区状态变化时触发事件
    • 水平触发:
      1. socket接收缓冲区不为空,有数据可读,则读事件一直触发
      2. socket发送缓冲区不满可以继续写入数据,则写一直触发

5 进程间通信方式#

  1. 管道:用于具有亲缘关系的进程之间的通信。
  2. 有名管道:遵循先进先出。以磁盘文件的方式存在,可以实现本机任意两个进程通信。
  3. 共享内存:不同进程可以访问同一块内存空间,不同进程可以及时看到对方进程中对共享内存中数据的更新。需要依靠同步操作,如互斥锁和信号量。
  4. 消息队列:消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。也是先进先出。
  5. 信号:用于通知接收进程某个事件已经发生
  6. 信号量:信号量是一个计数器,用于控制多个进程对共享数据的访问。
  7. 套接字:用于在客户端和服务器之间通过网络进行通信。

同一台机器进程通信最快的方式是什么,为什么。

  • 共享内存通信最快,共享内存的消息复制只有两次。

6 死锁的必要条件#

  1. 互斥
  2. 请求和保持
  3. 不可抢占
  4. 循环等待

7 进程状态#

  • 运行态:包括就绪
  • 阻塞态/睡眠态:等待IO操作
  • 死亡态
  • 僵尸态:子进程退出,父进程没有处理完子进程退出信息

8 用户态和内核态#

  • 内核态可以访问所有数据
  • 用户态只能受限的访问内存

需要限制不同的程序之间的访问能力

  • 如何避免频繁切换用户态和内核态
    1. 减少线程切换,释放锁和加锁会引起较多上下文切换
    2. 用CAS算法,避免阻塞现场
    3. 使用协程

二、内存#

1 页面置换算法#

  • 最佳页面置换算法:OPT
    • 选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。无法实现,是衡量其他算法的参考。
  • 先进先出页面置换算法:FIFO
    • 总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面进行淘汰。
  • 最近最久未使用页面置换算法:LRU
    • 记录每个页面上一次被访问到现在的时间,选最久未被使用的淘汰。
  • 最少使用页面置换算法:LFU
    • 选择之前使用次数最少的页面进行淘汰
  • 时钟置换算法:CLOCK

最佳置换算法性OPT能最好,但无法实现;
先进先出置换算法FIFO实现简单,但算法性能差;
最近最久未使用置换算法LRU性能好,但是实现起来需要专门的硬件支持,算法开销大。

2 栈上分配内存快还是堆上分配内存快#

栈上分配内存更快,因为栈上只需要移动栈指针

  1. 操作系统会在底层对栈提供支持,会分配专门的寄存器,存放栈的地址
  2. 栈的入栈出栈操作简单,有专门的指令执行,栈效率高
  3. 堆生长空间向上,地址越来越大,栈的生长空间向下,地址越来越小

3 内存分段分页#

  • 分段
    • 将程序分为代码段、数据段、堆栈段等。
  • 分页
    • 将段分成均匀的小块
    • 通过页表映射物理内存

设计模式

设计模式#

设计模式简介&分类#

设计模式是软件开发中常用的一种设计思想,用于解决特定的问题。根据设计模式的分类方式不同,可以有不同的模式数量。

按照常用的分类方式,设计模式可以分为三类:

创建型模式(Creational Patterns):用于创建对象的模式,包括简单工厂模式、工厂方法模式、抽象工厂模式、建造者模式、原型模式和单例模式等。

结构型模式(Structural Patterns):用于描述如何组合类和对象以形成更大的结构,包括适配器模式、桥接模式、组合模式、装饰器模式、外观模式、享元模式和代理模式等。

行为型模式(Behavioral Patterns):用于描述对象之间的通信方式和职责划分,包括责任链模式、命令模式、解释器模式、迭代器模式、中介者模式、备忘录模式、观察者模式、状态模式、策略模式、模板方法模式和访问者模式等。

各个设计模式解决什么问题#

简单工程模式#

简单工厂模式(Simple Factory Pattern)是一种创建型模式,它提供了一种创建对象的统一接口,可以根据不同的参数返回不同类的实例对象,而客户端无需了解这些具体的类。

简单工厂模式一般用于解决以下问题:

需要创建的对象较少:如果只需要创建少量的对象,使用简单工厂模式可以减少代码的复杂性。

客户端不需要知道创建的具体对象:简单工厂模式将创建对象的逻辑封装在工厂类中,客户端只需要调用工厂方法即可获得所需的对象,无需知道具体的创建过程。

代码复用:如果多个客户端需要创建相同的对象,使用简单工厂模式可以避免代码的重复。

需要注意的是,简单工厂模式只适用于创建对象较少的场景,如果需要创建的对象较多,则可以考虑使用工厂方法模式或抽象工厂模式。此外,简单工厂模式也有其缺点,例如增加新的对象类型需要修改工厂类的代码,违反了开闭原则,因此在设计时需要谨慎使用。

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

import "fmt"

type Product interface {
Show()
}

type ProductA struct{}

func (p *ProductA) Show() {
fmt.Println("Product A")
}

type ProductB struct{}

func (p *ProductB) Show() {
fmt.Println("Product B")
}

type Factory struct{}

func (f *Factory) CreateProduct(productType string) Product {
switch productType {
case "A":
return &ProductA{}
case "B":
return &ProductB{}
default:
return nil
}
}

func main() {
factory := &Factory{}

productA := factory.CreateProduct("A")
productA.Show()

productB := factory.CreateProduct("B")
productB.Show()
}

在上面的代码中,我们定义了 Product 接口和两个实现了该接口的具体产品 ProductAProductB。然后定义了 Factory 工厂类,其中的 CreateProduct 方法根据传入的参数返回不同的产品实例。最后在 main 函数中,我们使用工厂类创建了两个不同的产品并调用其 Show 方法展示出不同的效果。

工厂方法模式#

工厂方法模式(Factory Method Pattern)是一种创建型模式,它将对象的创建延迟到子类中来实现。工厂方法模式定义了一个用于创建对象的接口,让子类决定将哪一个类实例化。这样做的好处是将对象的创建和使用分离,客户端无需关心对象的创建细节,只需要关心如何使用对象即可。

工厂方法模式一般用于解决以下问题:

需要创建复杂对象:如果需要创建的对象比较复杂,需要进行一系列的初始化操作,使用工厂方法模式可以将这些初始化操作封装到具体的工厂子类中,让客户端更加简单地创建对象。

客户端不需要知道创建的具体对象:工厂方法模式将对象的创建封装在工厂子类中,客户端只需要通过工厂接口创建对象即可,无需知道具体的创建过程。

代码复用:如果多个客户端需要创建相同的对象,使用工厂方法模式可以避免代码的重复。

需要注意的是,工厂方法模式需要为每个产品定义一个具体的工厂子类,如果需要创建的产品很多,会导致类的数量增多,影响代码的可维护性,因此在使用时需要权衡设计的复杂度和代码的可维护性。同时,工厂方法模式也存在一定的开销,因为需要为每个产品定义一个工厂类,可能会导致类的数量增多,影响应用程序的性能。

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

import "fmt"

type Product interface {
Show()
}

type ProductA struct{}

func (p *ProductA) Show() {
fmt.Println("Product A")
}

type ProductB struct{}

func (p *ProductB) Show() {
fmt.Println("Product B")
}

type Factory interface {
CreateProduct() Product
}

type FactoryA struct{}

func (f *FactoryA) CreateProduct() Product {
return &ProductA{}
}

type FactoryB struct{}

func (f *FactoryB) CreateProduct() Product {
return &ProductB{}
}

func main() {
factoryA := &FactoryA{}
productA := factoryA.CreateProduct()
productA.Show()

factoryB := &FactoryB{}
productB := factoryB.CreateProduct()
productB.Show()
}

在上面的代码中,我们定义了 Product 接口和两个实现了该接口的具体产品 ProductAProductB。然后定义了 Factory 工厂接口和两个实现了该接口的具体工厂 FactoryAFactoryB,每个工厂实现了自己的 CreateProduct 方法,用于创建对应的产品实例。最后在 main 函数中,我们使用不同的工厂创建了不同的产品并调用其 Show 方法展示出不同的效果。

抽象工厂模式#

抽象工厂模式(Abstract Factory Pattern)是一种创建型模式,它提供了一种创建一系列相关或相互依赖对象的接口,而无需指定它们具体的类。

抽象工厂模式一般用于解决以下问题:

需要创建一系列相关或相互依赖的对象:如果需要创建的一系列对象具有相关性或者相互依赖,使用抽象工厂模式可以避免对象之间的耦合度过高。

系统需要独立于它的产品的创建、组合和表示:抽象工厂模式通过封装产品的创建过程,使得系统与具体产品的实现相分离,从而可以方便地替换产品系列,提高系统的灵活性和可维护性。

需要注意的是,抽象工厂模式一般适用于产品族(即相关联的产品组合)的创建,而不是单一产品的创建。此外,抽象工厂模式的缺点是扩展产品族比较困难,因为需要修改抽象工厂接口及其所有实现类,增加系统的复杂度和维护难度。

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

import "fmt"

// Abstract Product A
type Pizza interface {
Bake()
}

// Concrete Product A1
type CheesePizza struct{}

func (p *CheesePizza) Bake() {
fmt.Println("Baking a cheese pizza...")
}

// Concrete Product A2
type PepperoniPizza struct{}

func (p *PepperoniPizza) Bake() {
fmt.Println("Baking a pepperoni pizza...")
}

// Abstract Product B
type Beverage interface {
Prepare()
}

// Concrete Product B1
type Coke struct{}

func (b *Coke) Prepare() {
fmt.Println("Preparing a Coke...")
}

// Concrete Product B2
type Sprite struct{}

func (b *Sprite) Prepare() {
fmt.Println("Preparing a Sprite...")
}

// Abstract Factory
type PizzaAndBeverageFactory interface {
CreatePizza() Pizza
CreateBeverage() Beverage
}

// Concrete Factory 1
type PizzaAndCokeFactory struct{}

func (f *PizzaAndCokeFactory) CreatePizza() Pizza {
return &CheesePizza{}
}

func (f *PizzaAndCokeFactory) CreateBeverage() Beverage {
return &Coke{}
}

// Concrete Factory 2
type PizzaAndSpriteFactory struct{}

func (f *PizzaAndSpriteFactory) CreatePizza() Pizza {
return &PepperoniPizza{}
}

func (f *PizzaAndSpriteFactory) CreateBeverage() Beverage {
return &Sprite{}
}

func main() {
factory1 := &PizzaAndCokeFactory{}
pizza1 := factory1.CreatePizza()
beverage1 := factory1.CreateBeverage()
pizza1.Bake()
beverage1.Prepare()

factory2 := &PizzaAndSpriteFactory{}
pizza2 := factory2.CreatePizza()
beverage2 := factory2.CreateBeverage()
pizza2.Bake()
beverage2.Prepare()
}

在上面这个示例中,我们定义了两个产品族:PizzaBeveragePizza 产品族包含 CheesePizzaPepperoniPizza 两种产品,而 Beverage 产品族包含 CokeSprite 两种产品。

我们还定义了一个抽象工厂接口 PizzaAndBeverageFactory,其中包含两个方法 CreatePizza()CreateBeverage(),分别用于创建 PizzaBeverage 产品。

最后,我们定义了两个具体的工厂类 PizzaAndCokeFactoryPizzaAndSpriteFactory,它们分别实现了 PizzaAndBeverageFactory 接口,并实现了 CreatePizza()CreateBeverage() 方法,用于创建具体的产品。

main 函数中,我们首先使用 PizzaAndCokeFactory 工厂创建一个 CheesePizza 产品和一个 Coke 产品,然后使用 PizzaAndSpriteFactory 工厂创建一个 PepperoniPizza 产品和一个 Sprite 产品。最后,我们分别调用了这些产品的方法,输出了它们各自的信息。

需要注意的是,如果需要添加一种新的产品族(比如 Dessert 产品族),则需要新增一个新的抽象产品接口 Dessert,以及对应的具体产品类和抽象工厂接口及其实现类。这也是抽象工厂模式的一种缺陷,即扩展产品族比较困难,容易引起类层次结构的复杂度。

建造者模式#

建造者模式(Builder Pattern)主要解决的是对象的创建过程过于复杂而导致代码难以维护的问题。当需要创建一个包含多个组成部分的复杂对象时,如果直接在客户端代码中一步步创建每个部分并组装起来,将会导致代码冗长、可读性差、可维护性差等问题。

建造者模式通过将对象的构建过程抽象出来并将其封装在一个独立的 Builder 类中,使得客户端代码只需要关注需要创建的对象的类型和配置参数,而不需要关心其具体的构建过程。这样可以使得代码更加简洁、易于维护,同时也方便了对象的复用和扩展。

建造者模式通常涉及到以下几个角色:

产品(Product):需要被创建的复杂对象。

抽象建造者(Builder):定义了对象的构建过程,以及组装对象的方法。

具体建造者(ConcreteBuilder):实现了抽象建造者的接口,负责具体的对象构建和组装过程。

导演者(Director):负责组装各个部件,控制构建过程的顺序和逻辑,最终返回完整的对象。

下面是一个简单的 Golang 示例代码,用于创建一份汉堡套餐:

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
// 产品:汉堡套餐
type Meal struct {
Burger string
Fries bool
Drink string
}

// 抽象建造者:定义了对象的构建过程,以及组装对象的方法
type MealBuilder interface {
BuildBurger()
BuildFries()
BuildDrink()
GetMeal() Meal
}

// 具体建造者:实现了抽象建造者的接口,负责具体的对象构建和组装过程
type CheeseburgerMealBuilder struct {
meal Meal
}

func (b *CheeseburgerMealBuilder) BuildBurger() {
b.meal.Burger = "Cheeseburger"
}

func (b *CheeseburgerMealBuilder) BuildFries() {
b.meal.Fries = true
}

func (b *CheeseburgerMealBuilder) BuildDrink() {
b.meal.Drink = "Coke"
}

func (b *CheeseburgerMealBuilder) GetMeal() Meal {
return b.meal
}

// 导演者:负责组装各个部件,控制构建过程的顺序和逻辑,最终返回完整的对象
type Waiter struct {
builder MealBuilder
}

func (w *Waiter) SetBuilder(builder MealBuilder) {
w.builder = builder
}

func (w *Waiter) Construct() Meal {
w.builder.BuildBurger()
w.builder.BuildFries()
w.builder.BuildDrink()
return w.builder.GetMeal()
}

func main() {
builder := &CheeseburgerMealBuilder{}
waiter := &Waiter{}
waiter.SetBuilder(builder)
meal := waiter.Construct()
fmt.Println(meal)
}

在这个示例中,我们首先定义了一个产品 Meal,表示汉堡套餐,包含三个部分:Burger、Fries 和 Drink。然后定义了一个抽象建造者 MealBuilder,其中包含了三个方法 BuildBurger()、BuildFries() 和 BuildDrink(),用于构建不同部分的汉堡套餐,以及一个 GetMeal() 方法,用于返回最终构建完成的汉堡套餐。

接下来,我们定义了具体建造者 CheeseburgerMealBuilder,它实现了 MealBuilder 接口,并负责具体的对象构建和组装过程。在这个例子中,我们使用 CheeseburgerMealBuilder 来创建一份含有 Cheeseburger、Fries 和 Coke 的汉堡套餐。

最后,我们定义了一个导演者 Waiter,它持有一个 MealBuilder 对象,并负责组装各个部件,控制构建过程的顺序和逻辑,最终返回完整的对象。

在 main 函数中,我们首先创建了一个 CheeseburgerMealBuilder 对象和一个 Waiter 对象,然后将 CheeseburgerMealBuilder 对象传给 Waiter 对象。最后,我们通过调用 Waiter 对象的 Construct() 方法来构建汉堡套餐,并输出其内容。可以看到,通过建造者模式,我们可以将对象的构建过程抽象出来并将其与具体的对象实现分离开来,从而更加灵活地构建对象。这使得我们可以通过调整建造者的组装方式,来构建出不同的产品对象,而无需修改产品的具体实现。

原型模式#

原型模式是一种创建型设计模式,它允许通过复制现有对象来创建新对象,而无需向客户端暴露创建逻辑。它可以用于创建那些成本较高的对象,或者那些需要经过复杂计算才能得到的对象。

使用原型模式时,我们首先需要创建一个原型对象,它是我们要创建新对象的基础。然后,我们可以通过复制原型对象来创建新的对象,而不必重新创建这些对象。这个过程通常由一个原型管理器来控制,它维护了一个原型对象的注册表,客户端可以从中获取需要的原型对象,并通过复制来创建新的对象。

原型模式的主要优点是,它能够大幅度减少对象创建的开销,提高了对象创建的效率。同时,它也避免了客户端和创建逻辑之间的耦合,使得客户端无需关心对象的创建过程。此外,由于原型对象通常是通过复制来创建新对象的,因此可以保证新对象与原型对象具有相同的属性和行为。

下面是一个使用 Golang 实现的原型模式的示例代码:

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
// 原型接口:定义了复制自身的方法
type Prototype interface {
Clone() Prototype
}

// 具体原型:实现了原型接口,可以复制自身来创建新对象
type ConcretePrototype struct {
Name string
Age int
}

func (p *ConcretePrototype) Clone() Prototype {
return &ConcretePrototype{
Name: p.Name,
Age: p.Age,
}
}

// 原型管理器:维护了一个原型对象的注册表,客户端可以从中获取需要的原型对象,并通过复制来创建新的对象
type PrototypeManager struct {
prototypes map[string]Prototype
}

func (m *PrototypeManager) Register(name string, prototype Prototype) {
if m.prototypes == nil {
m.prototypes = make(map[string]Prototype)
}
m.prototypes[name] = prototype
}

func (m *PrototypeManager) Unregister(name string) {
delete(m.prototypes, name)
}

func (m *PrototypeManager) Get(name string) Prototype {
return m.prototypes[name].Clone()
}

func main() {
// 创建原型管理器并注册原型对象
manager := &PrototypeManager{}
prototype := &ConcretePrototype{
Name: "Alice",
Age: 20,
}
manager.Register("prototype", prototype)

// 通过原型管理器获取原型对象,并通过复制来创建新对象
clone := manager.Get("prototype")
fmt.Println(clone)
}

在这个示例中,我们首先定义了一个原型接口 Prototype,它包含了一个 Clone() 方法,用于复制自身来创建新对象。然后,我们定义了一个具体原型 ConcretePrototype,它实现了 Prototype 接口,并可以复制自身来创建新对象。

接下来,我们定义了一个原型管理器 PrototypeManager,它维护了一个原型对象的注册表,客户端可以从中获取需要的原型对象,并通过复制来创建新的对象。其中,Register() 方法用于注册原型对象,Unregister() 方法用于注销原型对象,Get() 方法用于获取原型对象。

在 main() 函数中,我们首先创建了一个原型管理器 manager,并注册了一个原型对象 prototype。然后,我们通过原型管理器获取原型对象,并通过复制来创建新对象,最后输出了新对象的属性值。

总的来说,原型模式主要解决的是创建成本高、创建过程复杂的对象的问题,通过复制现有对象来创建新对象,可以大幅度减少对象创建的开销,提高对象创建的效率,同时也避免了客户端和创建逻辑之间的耦合。

单例模式#

单例模式主要解决的是在系统中保证一个类只有一个实例,并且提供全局访问点,让其他对象可以通过该实例来访问该类的功能的问题。使用单例模式可以避免系统中出现多个相同的实例,减少系统内存占用和资源消耗,同时也方便了对实例的控制和管理。

在单例模式中,一般有两种方式来实现单例:

饿汉式单例:在类加载时就创建单例实例,并提供全局访问点,保证了单例的唯一性和全局可访问性。

懒汉式单例:在第一次调用时才创建单例实例,并提供全局访问点,同时需要处理多线程环境下的并发访问问题,保证了单例的唯一性和全局可访问性。

在实际开发中,单例模式常用于工具类、配置类、日志类、缓存类等。

当涉及到单例模式时,golang 的实现方式与其他面向对象语言有所不同,因为 golang 中没有类的概念,因此也没有类的静态成员变量和构造函数。但是,golang 中的包级别变量和初始化函数可以被用来实现饿汉式单例和懒汉式单例。

下面分别给出饿汉式单例和懒汉式单例的 golang 实现示例代码:

饿汉式单例:

1
2
3
4
5
6
7
8
9
10
11
package singleton

type Singleton struct {
// 定义一些属性
}

var instance *Singleton = &Singleton{ /* 初始化属性 */ }

func GetInstance() *Singleton {
return instance
}

在上面的代码中,我们首先定义了一个 Singleton 结构体,并在全局范围内创建了一个名为 instance 的包级别变量,该变量在定义时就已经进行了初始化。我们还定义了一个名为 GetInstance 的函数,用于获取 instance 变量的值。由于 instance 变量在定义时就已经进行了初始化,因此可以保证 GetInstance 函数始终返回同一个 Singleton 实例。

懒汉式单例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package singleton

import "sync"

type Singleton struct {
// 定义一些属性
}

var instance *Singleton
var once sync.Once

func GetInstance() *Singleton {
once.Do(func() {
instance = &Singleton{ /* 初始化属性 */ }
})
return instance
}

在上面的代码中,我们定义了一个 Singleton 结构体,并在全局范围内创建了一个名为 instance 的包级别变量。我们还定义了一个名为 GetInstance 的函数,用于获取 instance 变量的值。由于 instance 变量没有在定义时进行初始化,因此在第一次调用 GetInstance 函数时,会执行 once.Do 方法中的代码块,创建一个新的 Singleton 实例并赋值给 instance 变量。由于 once.Do 方法只会执行一次,因此可以保证 GetInstance 函数始终返回同一个 Singleton 实例。此外,我们还使用了 sync 包中的 Once 类型来保证在多线程环境下的并发访问问题。

适配器模式#

适配器模式(Adapter Pattern)主要是为了解决两个已有接口之间的兼容性问题而提出的。

在实际开发中,我们常常需要使用一些已有的类或者组件,但是这些已有的类或组件可能不符合我们当前的需求。如果我们需要使用这些类或组件中的某些方法或功能,但是它们的接口与我们当前的需求不兼容,那么我们可以使用适配器模式来解决这个问题。

适配器模式定义了一个适配器类,这个类实现了我们需要的目标接口,并且持有一个已有接口的引用,在适配器类中实现目标接口的方法时,通过调用已有接口的方法来实现目标接口的功能,从而让已有接口能够被我们的应用程序所使用。

使用适配器模式可以有效地解决两个不兼容接口之间的兼容性问题,使得我们的应用程序能够更加灵活地使用已有的类或组件,同时又不需要修改已有的类或组件的代码。适配器模式可以降低代码的耦合度,提高代码的可维护性和可复用性。

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
// Target 是目标接口,定义了目标接口的方法
type Target interface {
Request() string
}

// Adaptee 是已有接口,其方法与目标接口的方法不兼容
type Adaptee struct {
Data string
}

// SpecificRequest 是已有接口中的一个方法
func (a *Adaptee) SpecificRequest() string {
return a.Data
}

// Adapter 是适配器,实现了目标接口并持有已有接口的引用
type Adapter struct {
adaptee *Adaptee
}

// NewAdapter 是适配器的构造函数
func NewAdapter(adaptee *Adaptee) Target {
return &Adapter{adaptee: adaptee}
}

// Request 是目标接口的实现,通过调用已有接口的方法来实现目标接口的功能
func (a *Adapter) Request() string {
return "Adapter: " + a.adaptee.SpecificRequest()
}

func main() {
// 创建一个已有接口的实例
adaptee := &Adaptee{Data: "Adaptee"}

// 创建一个适配器的实例,将已有接口的实例作为参数传入
target := NewAdapter(adaptee)

// 调用目标接口的方法,实际上是通过已有接口的方法实现的
fmt.Println(target.Request())
}

在上面的代码中,我们定义了一个 Target 接口,其中定义了目标接口的方法 Request()。接着,我们定义了一个 Adaptee 结构体,其中的 SpecificRequest() 方法与目标接口的方法不兼容。

为了实现适配器模式,我们创建了一个 Adapter 结构体,并实现了目标接口的方法 Request(),在 Request() 方法中通过调用已有接口的方法 SpecificRequest() 来实现目标接口的功能。在 Adapter 的构造函数 NewAdapter() 中,我们传入已有接口的实例,创建一个适配器的实例并返回。

在 main() 函数中,我们创建了一个已有接口的实例 adaptee,并将其作为参数传入 NewAdapter() 函数中,创建一个适配器的实例 target。接着,我们调用目标接口的方法 Request(),实际上是通过已有接口的方法 SpecificRequest() 来实现的。

桥接模式#

桥接模式主要是为了解决在多维度变化中,如何有效地组合不同维度上的变化,而又不至于使得类的数量急剧增加的问题。当一个类有多个变化维度时,如果采用传统的继承方式,就需要定义多个子类来处理各种变化的组合,这样会导致类的数量急剧增加,给系统带来很大的复杂度和维护成本。

桥接模式的解决思路是将一个类的多个维度上的变化分离出来,使它们可以独立地变化,然后再通过组合的方式将它们组合起来,从而减少类的数量。这种思路和“组合优于继承”的设计原则是一致的。

桥接模式将类的一个维度上的变化抽象为一个接口,称为“实现类接口”,然后在该维度上定义一个“抽象类”,它包含一个指向实现类接口的引用,通过这个引用可以调用实现类的方法。在另一个维度上定义一个“具体类”,它继承自抽象类,并实现了抽象类中的方法,从而完成对另一个维度上的变化的支持。这样,我们就可以通过组合的方式将多个维度上的变化组合起来,而又不需要定义大量的子类。

桥接模式的优点是可以有效地将多个维度上的变化分离出来,使得系统更加灵活,同时也减少了类的数量,提高了系统的可维护性和可扩展性。其缺点是需要设计和实现更多的类和接口,增加了系统的复杂度。

总之,桥接模式主要是为了解决在多维度变化中,如何有效地组合不同维度上的变化,而又不至于使得类的数量急剧增加的问题。

当一个类有多个变化维度时,可以使用桥接模式进行设计。下面是一个使用Golang实现的桥接模式示例:

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

import "fmt"

// 实现类接口
type implementor interface {
operationImp() string
}

// 具体实现类A
type concreteImplementorA struct{}

func (*concreteImplementorA) operationImp() string {
return "ConcreteImplementorA"
}

// 具体实现类B
type concreteImplementorB struct{}

func (*concreteImplementorB) operationImp() string {
return "ConcreteImplementorB"
}

// 抽象类
type abstractClass struct {
implementor implementor
}

func (ac *abstractClass) operation() string {
return "AbstractClass: " + ac.implementor.operationImp()
}

// 客户端代码
func main() {
// 使用实现类A
implementorA := &concreteImplementorA{}
abstractClassA := &abstractClass{
implementor: implementorA,
}
fmt.Println(abstractClassA.operation())

// 使用实现类B
implementorB := &concreteImplementorB{}
abstractClassB := &abstractClass{
implementor: implementorB,
}
fmt.Println(abstractClassB.operation())
}

在上述示例中,implementor接口定义了实现类需要实现的方法operationImp(),具体实现类concreteImplementorA和concreteImplementorB分别实现了该接口的方法。抽象类abstractClass包含一个指向implementor接口的引用,通过这个引用可以调用实现类的方法。在客户端代码中,我们通过组合的方式将具体实现类和抽象类组合起来,从而实现多个维度上的变化组合。

组合模式#

组合模式主要解决的是对象结构的设计问题。当我们需要处理具有层次结构的对象,而且对于这些对象的处理需要一致时,可以使用组合模式。

组合模式可以使客户端对单个对象和组合对象的使用具有一致性,这也是它的优势所在。同时,组合模式也具有灵活性,因为可以通过简单的添加和删除节点来改变组合结构。

举个例子,比如我们需要处理一个组织机构,这个机构包含多个部门,而每个部门又可以包含多个员工,而且我们需要对这些员工进行统一的管理和处理。这种情况下,我们就可以使用组合模式,通过将部门和员工组合起来,从而实现对整个组织机构的管理和处理。

当我们使用组合模式时,通常会定义一个抽象组件(Component)类和一个具体组件类(Leaf),还有一个组合类(Composite)。下面是一个使用golang实现组合模式的代码示例:

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

import "fmt"

// 抽象组件
type Component interface {
GetName() string
Print()
}

// 具体组件
type Leaf struct {
name string
}

func NewLeaf(name string) *Leaf {
return &Leaf{name: name}
}

func (l *Leaf) GetName() string {
return l.name
}

func (l *Leaf) Print() {
fmt.Println(l.name)
}

// 组合类
type Composite struct {
name string
children []Component
}

func NewComposite(name string) *Composite {
return &Composite{name: name}
}

func (c *Composite) Add(component Component) {
c.children = append(c.children, component)
}

func (c *Composite) Remove(component Component) {
for i, child := range c.children {
if child == component {
c.children = append(c.children[:i], c.children[i+1:]...)
break
}
}
}

func (c *Composite) GetName() string {
return c.name
}

func (c *Composite) Print() {
fmt.Println(c.name)
for _, child := range c.children {
fmt.Print(" ")
child.Print()
}
}

func main() {
root := NewComposite("root")
root.Add(NewLeaf("leaf1"))
root.Add(NewLeaf("leaf2"))

composite := NewComposite("composite")
composite.Add(NewLeaf("leaf3"))
composite.Add(NewLeaf("leaf4"))
root.Add(composite)

root.Print()
}

在上面的例子中,Component是一个抽象组件,它定义了两个方法:GetName()和Print()。Leaf是具体组件类,它实现了Component接口中的方法。Composite是组合类,它包含一个名称和一个子组件的列表。Composite也实现了Component接口中的方法,并且可以通过Add()和Remove()方法来添加或删除子组件。在main()函数中,我们创建了一个根组合对象,添加了两个叶子节点和一个组合节点,并通过Print()方法来打印整个组合对象。

装饰器模式#

装饰器模式主要解决以下两个问题:

1.动态地给一个对象添加一些额外的职责,而不会影响到其他对象。
2.避免使用继承的方式扩展对象的功能,因为继承会造成子类数量的爆炸,使得代码变得难以维护。
装饰器模式可以在运行时动态地为对象添加职责,通过包装一个已有的对象,来扩展其功能,而不是通过继承的方式。这样可以避免对原有代码的修改,并且可以灵活地组合各种功能。同时,由于装饰器模式是通过对象组合的方式来实现功能的扩展,因此可以避免类的继承关系过于复杂的问题。

当我们需要对一个对象进行功能扩展时,可以使用装饰器模式。以下是一个使用 Golang 实现装饰器模式的示例代码:

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
// 定义组件接口
type Component interface {
Operation() string
}

// 具体组件
type ConcreteComponent struct {}

func (c *ConcreteComponent) Operation() string {
return "ConcreteComponent"
}

// 装饰器抽象类
type Decorator struct {
component Component
}

func (d *Decorator) Operation() string {
return d.component.Operation()
}

// 具体装饰器类A
type ConcreteDecoratorA struct {
Decorator
}

func (d *ConcreteDecoratorA) Operation() string {
return "ConcreteDecoratorA(" + d.component.Operation() + ")"
}

// 具体装饰器类B
type ConcreteDecoratorB struct {
Decorator
}

func (d *ConcreteDecoratorB) Operation() string {
return "ConcreteDecoratorB(" + d.component.Operation() + ")"
}

func main() {
// 创建一个具体组件
c := &ConcreteComponent{}

// 使用具体组件来创建装饰器
d1 := &ConcreteDecoratorA{Decorator{c}}
d2 := &ConcreteDecoratorB{Decorator{d1}}

// 调用具体装饰器的操作方法
fmt.Println(d2.Operation()) // 输出:ConcreteDecoratorB(ConcreteDecoratorA(ConcreteComponent))
}

在上面的代码中,我们首先定义了一个 Component 接口和一个具体实现 ConcreteComponent。然后定义了一个 Decorator 抽象类,该类实现了 Component 接口,并且维护了一个 Component 对象。接着我们定义了两个具体的装饰器类 ConcreteDecoratorA 和 ConcreteDecoratorB,它们都继承自 Decorator,并且在实现 Operation() 方法时,先调用 component.Operation(),然后在其返回值前后添加一些修饰语。

最后,我们使用具体组件来创建一个装饰器 d1,然后使用 d1 再创建一个装饰器 d2。调用 d2.Operation() 方法时,会依次执行 ConcreteDecoratorB 和 ConcreteDecoratorA 的 Operation() 方法,最终输出带有修饰语的结果。这就是装饰器模式的运行方式。

外观模式#

外观模式(Facade Pattern)主要解决的问题是将复杂的系统或子系统进行封装,提供一个简单的接口或入口供客户端使用,从而简化客户端与系统之间的交互,降低系统间的耦合度。

举个例子,比如一个电脑系统,它由多个子系统组成,如CPU、内存、硬盘、显卡等等。如果每次使用电脑时,都需要直接与这些子系统进行交互,那么操作起来就会非常繁琐。而外观模式可以提供一个简单的接口,例如开机、关机、运行软件等,这样客户端就不需要直接与各个子系统打交道了,只需要通过这些简单的接口进行操作即可。

外观模式可以降低客户端的复杂度和使用难度,也可以方便地对系统进行修改和扩展,同时也可以提高系统的安全性和可靠性。

当我们需要对外提供一个简单的接口,来隐藏系统复杂的内部结构时,可以使用外观模式。下面是一个使用golang实现的外观模式示例:

首先定义一个外观类(facade),它封装了复杂系统的各个子系统,并提供了一个简单的接口给客户端使用:

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
// Facade 外观类,封装了各个子系统,提供简单的接口给客户端使用
type Facade struct {
subsystem1 *Subsystem1
subsystem2 *Subsystem2
subsystem3 *Subsystem3
}

// NewFacade 创建一个新的外观类实例
func NewFacade() *Facade {
return &Facade{
subsystem1: NewSubsystem1(),
subsystem2: NewSubsystem2(),
subsystem3: NewSubsystem3(),
}
}

// Operation 统一的操作接口,供客户端使用
func (f *Facade) Operation() {
fmt.Println("Facade operation")
f.subsystem1.Operation1()
f.subsystem2.Operation2()
f.subsystem3.Operation3()
}

// Subsystem1 子系统1
type Subsystem1 struct{}

// NewSubsystem1 创建一个新的子系统1实例
func NewSubsystem1() *Subsystem1 {
return &Subsystem1{}
}

// Operation1 子系统1的操作
func (*Subsystem1) Operation1() {
fmt.Println("Subsystem1 operation")
}

// Subsystem2 子系统2
type Subsystem2 struct{}

// NewSubsystem2 创建一个新的子系统2实例
func NewSubsystem2() *Subsystem2 {
return &Subsystem2{}
}

// Operation2 子系统2的操作
func (*Subsystem2) Operation2() {
fmt.Println("Subsystem2 operation")
}

// Subsystem3 子系统3
type Subsystem3 struct{}

// NewSubsystem3 创建一个新的子系统3实例
func NewSubsystem3() *Subsystem3 {
return &Subsystem3{}
}

// Operation3 子系统3的操作
func (*Subsystem3) Operation3() {
fmt.Println("Subsystem3 operation")
}

func main() {
facade := NewFacade()
facade.Operation()
}

//Facade operation
//Subsystem1 operation
//Subsystem2 operation
//Subsystem3 operation

从输出结果可以看到,虽然客户端只调用了外观类的一个方法,但实际上内部封装了三个子系统的操作,并成功地输出了子系统的操作结果。这就是外观模式的作用,将系统的复杂度隐藏起来,提供一个简单的接口给客户端使用。

享元模式#

享元模式主要解决大量细粒度对象的共享问题,以减少内存的消耗。

在软件系统中,有时需要创建大量的对象,如果每个对象都包含相同或相似的状态信息,那么对象的内存消耗将会很大。享元模式通过共享这些相同或相似的状态信息来减少对象的数量,从而降低了内存的消耗。

通常情况下,享元模式将一个对象的状态分为内部状态和外部状态,内部状态是可以共享的,而外部状态是不可以共享的。通过共享内部状态,让系统中相同或相似的对象共享一个对象,从而减少了对象的数量。

例如,一个文本编辑器可能需要创建大量的字符对象,每个字符对象都包含字符的字体、颜色等属性信息,这些属性信息属于内部状态,可以共享。而每个字符对象在文本中的位置信息属于外部状态,不能共享。通过享元模式,可以将相同字体和颜色的字符对象共享一个对象,从而减少对象的数量。

另外,享元模式也可以用于缓存池、线程池等资源池的实现,以提高资源利用率和系统性能。

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
// UserLoginInfo 用户登录信息
type UserLoginInfo struct {
username string
password string
lastLoginTime time.Time
}

// UserLoginInfoFactory 用户登录信息工厂
type UserLoginInfoFactory struct {
loginInfos map[string]*UserLoginInfo
}

// NewUserLoginInfoFactory 创建用户登录信息工厂
func NewUserLoginInfoFactory() *UserLoginInfoFactory {
return &UserLoginInfoFactory{
loginInfos: make(map[string]*UserLoginInfo),
}
}

// GetLoginInfo 获取用户登录信息
func (f *UserLoginInfoFactory) GetLoginInfo(username, password string) *UserLoginInfo {
key := fmt.Sprintf("%s:%s", username, password)
if info, ok := f.loginInfos[key]; ok {
return info
}
info := &UserLoginInfo{
username: username,
password: password,
lastLoginTime: time.Now(),
}
f.loginInfos[key] = info
return info
}

在这个例子中,UserLoginInfo 表示一个用户的登录信息,其中 username 和 password 是内部状态,可以共享,而 lastLoginTime 是外部状态,不能共享。

UserLoginInfoFactory 表示用户登录信息的工厂,用于管理登录信息对象的创建和共享。当需要获取一个用户登录信息时,先根据 username 和 password 生成一个唯一的 key,如果这个 key 对应的登录信息已经存在,则直接返回,否则创建一个新的登录信息对象,并将其加入到 loginInfos 中,以便后续使用。

代理模式#

代理模式主要解决两类问题:

1.对象访问的控制:代理模式可以在代理对象和实际对象之间加入一些控制逻辑,限制对实际对象的直接访问,从而实现对对象访问的控制。

2.远程对象的访问:代理模式可以在代理对象和远程对象之间建立一个代理,使得本地对象可以通过代理访问远程对象,从而实现远程方法调用。

举个例子,假设我们有一个需要控制访问权限的文件系统,可以使用代理模式来实现对文件的访问控制。具体代码实现可以参考下面的示例:

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
// FileSystem 文件系统接口
type FileSystem interface {
ReadFile(filename string) (string, error)
WriteFile(filename, content string) error
}

// FileSystemImpl 文件系统实现
type FileSystemImpl struct {}

func (fs *FileSystemImpl) ReadFile(filename string) (string, error) {
// 读取文件
}

func (fs *FileSystemImpl) WriteFile(filename, content string) error {
// 写入文件
}

// FileSystemProxy 文件系统代理
type FileSystemProxy struct {
fs FileSystem
user string
}

func NewFileSystemProxy(fs FileSystem, user string) *FileSystemProxy {
return &FileSystemProxy{fs: fs, user: user}
}

func (p *FileSystemProxy) ReadFile(filename string) (string, error) {
if p.user != "admin" {
return "", errors.New("you don't have permission to read file")
}
return p.fs.ReadFile(filename)
}

func (p *FileSystemProxy) WriteFile(filename, content string) error {
if p.user != "admin" {
return errors.New("you don't have permission to write file")
}
return p.fs.WriteFile(filename, content)
}

在这个例子中,FileSystem 表示文件系统接口,FileSystemImpl 是文件系统的实现。FileSystemProxy 是文件系统的代理,用于实现对文件访问的控制。代理对象接收到请求后,先进行权限检查,只有具有管理员权限的用户才能执行读取或写入文件的操作。如果检查通过,则将请求转发给实际的文件系统对象进行处理。这样就实现了对文件访问的控制。

Golang实现经典数据结构

avl树#

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
144
145
146
147
148
149
150
package main

import "fmt"

type Node struct {
key, height int
left, right *Node
}

func height(node *Node) int {
if node == nil {
return -1
}
return node.height
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func rotateLeft(node *Node) *Node {
rightChild := node.right
node.right = rightChild.left
rightChild.left = node
node.height = max(height(node.left), height(node.right)) + 1
rightChild.height = max(height(rightChild.left), height(rightChild.right)) + 1
return rightChild
}

func rotateRight(node *Node) *Node {
leftChild := node.left
node.left = leftChild.right
leftChild.right = node
node.height = max(height(node.left), height(node.right)) + 1
leftChild.height = max(height(leftChild.left), height(leftChild.right)) + 1
return leftChild
}

func rotateLeftRight(node *Node) *Node {
node.left = rotateLeft(node.left)
return rotateRight(node)
}

func rotateRightLeft(node *Node) *Node {
node.right = rotateRight(node.right)
return rotateLeft(node)
}

func balance(node *Node) *Node {
if height(node.left)-height(node.right) > 1 {
if height(node.left.left) >= height(node.left.right) {
node = rotateRight(node)
} else {
node = rotateLeftRight(node)
}
} else if height(node.right)-height(node.left) > 1 {
if height(node.right.right) >= height(node.right.left) {
node = rotateLeft(node)
} else {
node = rotateRightLeft(node)
}
}
node.height = max(height(node.left), height(node.right)) + 1
return node
}

func put(node *Node, key int) *Node {
if node == nil {
return &Node{key: key, height: 0}
}
if key < node.key {
node.left = put(node.left, key)
} else if key > node.key {
node.right = put(node.right, key)
} else {
return node // key already exists
}
return balance(node)
}

func findMin(node *Node) *Node {
if node == nil {
return nil
}
for node.left != nil {
node = node.left
}
return node
}

func deleteMin(node *Node) *Node {
if node.left == nil {
return node.right
}
node.left = deleteMin(node.left)
return balance(node)
}

func delete(node *Node, key int) *Node {
if node == nil {
return nil
}
if key < node.key {
node.left = delete(node.left, key)
} else if key > node.key {
node.right = delete(node.right, key)
} else {
if node.left == nil {
return node.right
} else if node.right == nil {
return node.left
} else {
successor := findMin(node.right)
node.key = successor.key
node.right = deleteMin(node.right)
}
}
return balance(node)
}

func find(node *Node, key int) *Node {
if node == nil {
return nil
}
if key < node.key {
return find(node.left, key)
} else if key > node.key {
return find(node.right, key)
} else {
return node
}
}

func main() {
var root *Node
root = put(root, 10)
root = put(root, 20)
root = put(root, 30)
root = put(root, 40)
root = put(root, 50)
root = delete(root, 30)
fmt.Println(find(root, 10))
fmt.Println(find(root, 20))
fmt.Println(find(root, 30))
fmt.Println(find(root, 40))
fmt.Println(find(root, 50))
}

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
import (
"container/list"
"sync"
)

type LRUCache struct {
capacity int
cache map[int]*list.Element
list *list.List
mutex sync.Mutex
}

type CacheItem struct {
key int
value int
}

func Constructor(capacity int) LRUCache {
return LRUCache{
capacity: capacity,
cache: make(map[int]*list.Element),
list: list.New(),
}
}

func (this *LRUCache) Get(key int) int {
this.mutex.Lock()
defer this.mutex.Unlock()

if ele, ok := this.cache[key]; ok {
this.list.MoveToFront(ele)
return ele.Value.(*CacheItem).value
}
return -1
}

func (this *LRUCache) Put(key int, value int) {
this.mutex.Lock()
defer this.mutex.Unlock()

if ele, ok := this.cache[key]; ok {
this.list.MoveToFront(ele)
ele.Value.(*CacheItem).value = value
} else {
ele := this.list.PushFront(&CacheItem{key, value})
this.cache[key] = ele
if len(this.cache) > this.capacity {
ele := this.list.Back()
this.list.Remove(ele)
delete(this.cache, ele.Value.(*CacheItem).key)
}
}
}

红黑树#

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

import "fmt"

const (
red = true
black = false
)

type RBTree struct {
root *Node
}

type Node struct {
key, value int
color bool
left, right *Node
}

func (t *RBTree) put(key, value int) {
t.root = t.root.put(key, value)
t.root.color = black
}

func (n *Node) put(key, value int) *Node {
if n == nil {
return &Node{key: key, value: value, color: red}
}
if key < n.key {
n.left = n.left.put(key, value)
} else if key > n.key {
n.right = n.right.put(key, value)
} else {
n.value = value
}
if n.right.isRed() && !n.left.isRed() {
n = n.rotateLeft()
}
if n.left.isRed() && n.left.left.isRed() {
n = n.rotateRight()
}
if n.left.isRed() && n.right.isRed() {
n.flipColors()
}
return n
}

func (t *RBTree) get(key int) (int, bool) {
n := t.root
for n != nil {
if key < n.key {
n = n.left
} else if key > n.key {
n = n.right
} else {
return n.value, true
}
}
return 0, false
}

func (n *Node) isRed() bool {
if n == nil {
return false
}
return n.color == red
}

func (n *Node) rotateLeft() *Node {
x := n.right
n.right = x.left
x.left = n
x.color = n.color
n.color = red
return x
}

func (n *Node) rotateRight() *Node {
x := n.left
n.left = x.right
x.right = n
x.color = n.color
n.color = red
return x
}

func (n *Node) flipColors() {
n.color = red
n.left.color = black
n.right.color = black
}

func main() {
tree := &RBTree{}
tree.put(3, 3)
tree.put(2, 2)
tree.put(1, 1)
fmt.Println(tree.get(1))
fmt.Println(tree.get(2))
fmt.Println(tree.get(3))
}

Zookeeper常用指南

ZK简介#

Zookeeper是一个分布式的开源协调服务,可以用于在分布式系统中管理和协调大规模的计算机集群。它提供了一个简单的文件系统接口,可以用于协调分布式应用程序的各个组件,如配置管理、命名服务、集群管理等。

Zookeeper的主要特点是可靠性、高性能、可扩展性和简单性。它通过ZAB协议实现分布式一致性,可以保证在分布式系统中各个节点之间的数据一致性。Zookeeper还可以通过扩展机制来支持自定义协议和功能,使其具有更广泛的适用性。

zkCli#

  1. ls:列出指定路径下的子节点列表,命令格式为ls path。
  2. create:创建一个新的znode节点,命令格式为create [-s] path data。其中,-s参数表示创建一个序列化的节点。
  3. delete:删除指定的znode节点,命令格式为delete path [version]。version表示指定删除哪个版本的节点,如果不指定则删除最新版本。
  4. get:获取指定节点的数据内容,命令格式为get path。
  5. set:设置指定节点的数据内容,命令格式为set path data [version]。其中,version表示指定修改哪个版本的节点,如果不指定则修改最新版本。
  6. stat:获取指定节点的元数据信息,命令格式为stat path。
  7. help:显示帮助信息,命令格式为help [cmd]。如果指定了cmd,则显示cmd命令的详细使用说明。

Golang GMP简介

当我们需要处理大规模数据并发任务时,Golang 是一个不错的选择。Golang 在标准库中提供了一种称为 GMP(Goroutine、Channel、Mutex、Package)的并发编程模型,是 Golang 强大的并发编程能力的核心。本文将为您介绍 Golang 中的 GMP 并发编程模型。

Goroutine#

Goroutine 是 Golang 中的轻量级线程,由 Go 运行时(Go runtime)管理。Goroutine 能够并发执行,通过 go 关键字来创建。Goroutine 的启动和销毁开销很小,可以轻松地创建大量的 Goroutine。

以下是一个使用 Goroutine 的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package main

import (
"fmt"
"time"
)

func say(s string) {
for i := 0; i < 5; i++ {
time.Sleep(100 * time.Millisecond)
fmt.Println(s)
}
}

func main() {
go say("world")
say("hello")
}

在上面的例子中,我们创建了两个 Goroutine:say("world")say("hello")。它们会同时运行,打印出 “hello” 和 “world”,直到 say("hello") 执行完毕。

Channel#

Channel 是 Golang 中用于 Goroutine 之间通信的机制。Channel 可以被用来在 Goroutine 之间传递数据,避免了竞态条件和锁的使用。

以下是一个使用 Channel 的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

import "fmt"

func sum(s []int, c chan int) {
sum := 0
for _, v := range s {
sum += v
}
c <- sum
}

func main() {
s := []int{7, 2, 8, -9, 4, 0}
c := make(chan int)
go sum(s[:len(s)/2], c)
go sum(s[len(s)/2:], c)
x, y := <-c, <-c
fmt.Println(x, y, x+y)
}

在上面的例子中,我们创建了两个 Goroutine:sum(s[:len(s)/2], c)sum(s[len(s)/2:], c)。它们会同时运行,将数组的一半加起来,并将结果传递到 Channel 中。在主函数中,我们通过 <-c 从 Channel 中获取结果,并将两个结果相加。

Mutex#

Mutex 是 Golang 中用于多个 Goroutine 访问共享资源的机制。Mutex 可以确保同一时间只有一个 Goroutine 能够访问共享资源。

以下是一个使用 Mutex 的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import (
"fmt"
"sync"
)

var (
sum int
mutex sync.Mutex
)

func add(i int) {
mutex.Lock()
sum += i
mutex.Unlock()
}

func main() {
for i := 0; i < 1000; i++ {
go add(i)
}
fmt.Println(sum)
}

在上面的例子中,我们创建了 1000 个 Goroutine,每个 Goroutine 都会将一个数加到 sum 中。为了确保多个 Goroutine 不会同时访问 sum,我们使用 Mutex 来锁定 sum,以确保同一时间只有一个 Goroutine 能够访问 sum

Package#

Package 是 Golang 中用于组织代码的机制。Golang 的标准库提供了大量的 Package,例如 io、net、http 等。我们也可以自己编写 Package 来组织自己的代码。

以下是一个自定义 Package 的例子:

1
2
3
4
5
6
// greeting/greeting.go
package greeting

func Greet(name string) string {
return "Hello, " + name + "!"
}

在上面的例子中,我们创建了一个名为 greeting 的 Package,其中包含一个 Greet 函数,用于返回问候语。

1
2
3
4
5
6
7
8
9
// main.go
package main

import "fmt"
import "greeting"

func main() {
fmt.Println(greeting.Greet("world"))
}

在主函数中,我们导入 greeting Package,并使用 Greet 函数打印问候语。

通过 GMP 模型,Golang 提供了强大的并发编程能力,使得开发者能够轻松地处理大规模数据并发任务。当然,为了正确使用 GMP,开发者需要深入了解它们的实现细节。

hexo使用指南

Hexo 日常使用指南#

简介#

Hexo 是一个快速、简洁且高效的基于 Node.js 的静态博客框架,使用 Hexo,您可以使用 Markdown 等轻量级语言来撰写博客文章,并将其转换为静态页面进行展示,而不需要像传统博客系统那样依赖于数据库和服务器。Hexo 具有快速、简洁、高效等特点,非常适合个人博客、技术博客和文学博客等多种用途。

安装 Hexo#

要使用 Hexo,您需要先安装 Node.js 和 Git,然后使用 npm(Node.js 包管理器)来安装 Hexo。以下是安装步骤:

  1. 安装 Node.js:在 Node.js 官方网站下载并安装 Node.js。

  2. 安装 Git:在 Git 官方网站下载并安装 Git。

  3. 安装 Hexo:在命令行中执行以下命令安装 Hexo:

    1
    $ npm install hexo-cli -g
  4. 初始化 Hexo:在命令行中执行以下命令初始化 Hexo:

    1
    2
    3
    $ hexo init blog
    $ cd blog
    $ npm install

创建文章#

使用 Hexo 创建文章非常简单,只需要在命令行中执行以下命令:

1
$ hexo new "Hello World"

其中,”Hello World” 是文章的标题,Hexo 会自动生成一个 Markdown 文件,保存在 source/_posts 目录下。您可以使用 Markdown 语法来撰写文章。

生成静态文件#

使用 Hexo 生成静态文件非常简单,只需要在命令行中执行以下命令:

1
$ hexo generate

Hexo 会根据您的配置文件和主题模板生成静态文件,保存在 public 目录下。

启动本地服务器#

使用 Hexo 启动本地服务器非常简单,只需要在命令行中执行以下命令:

1
$ hexo server

然后在浏览器中访问 http://localhost:4000/ 即可查看博客。

部署博客#

使用 Hexo 部署博客非常简单,只需要在命令行中执行以下命令:

1
$ hexo deploy

然后 Hexo 会将静态文件部署到您指定的远程服务器或云平台。在部署前,您需要先配置 _config.yml 文件中的 deploy 部分。

清除缓存#

在 Hexo 使用过程中,可能会产生一些缓存文件和已生成的静态文件。如果您想要清除这些文件,可以在命令行中执行以下命令:

1
$ hexo clean

安装主题#

Hexo 支持丰富的主题和插件,您可以根据自己的需求来选择和安装。以下是安装主题的步骤:

  1. 在 Hexo 官方主题库中选择并下载主题。

  2. 将主题解压缩到 themes 目录下。

  3. 修改配置文件 _config.yml 中的 theme 字段为您所安装的主题名称。

  4. 在命令行中执行以下命令重新生成静态文件:

    1
    $ hexo generate

使用插件#

Hexo 支持丰富的插件,可以帮助您更好地管理博客内容、优化博客性能、增强博客功能等。以下是使用插件的步骤:

  1. 在 Hexo 插件库中选择并安装插件。

  2. 修改配置文件 _config.yml 中的 plugins 字段,添加您所安装的插件。

  3. 在命令行中执行以下命令重新生成静态文件:

    1
    $ hexo generate

总结#

Hexo 是一个简单、快速、高效的静态博客框架,可以帮助您快速搭建个人博客、技术博客和文学博客等,同时还支持丰富的主题和插件,可以帮助您更好地管理博客内容、优化博客性能、增强博客功能等。