发表于

哈喽，大家好，我是小爬虫，上一节我们讲了requests库的使用，没有学习过的同学可以关注专栏进行学习。今天我们再次使用requests来实现一个案例：爬取百度翻译。

百度翻译接口分析

首先我们分析一下百度翻译怎么抓取，先在百度翻译页面随意输入一个关键字‘cat’进行翻译，可以看到翻译结果在下面显示了。

接下来我们鼠标右键打开网页源代码，搜索一下网页源代码中是否含有翻译结果。

很明显，源代码中并没有翻译结果。于是我们应该想到，翻译结果并不是存放在html源代码中返回的，而是通过js网络请求返回的。鼠标右键点击检查，进入浏览器调试工具，定位到Network，重新输入关键字‘cat’查看js做了哪些网络请求。通过观察发现其中一个请求就是我们想要找的。

进入Headers查看其request的url和方法发现url是：

1
arduino复制代码https://fanyi.baidu.com/sug

请求方法是POST请求。

再进入Payload页面找到POST请求的data参数，发现是如下格式，其中kw就是对应的key，‘cat’就是我们要搜索的关键字。

1
2
3
css复制代码{
   kw: 'cat'
}

我们进入Preview下面观察这个请求返回的结果，可以看到返回的是一个json格式的数据，其中我们需要的结果是data，这是一个列表，每一个item里面的k和v就是单词对应的翻译结果，这正是我们需要的。

实现百度翻译的爬取

经过以上分析，我们找到了我们应该请求的url，请求的方法是POST，还有POST请求应该携带的data参数的格式，以及请求返回的数据格式。接下来我们就利用我们上一节所讲到的requests发送POST请求的方法来实现，我们很容易写出如下代码

1
2
3
4
5
6
7
8
9
10
11
ini复制代码import requests

url = "https://fanyi.baidu.com/sug"
data = {
    "kw": "cat"
}

resp = requests.post(url, data=data)
data_list = resp.json()['data']
for item in data_list:
    print(f"{item['k']}: {item['v']}")

运行观察打印的结果，可以看到打印出来了我们需要的翻译内容。

当然我们可以把POST请求data里面需要翻译的kw，换成如下的写法，这样就可以实现我们输入一个任意关键字，都可以返回我们需要的结果，这样就实现了一个交互式的翻译爬虫。

1
2
3
css复制代码data = {
    "kw": input("请输入需要翻译的关键字：")
}

本节的实践就到这里，接下来我们将会写一个爬虫来爬取豆瓣的页面，敬请期待。记得关注小爬哦~

本文首发于公众号：小爬虫，欢迎关注

在这里插入图片描述

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第27天，活动详情查看：2021最后一次更文挑战」

MVC设计模式

MVC 模式代表 Model-View-Controller(模型-视图-控制器) 模式。这种模式用于应用程序的分层开发。

• Model(模型) - 模型代表一个存取数据的对象或 JAVA POJO。它也可以带有逻辑，在数据变化时更新控制器。

• View(视图) - 视图代表模型包含的数据的可视化。

• Controller(控制器) - 控制器作用于模型和视图上。它控制数据流向模型对象，并在数据变化时更新视图。它使视图与模型分离开。

实现

我们将创建一个作为模型的 Student 对象。StudentView 是一个把学生详细信息输出到控制台的视图类，StudentController 是负责存储数据到 Student 对象中的控制器类，并相应地更新视图 StudentView。

MVCPatternDemo，我们的演示类使用 StudentController 来演示 MVC 模式的用法。

步骤 1

创建模型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typescript复制代码public class Student {
   private String rollNo;
   private String name;
   public String getRollNo() {
      return rollNo;
   }
   public void setRollNo(String rollNo) {
      this.rollNo = rollNo;
   }
   public String getName() {
      return name;
   }
   public void setName(String name) {
      this.name = name;
   }
}

步骤 2

创建视图。

1
2
3
4
5
6
7
csharp复制代码public class StudentView {
   public void printStudentDetails(String studentName, String studentRollNo){
      System.out.println("Student: ");
      System.out.println("Name: " + studentName);
      System.out.println("Roll No: " + studentRollNo);
   }
}

步骤 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
typescript复制代码public class StudentController {
   private Student model;
   private StudentView view;
 
   public StudentController(Student model, StudentView view){
      this.model = model;
      this.view = view;
   }
 
   public void setStudentName(String name){
      model.setName(name);    
   }
 
   public String getStudentName(){
      return model.getName();    
   }
 
   public void setStudentRollNo(String rollNo){
      model.setRollNo(rollNo);      
   }
 
   public String getStudentRollNo(){
      return model.getRollNo();     
   }
 
   public void updateView(){           
      view.printStudentDetails(model.getName(), model.getRollNo());
   }  
}

步骤 4

使用 StudentController 方法来演示 MVC 设计模式的用法。

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
java复制代码public class MVCPatternDemo {
   public static void main(String[] args) {
 
      //从数据库获取学生记录
      Student model  = retrieveStudentFromDatabase();
 
      //创建一个视图：把学生详细信息输出到控制台
      StudentView view = new StudentView();
 
      StudentController controller = new StudentController(model, view);
 
      controller.updateView();
 
      //更新模型数据
      controller.setStudentName("John");
 
      controller.updateView();
   }
 
   private static Student retrieveStudentFromDatabase(){
      Student student = new Student();
      student.setName("Robert");
      student.setRollNo("10");
      return student;
   }
}

步骤 5

执行程序，输出结果：

1
2
3
4
5
6
yaml复制代码Student: 
Name: Robert
Roll No: 10
Student: 
Name: John
Roll No: 10

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

往期精选（欢迎转发~~）

很有意思的Raft原理，带你动画还原，后面附带具体示例，欢迎来戳~~

前言

ETCD系列的文章是我去年写的，当时写的比较散，图片也看不清，现在提炼文章中比较核心的内容，重新整理，对于想学习ETCD的同学，通过这边文章，一定会有所收获！

走进ETCD

什么是ETCD

etcd是一个Go言编写的分布式、高可用的一致性键值存储系统，用于提供可靠的分布式键值存储、配置共享和服务发现等功能，具有以下特点：

  • 简单：
    • 易使用：基于HTTP+JSON的API让你用curl就可以轻松使用；
    • 易部署：使用Go语言编写，跨平台，部署和维护简单。
  • 可靠：
    • 强一致：使用Raft算法充分保证了分布式系统数据的强一致性；
    • 高可用：具有容错能力，假设集群有n个节点，当有(n-1)/2节点发送故障，依然能提供服务；
    • 持久化：数据更新后，会通过WAL格式数据持久化到磁盘，支持Snapshot快照。
  • 快速：每个实例每秒支持一千次写操作，极限写性能可达10K QPS。
  • 安全：可选SSL客户认证机制。

ETCD框架

从etcd的架构图中我们可以看到，etcd主要分为四个部分：

  • HTTP Server：用于处理用户发送的API请求以及其它etcd节点的同步与心跳信息请求。
  • Store：用于处理etcd支持的各类功能的事务，包括数据索引、节点状态变更、监控与反馈、事件处理与执行等等，是etcd对用户提供的大多数API功能的具体实现。
  • Raft：Raft强一致性算法的具体实现，是etcd的核心。
  • WAL：Write Ahead Log（预写式日志），是etcd的数据存储方式。除了在内存中存有所有数据的状态以及节点的索引以外，etcd就通过WAL进行持久化存储。WAL中，所有的数据提交前都会事先记录日志。Snapshot是为了防止数据过多而进行的状态快照；Entry表示存储的具体日志内容。

Raft协议

基本概念

名词解释

Raft协议一共包含如下3类角色：

  • Leader（领袖）：领袖由群众投票选举得出，每次选举，只能选出一名领袖；
  • Candidate（候选人）：当没有领袖时，某些群众可以成为候选人，然后去竞争领袖的位置；
  • Follower（群众）：这个很好理解，就不解释了。

然后在进行选举过程中，还有几个重要的概念：

  • Leader Election（领导人选举）：简称选举，就是从候选人中选出领袖；
  • Term（任期）：它其实是个单独递增的连续数字，每一次任期就会重新发起一次领导人选举；
  • Election Timeout（选举超时）：就是一个超时时间，当群众超时未收到领袖的心跳时，会重新进行选举。

角色转换

这幅图是领袖、候选人和群众的角色切换图，我先简单总结一下：

  • 群众 -> 候选人：当开始选举，或者“选举超时”时
  • 候选人 -> 候选人：当“选举超时”，或者开始新的“任期”
  • 候选人 -> 领袖：获取大多数投票时
  • 候选人 -> 群众：其它节点成为领袖，或者开始新的“任期”
  • 领袖 -> 群众：发现自己的任期ID比其它节点分任期ID小时，会自动放弃领袖位置
  • 备注：后面会针对每一种情况，详细进行讲解。

选举

领导人选举

为了便于后续的讲解，我画了一副简图，“选举定时器”其实就是每个节点的“超时时间”。

成为候选人：每个节点都有自己的“超时时间”，因为是随机的，区间值为150~300ms，所以出现相同随机时间的概率比较小，因为节点B最先超时，这时它就成为候选人。

选举领导人：候选人B开始发起投票，群众A和C返回投票，当候选人B获取大部分选票后，选举成功，候选人B成为领袖。

心跳探测：为了时刻宣誓自己的领导人地位，领袖B需要时刻向群众发起心跳，当群众A和C收到领袖B的心跳后，群众A和C的“超时时间”会重置为0，然后重新计数，依次反复。

这里需要说明一下，领袖广播心跳的周期必须要短于“选举定时器”的超时时间，否则群众会频繁成为候选者，也就会出现频繁发生选举，切换Leader的情况。

领袖挂掉情况

当领袖B挂掉，群众A和C会的“选举定时器”会一直运行，当群众A先超时时，会成为候选人，然后后续流程和“领导人选举”流程一样，即通知投票 -> 接收投票 -> 成为领袖 -> 心跳探测。


出现多个候选者情况

当出现多个候选者A和D时，两个候选者会同时发起投票，如果票数不同，最先得到大部分投票的节点会成为领袖；如果获取的票数相同，会重新发起新一轮的投票。

当C成为新的候选者，此时的任期Term为5，发起新一轮的投票，其它节点发起投票后，会更新自己的任期值，最后选择新的领袖为C节点。

日志复制

复制状态机

复制状态机的基本思想是一个分布式的状态机，系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在操作日志中。如下图所示，服务器上的一致性模块负责接收外部命令，然后追加到自己的操作日志中，它与其他服务器上的一致性模块进行通信，以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。一旦指令被正确复制，那么每一个服务器的状态机都将按照操作日志的顺序来处理它们，然后将输出结果返回给客户端。

=80%x)

数据同步流程

数据同步流程，借鉴了“复制状态机”的思想，都是先“提交”，再“应用”。当Client发起数据更新请求，请求会先到领袖节点C，节点C会更新日志数据，然后通知群众节点也更新日志，当群众节点更新日志成功后，会返回成功通知给领袖C，至此完成了“提交”操作；当领袖C收到通知后，会更新本地数据，并通知群众也更新本地数据，同时会返回成功通知给Client，至此完成了“应用”操作，如果后续Client又有新的数据更新操作，会重复上述流程。

日志原理

每一个日志条目一般包括三个属性：整数索引Log Index、任期号Term和指令Commond。每个条目所包含的“整数索引”即该条目在日志文件中的槽位，“任期号”对应到图中就是每个方块中的数字，用于检测在不同服务器上日志的不一致问题，指令即用于被状态机执行的外部命令，图中就是带箭头的数字。

领导人决定什么时候将日志条目应用到状态机是安全的，即可被提交的呢？一旦领导人创建的条目已经被复制到半数以上的节点上了，那么这个条目就称为可被提交的。例如，图中的9号条目在其中4节点（一共7个节点）上具有复制，所以9号条目是可被提交的；但条目10只在其中3个节点上有复制，因此10号条目不是可被提交的。

=80%x)

一般情况下，Leader和Follower的日志都是保存一致的，如果Leader节点在故障之前没有向其它节点完全复制日志文件之前的所有条目，会导致日志不一致问题。在Raft算法中，Leader会强制Follower和自己的日志保存一致，因此Follower上与Leader的冲突日志会被领导者的日志强制覆写。为了实现上述逻辑，就需要知道Follower上与Leader日志不一致的位置，那么Leader是如何精准找到每个Follower日志不一致的那个槽位呢？

Leader为每一个Follower维护了一个nextlndex，它表示领导人将要发送给该追随者的下一条日志条目的索引，当一个Leader赢得选举时，它会假设每个Follower上的日志都与自己的保持－致，于是先将 nextlndex初始化为它最新的日志条目索引数+1，在上图中，由于Leader最新的日志条目index是10 ，所以nextlndex的初始值是11。当Leader向Follower发送AppendEntries RPC时，它携带了（item_id，nextIndex - 1）二元组信息，item_id即为nextIndex - 1这个槽位的日志条目的term。Follower接收到AppendEntries RPC消息后，会进行一致性检查，即搜索自己的日志文件中是否存在这样的日志条目，如果不存在，就像Leader返回AppendEntries RPC失败，然后领导人会将nextIndex递减，然后进行重试，直到成功为止。之后的逻辑就比较简单，Follower将nextIndex之前的日志全部保留，之后的全部删除，然后将Leader的nextIndex之后的日志全部同步过来。

上面只是讲述了方法，下面举个例子，加深一下理解，还是以上面的图为例。Leader的nextlndex为11，向b发送AppendEntries RPC(6,10)，发现b没有，继续发送(6,9)(6,8) (5,7) (5,6) (4,5)，最后发送(4,4)才找到，所以对于b，nextlndex=4之后的日志全部删除，然后将Leader的nextlndex=4的日志全部追加过来。

脑裂情况

当网络问题导致脑裂，出现双Leader情况时，每个网络可以理解为一个独立的网络，因为原先的Leader独自在一个区，所以向他提交的数据不可能被复制到大多数节点上，所以数据永远都不会提交，这个可以在第4幅图中提现出来（SET 3没有提交）。

当网络恢复之后，旧的Leader发现集群中的新Leader的Term比自己大，则自动降级为Follower，并从新Leader处同步数据达成集群数据一致，同步数据的方式可以详见“3.3.3 日志原理”。

脑裂情况其实只是异常情况的一种，当Leader通知Follower更新日志、Leader提交更新时，都存在各种异常情况导致的问题，这个我就不再详述了，具体可以参考《云原生分布式存储基石-etcd深入解析》书中的“1.4.3 异常情况”这一章，里面讲述的比较清楚。

ETCD集群部署

ETCD安装请参考文章《ETCD系列教程2 - ETCD体验》

下面我们可以部署一个etcd集群，我把代码还是写到文件中，第一个脚本为不支持在 Docs 外粘贴 block，内容如下（启动etcd需要很多参数，这些参数我都已经注释说明，更多参数详见：www.cnblogs.com/linuxws/p/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
ini复制代码TOKEN=token-01
CLUSTER_STATE=new
NAME_1=etcd-01
NAME_2=etcd-02
NAME_3=etcd-03
HOST_1=127.0.0.1
HOST_2=127.0.0.1
HOST_3=127.0.0.1
PORT_API_1=2379
PORT_PEER_1=2380
PORT_API_2=2479
PORT_PEER_2=2480
PORT_API_3=2579
PORT_PEER_3=2580

CLUSTER=${NAME_1}=http://${HOST_1}:${PORT_PEER_1},${NAME_2}=http://${HOST_2}:${PORT_PEER_2},${NAME_3}=http://${HOST_3}:${PORT_PEER_3}

# For every machine
THIS_NAME=${NAME_1}
THIS_IP=${HOST_1}
THIS_PORT_API=${PORT_API_1}
THIS_PORT_PEER=${PORT_PEER_1}
# 用于杀死进程
lsof -i:2379 | awk '{print $2}' | grep -v "PID" | uniq | xargs kill -9

# --enable-v2 支持v2接口，可以省略
# --data-dir 数据存储目录，可以省略
# --name 节点名称，必须
# --initial-advertise-peer-urls  数据在集群内进行交互的url，必须
# --listen-peer-urls  集群节点之间通信监听的url，必须
# --advertise-client-urls 客户通过该地址与本member交互信息，可以省略
# --listen-client-urls 监听客户端请求的url，必须
# --initial-cluster 初始启动的集群配置，必须
# --initial-cluster-state 初始化集群状态，取值为new和existing，可以省略
# --initial-cluster-token 集群初始化token，可以省略
etcd --enable-v2=true --data-dir=data.${THIS_NAME} --name ${THIS_NAME} \
        --initial-advertise-peer-urls http://${THIS_IP}:${THIS_PORT_PEER} --listen-peer-urls http://${THIS_IP}:${THIS_PORT_PEER} \
        --advertise-client-urls http://${THIS_IP}:${THIS_PORT_API} --listen-client-urls http://${THIS_IP}:${THIS_PORT_API} \
        --initial-cluster ${CLUSTER} \
        --initial-cluster-state ${CLUSTER_STATE} --initial-cluster-token ${TOKEN}

第二个脚本需要把里面的内容替换如下：

1
2
3
4
5
6
7
ini复制代码# For every machine
THIS_NAME=${NAME_2}
THIS_IP=${HOST_2}
THIS_PORT_API=${PORT_API_2}
THIS_PORT_PEER=${PORT_PEER_2}
# 用于杀死进程
lsof -i:2479 | awk '{print $2}' | grep -v "PID" | uniq | xargs kill -9

第三个脚本需要把里面的内容替换如下：

1
2
3
4
5
6
7
ini复制代码# For every machine
THIS_NAME=${NAME_3}
THIS_IP=${HOST_3}
THIS_PORT_API=${PORT_API_3}
THIS_PORT_PEER=${PORT_PEER_3}
# 用于杀死进程
lsof -i:2579 | awk '{print $2}' | grep -v "PID" | uniq | xargs kill -9

有了这3个脚本，分别开3个窗口，分别执行，服务启动截图如下：

当这3个脚本全部启动后，集群部署完毕，我们检查一下3个节点的健康状态：

1
2
3
arduino复制代码curl http://127.0.0.1:2379/health
curl http://127.0.0.1:2479/health
curl http://127.0.0.1:2579/health

如果都返回{“health”:”true”}，表示部署成功，下面我们查看一下部署的节点信息：

1
bash复制代码curl http://127.0.0.1:2379/v2/members

返回结果如下，其中peerURLs是节点互相通信访问的url，clientURLs是对外访问的url：

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
json复制代码{
    "members":[
        {
            "id":"264ae6bc59e99892",
            "name":"etcd-01",
            "peerURLs":[
                "http://127.0.0.1:2380"
            ],
            "clientURLs":[
                "http://127.0.0.1:2379"
            ]
        },
        {
            "id":"dbafe5ad6b652eda",
            "name":"etcd-02",
            "peerURLs":[
                "http://127.0.0.1:2480"
            ],
            "clientURLs":[
                "http://127.0.0.1:2479"
            ]
        },
        {
            "id":"f570ae41f524bdcb",
            "name":"etcd-03",
            "peerURLs":[
                "http://127.0.0.1:2580"
            ],
            "clientURLs":[
                "http://127.0.0.1:2579"
            ]
        }
    ]
}

ETCD使用

集群管理

我们在部署集群时，用到一些方法，这里我简单汇总一下：

1
2
3
4
5
6
bash复制代码// 版本检查，输出{"etcdserver":"3.4.14","etcdcluster":"3.4.0"}
curl http://127.0.0.1:2379/version
// 健康检查，输出{"health":"true"}
curl http://127.0.0.1:2379/health
// 查看集群节点
curl http://127.0.0.1:2379/v2/members

键值操作

设置键的值：

1
bash复制代码curl http://127.0.0.1:2379/v2/keys/message -XPUT -d value="hello world"

返回结果：

1
2
3
4
5
6
7
8
9
json复制代码{
    "action":"set",
    "node":{
        "key":"/message",
        "value":"hello world",
        "modifiedIndex":43,
        "createdIndex":43
    }
}

读取键的值：

1
bash复制代码curl http://127.0.0.1:2379/v2/keys/message

返回结果：

1
2
3
4
5
6
7
8
9
json复制代码{
    "action":"get",
    "node":{
        "key":"/message",
        "value":"hello world",
        "modifiedIndex":43,
        "createdIndex":43
    }
}

给键设置10s的超时时间：

1
bash复制代码curl http://127.0.0.1:2379/v2/keys/message -XPUT -d value="hello world" -d ttl=10

返回结果（prevNode是旧值）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
json复制代码{
    "action":"set",
    "node":{
        "key":"/message",
        "value":"hello world",
        "expiration":"2021-01-21T00:16:13.777434Z",
        "ttl":10,
        "modifiedIndex":44,
        "createdIndex":44
    },
    "prevNode":{
        "key":"/message",
        "value":"hello world",
        "modifiedIndex":43,
        "createdIndex":43
    }
}

获取该键值，超时后，就提示“key not found”：

watch通知

可以对key设置监听，当key的值有变化时，会通知监听的客户端，我们先在客户端A监听key：

1
bash复制代码curl http://127.0.0.1:2379/v2/keys/message?wait=true

然后在客户端B，修改该key的值：

1
bash复制代码curl http://127.0.0.1:2379/v2/keys/message -XPUT -d value="hello world2"

客户端A返回并退出，返回结果：

1
2
3
4
5
6
7
8
9
json复制代码{
    "action":"set",
    "node":{
        "key":"/message",
        "value":"hello world2",
        "modifiedIndex":48,
        "createdIndex":48
    }
}

如果希望客户端A能持续监听，不退出，可以通过增加stream=true参数：

1
ini复制代码curl "http://127.0.0.1:2379/v2/keys/message?wait=true&stream=true"

当在客户端B执行如下时：

1
bash复制代码curl http://127.0.0.1:2379/v2/keys/message -XPUT -d value="hello world" -d ttl=10

客户端A会实时监听返回，比如当给key设置值，或者当key过期时，客户端A都会监听到：

更多ETCD操作，请参考文章《ETCD系列教程2 - ETCD体验》

初探ETCD 3.0

该部分作为扩展知识，仅供了解，更多内容请参考文章《ETCD系列教程3 - 深入ETCD》

版本说明

目前etcd主要经历了3个大的版本，分别为etcd 0.4版本、etcd 2.0版本和etcd 3.0版本。对于etcd 2.0版本，已经可以很好满足etcd的初步需求，主要包括：

  • 专注于key-value存储，而不是一个完整的数据库；
  • 通过HTTP + JSON的方式暴露给外部API；
  • watch机制提供持续监听某个key变化的功能，以及基于TTL的key的自动过期机制。

但是在实际过程中，我们也发现了一些问题，比如客户端需要频繁地与服务端进行通信，集群在空间和时间上都需要承受较大的压力，以及垃圾回收key的时间不稳定等，同时“微服务”架构要求etcd能够单集群支撑更大规模的并发，因此诞生了etcd 3.0版本，主要对HTTP + JSON的通信方式、key的自动过期机制、watch机制、数据持久化等进行了优化，下面我们看看etcd 3.0版本对每个模块都做了哪些优化。

客户端通信方式

gRPC是Google开源的 个高性能、跨语言的RPC框架，基于HTTP/2协议实现。它使用protobuf作为序列化和反序列化协议，即基于 protobuf 来声明数据模型和RPC接口服务。protobuf的效率远高于JSON，尽管etcd v2的客户端已经对JSON的序列号和反序列化进行了大量的优化，但是etcd v3的gRPC序列号和反序列化的速度依旧是etcd v2的两倍多。

etcdv3的客户端使用gRPC与server进行通信，通信的消息协议使用protobuf进行约定，代替了v2版本的HTTP+JSON格式，使用二进制替代文本，更加节省空间。同时gRPC使用的是HTTP/2协议，同一个连接可以同时处理多个请求，不必像HTTP1.1协议中，多个请求需要建立多个连接。同时，HTTP/2会对请求的Header和请求数据进行压缩编码，常见的有Header帧，用于传输Header内容，另外就是Data帧，来传输正文实体。客户端可以将多个请求放到不同的流中，然后将这些流拆分成帧的形式进行二进制传输，传输的帧也会有一个编号，因此在一个连接中客户端可以发送多个请求，减少了连接数，降低了对服务器的压力，二进制的数据传输格式也会是传输速度更快。

总结一下，其实这里主要进行2点优化：

  • 二进制取代字符串：通过gRPC进行通信，代替了v2版本的HTTP+JSON格式；
  • 减少TCP连接：使用HTTP/2协议，同一个连接可以同时处理多个请求，摒弃多个请求需要建立多个连接的方式。

键的过期机制

etcdv2中的键的实效是使用TTL机制来实现的，每个有存活时间的键，客户端必须定期的进行刷新重新设置保证它不被自动删除，每次刷新同时还会重新建立连接去更新键。也就是说，及时整个集群都处于空闲状态，也会有很多客户端与服务器进行定期通信，以保证某个key不被自动删除。

etcdv3版本中采用了租约机制进行实现，每个租约会有一个TTL，然后将一些key附加到租约上，当租约到期后，附加到它上边的key都会被删除。利用键的过期机制可以实现服务注册功能，我们可以将一个服务的域名、IP等信息注册到etcd中，并给相应的键设置租约，并在TTL时间内定期维持一个心跳进行刷新。当服务故障后，心跳消失从而相应的键就会自动删除，从而实现了服务的注册功能和服务的健康检查功能。

总结一下，就是v2版本比较傻瓜，需要时刻维护每个key的通信，v3就比较智能，整个统一的过期key的代号，我们把代号称之为“租约”，我们只需要维护这个代号即可，避免客户端去维护所有的key。

watch机制

etcdv2中的键被废除以后，为了能够跟踪key的变化，使用了事件机制进行跟踪，维护键的状态，来防止被删除掉的后键还能恢复和watch到，但是有一个滑动窗口的大小限制，那么如果要获取1000个时间之前的键就获取不到了。因此etcdv2中通过watch来同步数据不是那么可靠，断开连接一段时间后就会导致有可能中间的键的改动获取不到了。在etcdv3中支持get和watch键的任意的历史版本记录。

另外，v2中的watch本质上还是建立很多HTTP连接，每一个watch建立一个tcp套接字连接，当watch的客户端过多的时候会大大消耗服务器的资源，如果有数千个客户端watch数千个key，那么etcd v2的服务端的socket和内存资源会很快被耗尽。v3版本中的watch可以进行连接复用，多个客户端可以共用相同的TCP连接，大大减轻了服务器的压力。

总结一下，其实这里主要进行2点优化：

  • 实时监听key的更新：解决v2中途key的数据更新，客服端不会感知的问题；
  • 多路复用：这个可以想到select和epool模型，就是一个客户之前需要建立多个TCP连接，现在只需要建立一个即可。

数据存储模型

etcd是一个key-value数据库，ectd v2只保存了key的最新的value，之前的value会被直接覆盖，如果需要知道一个key的历史记录，需要对该key维护一个历史变更的窗口，默认保存最新的1000个变更，但是当数据更新较快时，这1000个变更其实“不够用”，因为数据会被快速覆盖，之前的记录还是找不到。为了解决这个问题，etcd v3摒弃了v2不稳定的“滑动窗口”式设计，引入MVCC机制，采用从历史记录为主索引的存储结构，保存了key的所有历史记录变更，并支持数据在无锁状态下的的快速查询。
etcd是一个key-value数据库，etcdv2的key是一个递归的文件目录结构，在v3版本中的键改成了扁平化的数据结构，更加简洁，并通过线段树的优化方式，支持key的快速查询。

由于etcd v3实现了MVCC，保存了每个key-value pair的历史版本，数据了大了很多，不能将整个数据库都存放到内存中。因此etcd v3摒弃了内存数据库，转为磁盘数据库，即整个数据都存储在磁盘上，底层的存储引擎使用的是BoltDB。

总结一下，其实这里主要进行3点优化：

  • 保存历史数据：摈弃v2的“滑动窗口”式设计，通过MVCC机制，保存了所有的历史数据；
  • 数据落磁盘：因为要保存历史数据，数据量态度，不适合全内存存储，使用BoltDB存储；
  • 查询优化：摒弃v2的目录式层级化设计，使用线段树优化查询。

欢迎大家多多点赞，更多文章，请关注微信公众号“楼仔进阶之路”，点关注，不迷路~~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

Goroutine

什么是Goroutine

  • Goroutine是Golang特有的并发体，是一种轻量级的”线程”
  • Go中最基本的执行单元,每个Goroutine独立执行
  • 每一个Go程序至少有一个Goroutine：主Goroutine。当程序启动时，它会自动创建。
1
2
3
4
5
6
7
8
9
10
go复制代码func main() {
  say()  // 运行中，等待结果
  
  go say()
  fmt.Println("end")  // 不需要等待say()的执行结果
}

func say(){
   fmt.Println("hello world")
}

Vs Os Thread

系统线程 Os Thread

每个系统线程有固定大小的栈，一般默认2M，这个栈主要用来保存函数递归调用时参数和局部变量，由内核调度

固定大小的栈就会带来问题

  • 空间浪费
  • 空间可能又不够，存在栈溢出的风险

Goroutine

由Go的调度器调度，刚创建的时候很小（2kb或者4kb），会根据需要动态地伸缩栈的大小（主流实现中栈的最大值可达到1GB）。

因为启动的代价很小，所以我们可以轻易地启动成千上万个Goroutine。

通过示例了解

1. 多个goroutine同时运行

运行的顺序由调度器决定，不需要相互依赖

1
2
3
4
5
6
7
8
9
10
11
go复制代码func main() {
   fmt.Println("Started")
   for i := 0; i < 10; i++ {
      go execute(i)
   }
   time.Sleep(time.Second * 1)
   fmt.Println("Finished")
}
func execute(id int) {
   fmt.Printf("id: %d\n", id)
}

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
go复制代码func main() {
   urls := []string{
      "https://pic.netbian.com/uploads/allimg/210925/233922-163258436234e8.jpg",
      "https://pic.netbian.com/uploads/allimg/210920/180354-16321322345f20.jpg",
      "https://pic.netbian.com/uploads/allimg/210916/232432-16318058722f4d.jpg",
   }
   for _,url := range urls{

      go downloadFile(url)
   }
   time.Sleep(time.Second)
}

func downloadFile(URL string) error {
   //Get the response bytes from the url
   response, err := http.Get(URL)
   if err != nil {
      return err
   }
   defer response.Body.Close()

   if response.StatusCode != 200 {
      return errors.New("Received non 200 response code")
   }
   //Create a empty file
   file, err := os.Create(path.Base(URL))
   if err != nil {
      return err
   }
   defer file.Close()

   //Write the bytes to the fiel
   _, err = io.Copy(file, response.Body)
   if err != nil {
      return err
   }

   return nil
}

Recover

每个Goroutine都要有recover机制，因为当一个Goroutine抛panic的时候只有自身能够捕捉到其它Goroutine是没有办法捕捉的。

如果没有recover机制，整个进程会crash。

注意：Goroutine发生panic时，只会调用自身的defer，所以即便主Goroutine里写了recover逻辑，也无法recover。

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
go复制代码func main() {
	go do1()
	go do2()
	time.Sleep(10*time.Second)
}

func do1() {
	for i := 0; i < 100; i++ {
		fmt.Println("do1", i)
	}
}

func do2() {

	defer func() {
		if err := recover(); err != nil {
			log.Printf("recover: %v", err)
		}
	}()

	for i := 0; i < 100; i++ {
		if i ==5{
			panic("do panic")
		}
		fmt.Println("do2", i)
	}
}

Channel

基本介绍

Channel是Go内置的数据类型，为初始化的channel的值为nil

通过发送和接收指定元素类型的值来进行通信

  • Channel 提供了 goroutines 之间的同步和通信
  • Goroutine 实现并发/并行的轻量级独立执行。

Shard Memory

thread1Memorythread2thread3

CSP

Communicating sequential processes 通信顺序编程

用于描述两个独立的并发实体通过共享的通讯 channel(管道)进行通信的并发模型，

不关注发送消息的实体，而关注与发送消息时使用的channel

不要通过共享内存来通信，而通过通信来共享内存。 – Rob Pike

Goroutine1ChannelGoroutine2

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
go复制代码type hchan struct {
    qcount   uint           // total data in the queue
    dataqsiz uint           // size of the circular queue
    buf      unsafe.Pointer // points to an array of dataqsiz elements
    elemsize uint16
    closed   uint32         // denotes weather channel is closed or not
    elemtype *_type         // element type
    sendx    uint           // send index
    recvx    uint           // receive index
    recvq    waitq          // list of recv waiters
    sendq    waitq          // list of send waiters
    lock     mutex
}

基本用法

定义

1
go复制代码ChannelType = ( "chan" | "chan" "<-" | "<-" "chan" ) ElementType .

<-运算符指定通道方向， *发送或接收。如果没有给出方向，则通道是 *双向的

1
2
3
go复制代码chan T          // 可以发送接收T
chan<- T        // 只能发送T
<-chan T        // 只能接收T

创建

1
2
go复制代码ch := make(chan int)     // 无缓冲 cap 0
ch := make(chan int,100) // 有缓冲 cap 100

操作

1
2
3
go复制代码ch <- 1. // 发送
<-ch.    // 接收
close(ch)// 关闭

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
go复制代码func goroutineA(ch <-chan int) {
   fmt.Println("[goroutineA] want a data")
   val := <-ch
   fmt.Println("[goroutineA] received the data", val)
}

func goroutineB(ch chan<- int) {
   ch <- 1
   fmt.Println("[goroutineB] send the data 1")
}

func main() {
   ch := make(chan int)
   go goroutineA(ch)
   go goroutineB(ch)
   time.Sleep(time.Second)
}

groutineAchannelgroutineBhello，我想要获取一个数据我现在还没有数据那我睡觉了，等有数据再叫醒我okhello，我要发送一个数据给你ok，发过来吧醒醒，接收数据啦来咯groutineAchannelgroutineB

Unbuffered channels

缓冲区大小为0的channel

channel接收者会阻塞，直到收到消息，channel发送者会阻塞，直到接收者收到消息

unbuffer

Buffered channels

拥有缓冲区，当缓冲区已满时，发送者会阻塞；当缓冲区为空时，接收者会阻塞

buffer.png

总结

不要关注channel的数据结构，更应该关注channel的行为

Command nil empty full not full & empty closed
Receive block block success success success
Send block success block success panic
Close panic success success success panic

几条原则

  • channel 上的发送操作总在对应的接收操作完成前发生
  • 如果 channel 关闭后从中接收数据，接受者就会收到该 channel 返回的零值
  • 从无缓冲的 channel 中进行的接收，要发生在对该 channel 进行的发送完成前
  • 不要在数据接收方或者在有多个发送者的情况下关闭通道。换句话说，我们只应该让一个通道唯一的发送者关闭此通道

示例

1
2
3
4
5
6
7
8
9
go复制代码package main

import "fmt"

func main() {
	ch1 := make(chan string)
	ch1 <- "hello world"
	fmt.Println(<-ch1)
}

执行之后会报错

1
go复制代码fatal error: all goroutines are asleep - deadlock!

原因？

第7行 给通道ch1传入值 hello world,但是对于无缓冲的通道，在接收者未准备好前发送操作是阻塞的，缺少接收者造成死锁

如何解决？

1. 增加接收者
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
go复制代码func main() {

	ch1 := make(chan string)
	go func() {
		fmt.Println(<-ch1)
	}()
	ch1 <- "hello world"
	time.Sleep(time.Millisecond)
}

func main() {
	ch1 := make(chan string)
	go func() {
		ch1 <- "hello world"
	}()
	fmt.Println(<-ch1)
}
2. 增加channel容量
1
2
3
4
5
6
go复制代码func main() {

	ch1 := make(chan string,1)
	ch1 <- "hello world"
	fmt.Println(<-ch1)
}

Goroutine & Channel 串起来

常见的并发模式

通知

  1. 向一个通道发送一个值实现通知
1
2
3
4
5
6
7
8
9
10
11
12
13
14
go复制代码func main() {
   ch := make(chan int)
   go do(ch)
   // do something
   <- ch
   fmt.Println("done")
}

func do(ch chan int){
   // 长时间操作
   time.Sleep(3*time.Second)
   fmt.Println("doing")
   ch <- 1
}
  1. 从一个通道接收值实现通知
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
go复制代码func main() {
   ch := make(chan int)

   go do(ch)
   // do something
   ch <- 1
   fmt.Println("done")
}

func do(ch chan int){
   // 长时间操作
   time.Sleep(3*time.Second)
   fmt.Println("doing")
   <-ch
}

互斥锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
go复制代码func main() {
   mutex := make(chan struct{}, 1) // 容量必须为1

   counter := 0
   increase := func() {
      mutex <- struct{}{} // 加锁
      counter++
      <-mutex // 解锁
   }

   increase1000 := func(done chan<- struct{}) {
      for i := 0; i < 1000; i++ {
         increase()
      }
      done <- struct{}{}
   }

   done := make(chan struct{})
   go increase1000(done)
   go increase1000(done)
   <-done; <-done
   fmt.Println(counter) // 2000
}

控制协程的并发数量

不限制的场景

1
2
3
4
5
6
7
8
9
10
11
12
13
go复制代码func main() {
   for i := 0; i < math.MaxInt32; i++ {
      go func(i int) {

         log.Println(i)
         time.Sleep(time.Second)
      }(i)
   }

   for {
		 time.Sleep(time.Second)
	 }
}

运行结果

1
2
3
4
5
go复制代码$ go run main.go
...
150577
150578
panic: too many concurrent operations on a single file or socket (max 1048575)

问题：如何限制协程的数量？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
go复制代码// main_chan.go
func main() {
	ch := make(chan struct{}, 4)

	for i := 0; i < 20; i++ {
		ch <- struct{}{}
		go func(i int) {

			log.Println(i)
			time.Sleep(time.Second)
			<-ch
		}(i)
	}

	for {
		time.Sleep(time.Second)
	}
}

生产者消费者模型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
go复制代码// 生产者: 生成 factor 整数倍的序列
func Producer(factor int, out chan<- int) {
	for i := 0; i < 10; i++ {
		out <- i * factor
	}
}

// 消费者
func Consumer(in <-chan int) {
	for v := range in {
		fmt.Println(v)
	}
}
func main() {
	ch := make(chan int, 3) // 成果队列

	go Producer(3, ch) // 生成 3 的倍数的序列
	go Producer(5, ch) // 生成 5 的倍数的序列
	go Consumer(ch)    // 消费 生成的队列

	time.Sleep(5 * time.Second)
}

返回最优的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
go复制代码func main() {
   ch := make(chan string, 32)

   go func() {
      ch <- searchByGoogle("golang")
   }()
   go func() {
      ch <- searchByBaidu("golang")
   }()

   fmt.Println(<-ch)
}

func searchByGoogle(search string) string {
   time.Sleep(2 * time.Second)
   return "google result: " + search
}

func searchByBaidu(search string) string {
   time.Sleep(time.Second)
   return "baidu result " + search
}
问题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
go复制代码func main() {
	ch := make(chan string, 32)
	cancel := make(chan struct{},2)
	
	go func() {
		ch <- searchByGoogle("golang",cancel)
	}()
	go func() {
		ch <- searchByBaidu("golang",cancel)
	}()

	fmt.Println(<-ch)
	cancel <- struct{}{}

	time.Sleep(time.Second)
}

func searchByGoogle(search string,cancel chan struct{}) string {

	done := make(chan struct{})
	go func() {
		time.Sleep(2 * time.Second)
		done <- struct{}{}
	}()

	select {
	case <- done:
		return "google result " + search
	case <- cancel:
		fmt.Println("google cancel")
		return "google cancel"
	}
}

func searchByBaidu(search string,cancel chan struct{}) string {
	done := make(chan struct{})
	go func() {
		time.Sleep(1 * time.Second)
		done <- struct{}{}
	}()

	select {
	case <- done:
		return "baidu result " + search
	case <- cancel:
		fmt.Println("google cancel")
		return "baidu cancel"
	}
}
问题2：

如何做超时控制？

Goroutine 泄漏

1. 被遗忘的发送者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
go复制代码func searchByBaidu(search string,cancel chan struct{}) string {
	done := make(chan struct{}) 
	go func() {
		time.Sleep(1 * time.Second)
		done <- struct{}{}
	}()

	select {
	case <- done:
		return "baidu result " + search
	case <- cancel:
		fmt.Println("google cancel")
		return "baidu cancel"
	}
}

case <- done 和 case <- cancel不确定会执行哪一个，如果执行 <-cancel ，则第五行 done <- struct{}{} 会永远阻塞，Goroutine无法退出

如何解决？

增加channel容量

1
go复制代码done := make(chan struct{})

还有其他办法吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
go复制代码func searchByBaidu(search string,cancel chan struct{}) string {
   done := make(chan struct{})
   go func() {
      time.Sleep(1 * time.Second)
      select {
      case done <- struct{}{}:
      default:
         return
      }
   }()

   select {
   case <- done:
      return "baidu result " + search
   case <- cancel:
      fmt.Println("google cancel")
      return "baidu cancel"
   }
}

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
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
go复制代码import (
   "errors"
   "fmt"
   "io"
   "net/http"
   "os"
   "path"
   "runtime"
)

type result struct {
   url string
   err error
}

func main() {

   startGNum := runtime.NumGoroutine()
   urls := []string{
      "https://pic.netbian.com/uploads/allimg/210925/233922-163258436234e8.jpg",
      "https://pic.netbian.com/uploads/allimg/210920/180354-16321322345f20.jpg",
      "https://pic.netbian.com/uploads/allimg/210916/232432-16318058722f4d.jpg",
   }

   total := len(urls)
   // 填充输入
   input := make(chan string, total)
   for _, url := range urls {
      input <- url
   }
   // close(input)
   output := make(chan *result, total)
   // 启动4个goroutine
   for i := 0; i < 4; i++ {
      go download(input, output)
   }
   // 等待结果
   for i := 0; i < total; i++ {
      ret := <-output
      fmt.Println(ret.url, ret.err)
   }
   time.Sleep(2*time.Second)  // 等待download协程的退出
   endGNum := runtime.NumGoroutine()
   fmt.Println("start goroutine", startGNum)
   fmt.Println("end goroutine", endGNum)
}

func download(input <-chan string, output chan<- *result) {

   for v := range input {
      err := downloadFile(v)
      output <- &result{
         url: v,
         err: err,
      }
   }
   fmt.Println("download finish!!!")
}

func downloadFile(URL string) error {
   //Get the response bytes from the url
   response, err := http.Get(URL)
   if err != nil {
      return err
   }
   defer response.Body.Close()

   if response.StatusCode != 200 {
      return errors.New("Received non 200 response code")
   }
   //Create a empty file
   file, err := os.Create(path.Base(URL))
   if err != nil {
      return err
   }
   defer file.Close()

   //Write the bytes to the fiel
   _, err = io.Copy(file, response.Body)
   if err != nil {
      return err
   }

   return nil
}

这个会产生Goroutine的泄漏，原因是第49行的for v := range input 当没有数据输入的时候还在继续等待输入，所有应该在没有数据输入的时候告诉它，让它不要傻傻的等

如何解决？

  1. 关闭input 通道
  2. 传递一个通道告诉它结果

原则

  1. 永远不要在不知道如何停止的情况下启动Goroutine，当我们启动一个Goroutine的时候需要考虑几个问题
* 什么时候停止？
* 可以通过什么方式终止它？
  1. 将并发留给调用者
* 请将是否异步调用的选择权交给调用者，不然很有可能调用者并不知道你在这个函数里面使用了Goroutine
* 如果你的函数启动了一个 Goroutine，您必须为调用者提供一种明确停止该 Goroutine 的方法。将异步执行函数的决定留给该函数的调用者通常更容易。

总结

Concurrency is a useful tool, but it must be used with caution.

并发是一个有用的工具，但是必须谨慎使用

参考链接

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第27天，活动详情查看：2021最后一次更文挑战」

排序

常见的排序算法

image-20211119082822804

常见排序算法的实现

选择排序 最慢排序（最好理解）所以搬血

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

直接选择排序

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

image-20211120195032904

上面那个就是选择排序的本质，但是一次就选一个最大或者最小是不是有点浪费，我们一次同时选到最大最小，就是会比传统的选择排序快一倍

我们基本看到上面代码的缺陷就是我们第一个就是最大是时候，最大的就被换走了，而最小的就被换过来了，但是最大的下标还是标记首位置，把最小的换到后面，也就出现了最小的1在后面的现象

解决方法：既然你最大数的下标和begin重合，那最大数被换走的时候，maxi这个下标也要连带着走

image-20211120233139638

实际上下面 才是我第一次写的代码，直接说下次我再也不写装逼的交换了

image-20211120235444317

我来道bug恶心之处 看好了跳跳 5 ^ 5 0 这就是恶心之处，下次再也不装逼了==

数据交换 剥离出来其他函数也会用到 我明明是简洁之人为了一时的高级而忘记了朴素罪过罪过

1
2
3
4
5
6
c复制代码//数据交换
void Swap(int* pa, int* pb) {
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

选择排序

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
c复制代码// 选择排序
void SelectSort(int* a, int n) {
	int begin = 0;
	int end = n - 1;
	while (begin < end){
		//单趟
		//最大数，最小数的下标
		int mini = begin;//这边假设是刚开始的下标
		int maxi = end;  //这边假设是末尾的下标
		int i = 0;
		for (i = begin; i <= end; i++) {
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[maxi])
				maxi = i;
		}
		//最小的放前面
		Swap(&a[begin], &a[mini]);
		
		if (begin == maxi)
			//如果最大数就是begin位置的，那么交换的时候最大数连带着下标一起动
			maxi = mini;
		//最大的放后面
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

时间复杂度是O(N^2^) 我们的优化不是质的优化，而是量的优化

最好：O(N^2^)

最坏：O(N^2^)

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

image-20211121094727004

向下调整函数

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
c复制代码//向下调整函数
void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	//创建一个孩子变量，有两个孩子就在这个上加1就行
	int child = parent * 2 + 1;
#if HEAP
	while (child < n)
	{
		//选大孩子
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		//大的孩子还大于父亲就交换
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
#elif !HEAP
	while (child < n)
	{
		//选小孩子
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		//小的孩子还小于父亲就交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
#endif // HEAP	
}

堆排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
c复制代码// 堆排序   我们之前讲过升序建大堆
void HeapSort(int* a, int n) {
	//建堆时间复杂度O(N)
	//建大堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	//堆排序时间复杂度O(N*logN)
	while (end>0){
		//交换 把最大的放到后面
		Swap(&a[0], &a[end]);
		//在向下调整
		AdjustDown(a,end,0);
		end--;
	}
}

堆排序时间复杂度O(N*logN)

测性能 让你看看什么叫堆

这里我们测性能就用release版本测吧 因为release版本是程序最优状态，每个排序都是最好状态，巅峰打巅峰

1000大小数组 一千

image-20211121113727817

10000大小数组 一万

image-20211121114331200

100000大小数组 十万

image-20211121114552970

1000000大小数组 一百万

image-20211121125949374

10000000大小数组 一千万 我们不带选择，插入玩太拉跨了，我们看看希尔，堆在超大数据面前谁性能更优

image-20211121130941961

性能函数图

image-20211121133907018

代码

Sort.h

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
C复制代码#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

#define HEAP        1

// 排序实现的接口
// 打印数组
extern void PrintArray(int* a, int n);
// 插入排序
extern void InsertSort(int* a, int n);
// 希尔排序
extern void ShellSort(int* a, int n);
//数据交换
extern void Swap(int* pa, int* pb);
// 选择排序
extern void SelectSort(int* a, int n);
//向下调整
extern void AdjustDwon(int* a, int n, int parent);
// 堆排序
extern void HeapSort(int* a, int n);
// 冒泡排序
extern void BubbleSort(int* a, int n);
// 快速排序递归实现
// 快速排序hoare版本
extern int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
extern int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
extern int PartSort3(int* a, int left, int right);
extern void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
extern void QuickSortNonR(int* a, int left, int right);
// 归并排序递归实现
extern void MergeSort(int* a, int n);
// 归并排序非递归实现
extern void MergeSortNonR(int* a, int n);
// 计数排序
extern void CountSort(int* a, int n);

Sort.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
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
c复制代码#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

// 打印数组
void PrintArray(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}
// 插入排序
void InsertSort(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; i++)	{
		int end = i;
		int x = a[end+1];
		while (end >= 0) {
			//要插入的数比顺序中的数小就准备挪位置
			if (a[end] > x) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				//插入的数比顺序中的要大就跳出
				break;
			}
		}
		//跳出来两种情况
		//1.end == -1 的时候
		//2.break 的时候
		//把x给end前面一位
		a[end + 1] = x;
	}
}
// 希尔排序
void ShellSort(int* a, int n) {
	//分组
	int gap = n;
	//多次预排序（gap>1）+ 直接插入（gap == 1）
	while (gap>1){
		//gap /= 2;
		//除以三我们知道不一定会过1，所以我们+1让他有一个必过1的条件
		gap = gap / 3 + 1;
		//单组多躺
		int i = 0;
		for (i = 0; i < n - gap; i++) {
		int end = i;
		int x = a[end + gap];
		while (end >= 0) {
			if (a[end] > x) {
				a[end + gap] = a[end];
				//步长是gap
				end -= gap;
			}
			else {
				break;
			}
		}
		a[end + gap] = x;
	}
	}	
}
//数据交换
void Swap(int* pa, int* pb) {
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
// 选择排序
void SelectSort(int* a, int n) {
	int begin = 0;
	int end = n - 1;
	while (begin < end){
		//单趟
		//最大数，最小数的下标
		int mini = begin;//这边假设是刚开始的下标
		int maxi = end;  //这边假设是末尾的下标
		int i = 0;
		for (i = begin; i <= end; i++) {
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[maxi])
				maxi = i;
		}
		//最小的放前面
		Swap(&a[begin], &a[mini]);
		
		if (begin == maxi)
			//如果最大数就是begin位置的，那么交换的时候最大数连带着下标一起动
			maxi = mini;
		//最大的放后面
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}
//向下调整函数
void AdjustDown(int* a, int n, int parent)
{
	assert(a);
	//创建一个孩子变量，有两个孩子就在这个上加1就行
	int child = parent * 2 + 1;
#if HEAP
	while (child < n)
	{
		//选大孩子
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		//大的孩子还大于父亲就交换
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
#elif !HEAP
	while (child < n)
	{
		//选小孩子
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		//小的孩子还小于父亲就交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
#endif // HEAP	
}
// 堆排序   我们之前讲过升序建大堆
void HeapSort(int* a, int n) {
	//建堆时间复杂度O(N)
	//建大堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	//堆排序时间复杂度O(N*logN)
	while (end>0){
		//交换 把最大的放到后面
		Swap(&a[0], &a[end]);
		//在向下调整
		AdjustDown(a,end,0);
		end--;
	}
}

test.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
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
c复制代码#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

// 测试排序的性能对比
void TestOP()
{
	//设置随机起点
	srand(time(NULL));
	//将要创建的数组大小
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		//保证两个数组是一样的
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
	}
	int begin1 = clock();//开始时间
	//InsertSort(a1, N);
	int end1 = clock();  //结束时间
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	//SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	printf("InsertSort:%d\n", end1 - begin1);//结束时间减去开始时间 
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
}
//测试插入排序
void TestInsertSort() {
	int a[] = { 1,5,3,7,0,9 };
	InsertSort(a, sizeof(a) / sizeof(a[0]));	
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试希尔排序
void TestShellSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试选择排序
void TestSelectSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	SelectSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试堆排序
void TestHeapSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
int main(){
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	TestOP();
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第27天，活动详情查看：2021最后一次更文挑战」

链式二叉树

我们需要明白一点，就是普通的二叉树增删查改没有什么价值，因为普通二叉树用来存数据复杂且不方便

那么链式二叉树有什么好的地方呢

价值体现：在他的基础之上，增加一些性质，才有意义

1.搜索二叉树 ：最多查找高度次—>时间复杂度O(N)—>单链树也就引出平衡二叉树—>AVL树和红黑树

2.Huffman 树（以后再说，反正不是现在了解的）

我们不关注普通二叉树的增删查改，我们关注递归遍历结构

1.为后面学习更有用树打基础

2.很多oj题结构普遍二叉树

二叉树被分成 根 左子树 右子树

二叉树的遍历

前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

image-20211112211723351

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：（上图为例图）（前中后访问根的时机不一样）

image-20211112213707848

1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。根 左子树 右子树

上图前序遍历的顺序是：A B D NULL NULL NULL C E NULL NULL F NULL NULL只有把空放进去才能真正的知道思想，那些不加 空的就是耍流氓，没错说的就是你们老师，对你们耍流氓

2.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。左子树 根 右子树

上图中序遍历的顺序是：NULL D NULL B NULL A （这时候想访问C就得访问E）NULL E NULL C NULL F NULL

3.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。左子树 右子树 根

上图后序遍历的顺序是：NULL NULL D NULL B NULL NULL E NULL NULL F C A

分治

这里我们用的思想是分治的思想，分而治之—–大事化小，小事化了

二叉树

二叉树节点

1
2
3
4
5
6
7
8
9
c复制代码//二叉树数据类型
typedef char BTDataType;
//二叉树节点
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

我们把上面的树建好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c复制代码//创建树 我们不学二叉树的增删查改原因就在这，我们想要啥树自己链一个就行，没必要增删查改
BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;
	return nodeA;
}

二叉树前序遍历

image-20211113085631295

这张图我实际上是想通过左右与上下滚动联合操作来截图的，然后我就找几个小时，基本能找的都找了，全网没有左右滚动截图的软件基本全是截图后窗口亮，不可以操作外面的滚动条，就算能操作也不可以左右滚动截图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码//二叉树前序遍历
void PreOrder(BTNode* root)
{
	//不断言的原因是可以存在空树
	if (!root)//空树就直接返回
	{
		return;
	}
	printf("%c ",root->data);
	//递归左树
	PreOrder(root->left);
	//递归右树
	PreOrder(root->right);
}

二叉树中序遍历

image-20211113152651694

我故意写成一个窗口的宽度，不然会很麻烦

image-20211113171127588 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c复制代码//二叉树中序遍历
void InOrder(BTNode* root)
{
	//不断言的原因是可以存在空树
	if (!root)//空树就直接返回
	{
		//想打印空也可以
		printf("NULL ");
		return;
	}
	//不为空 递归左树
	InOrder(root->left);
	//打印数据
	printf("%c ",root->data);
	//递归右树
	InOrder(root->right);
}

二叉树后序遍历

image-20211113183048915 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c复制代码//二叉树后序遍历
void PostOrder(BTNode* root)
{
	//不断言的原因是可以存在空树
	if (!root)//空树就直接返回
	{
		//想打印空也可以
		printf("NULL ");
		return;
	}
	//不为空 递归左树
	PostOrder(root->left);
	//递归右树
	PostOrder(root->right);
	//打印数据
	printf("%c ", root->data);
}

二叉树节点个数

次数用传址的方式

image-20211113191511501 

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码//二叉树节点个数
void BinaryTreeSize(BTNode* root,int* pn)
{
	//不断言的原因是可以存在空树
	if (!root)//空树就直接返回
	{
		return;
	}
	(*pn)++;
	BinaryTreeSize(root->left, pn);
	BinaryTreeSize(root->right, pn);
}

次数用返回值的方式（假如我是代码我必然要嫁给这条代码）

image-20211113193430719 

1
2
3
4
5
c复制代码//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right)+1;
}

二叉树叶子节点个数

image-20211113232154579 

1
2
3
4
5
6
7
8
9
C复制代码//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (!root)//空树返回0
		return 0;
	if (!(root->left) && !(root->right))
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

二叉树第k层节点个数

image-20211114000025087 

1
2
3
4
5
6
7
8
9
10
11
c复制代码//二叉树第k层节点个数
int BinaryTreeLevelSize(BTNode* root, int k)
{
	if (!root)
		return 0;
	if (1 == k)
		return 1;
	//root不等于空，k也不等于1，说明root这棵树的第k层节点在子树里面
	//转换成求左右子树的第k-1层节点数量
	return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}

二叉树深度/高度

image-20211114005007897 

1
2
3
4
5
6
7
8
9
10
11
c复制代码//二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (!root)
		return 0;
	//把递归的数用变量保存起来，减少资源的消耗
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

二叉树查找值为x的节点

image-20211114013914115 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c复制代码//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (!root)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftRet = BinaryTreeFind(root->left, x);
	if (leftRet)
		return leftRet;
	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet)
		return rightRet;
	//上面都没进就打印空
	return NULL;
}

二叉树层序遍历

image-20211117085251571 

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
c复制代码//二叉树层序遍历   不需要用递归，用队列就可以解决
void BinaryTreeLevelOrder(BTNode* root)
{
	//空就返回
	if (!root)
		return;
	//创建一个队列
	Queue q;
	//队列初始化
	QueueInit(&q);
	//把root放进队列
	QueuePush(&q,root);
	//队空就跳出来
	while (!QueueErase(&q))
	{
		//把队头取出来放准备拿里面的data
		BTNode* front = QueueFront(&q);
		//再出队
		QueuePop(&q);
		//打印
		printf("%c ", front->data);
		//带左孩子进队
		if (front->left)
			QueuePush(&q,front->left);
		//带右孩子进队
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	//和队列初始化的队列销毁
	QueueDestroy(&q);
}

判断二叉树是否是完全二叉树BinaryTreeComplete

image-20211118000032718 

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
c复制代码// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueErase(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//出到空跳出
		if (!front)
			break;
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	//遇到空了以后，检查队列中剩下的节点
	//1.剩下全是空，则是完全二叉树
	//2.剩下的存在非空，则不是完全二叉树
	while (!QueueErase(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//出到非空就不是完全二叉树
		if (front)
		{
			//这里最容易忘记return之前要对销毁
			QueueDestroy(&q);
			return false;
		}
		
	}
	QueueDestroy(&q);
	return true;
}

二叉树销毁BinaryTreeDestory

image-20211120002929144 

1
2
3
4
5
6
7
8
9
c复制代码//二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (!root)
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

代码

BinaryTree.h

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
c复制代码#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#define CountMode 0


//二叉树数据类型
typedef char BTDataType;
//二叉树节点
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

//二叉树前序遍历
extern void PreOrder(BTNode* root);
//二叉树中序遍历
extern void InOrder(BTNode* root);
//二叉树后序遍历
extern void PostOrder(BTNode* root);
//获得节点函数
extern BTNode* BuyNode(BTDataType x);
#if CountMode
//二叉树节点个数
extern void BinaryTreeSize(BTNode* root, int* pn);
#elif !CountMode
//二叉树节点个数
extern int BinaryTreeSize(BTNode* root);
#endif
//二叉树叶子节点个数
extern int BinaryTreeLeafSize(BTNode* root);
//二叉树第k层节点个数
extern int BinaryTreeLevelSize(BTNode* root,int k);
//二叉树深度/高度
extern int BinaryTreeDepth(BTNode* root);
//二叉树查找值为x的节点
extern BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树层序遍历   
extern void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
extern bool BinaryTreeComplete(BTNode* root);
//二叉树销毁
extern void BinaryTreeDestory(BTNode* root);

BinaryTree.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
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
c复制代码#define _CRT_SECURE_NO_WARNINGS 1

#include"BinaryTree.h"
#include"Queue.h"

//获得节点函数
BTNode* BuyNode(BTDataType x)
{
	//创建二叉树节点
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	//检查是否成功创建
	assert(node);
	//把数据放到节点里
	node->data = x;
	//左右子树先空树
	node->left = node->right = NULL;
	return node;
}

//二叉树前序遍历
void PreOrder(BTNode* root)
{
	//不断言的原因是可以存在空树
	if (!root)//空树就直接返回
	{
		//想打印空也可以
		printf("NULL ");
		return;
	}

	printf("%c ",root->data);
	//递归左树
	PreOrder(root->left);
	//递归右树
	PreOrder(root->right);
}
//二叉树中序遍历
void InOrder(BTNode* root)
{
	//不断言的原因是可以存在空树
	if (!root)//空树就直接返回
	{
		//想打印空也可以
		printf("NULL ");
		return;
	}
	//不为空 递归左树
	InOrder(root->left);
	//打印数据
	printf("%c ",root->data);
	//递归右树
	InOrder(root->right);
}
//二叉树后序遍历
void PostOrder(BTNode* root)
{
	//不断言的原因是可以存在空树
	if (!root)//空树就直接返回
	{
		//想打印空也可以
		printf("NULL ");
		return;
	}
	//不为空 递归左树
	PostOrder(root->left);
	//递归右树
	PostOrder(root->right);
	//打印数据
	printf("%c ", root->data);
}
#if CountMode
//二叉树节点个数
void BinaryTreeSize(BTNode* root,int* pn)
{
	//不断言的原因是可以存在空树
	if (!root)//空树就直接返回
	{
		return;
	}
	(*pn)++;
	BinaryTreeSize(root->left, pn);
	BinaryTreeSize(root->right, pn);
}
#elif !CountMode
//二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right)+1;
}
#endif
//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (!root)//空树返回0
		return 0;
	if (!(root->left) && !(root->right))
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
//二叉树第k层节点个数
int BinaryTreeLevelSize(BTNode* root, int k)
{
	//k小于等于零直接断言 因为都是从第一层开始的
	assert(k > 0);
	if (!root)
		return 0;
	if (1 == k)
		return 1;
	//root不等于空，k也不等于1，说明root这棵树的第k层节点在子树里面
	//转换成求左右子树的第k-1层节点数量
	return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}
//二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (!root)
		return 0;
	//把递归的数用变量保存起来，减少资源的消耗
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (!root)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftRet = BinaryTreeFind(root->left, x);
	if (leftRet)
		return leftRet;
	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet)
		return rightRet;
	//上面都没进就打印空
	return NULL;
}
//二叉树层序遍历   不需要用递归，用队列就可以解决
void BinaryTreeLevelOrder(BTNode* root)
{
	//空就返回
	if (!root)
		return;
	//创建一个队列
	Queue q;
	//队列初始化
	QueueInit(&q);
	//把root放进队列
	QueuePush(&q,root);
	//队空就跳出来
	while (!QueueErase(&q))
	{
		//把队头取出来放准备拿里面的data
		BTNode* front = QueueFront(&q);
		//再出队
		QueuePop(&q);
		//打印
		printf("%c ", front->data);
		//带左孩子进队
		if (front->left)
			QueuePush(&q,front->left);
		//带右孩子进队
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	//和队列初始化的队列销毁
	QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueErase(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//出到空跳出
		if (!front)
			break;
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	//遇到空了以后，检查队列中剩下的节点
	//1.剩下全是空，则是完全二叉树
	//2.剩下的存在非空，则不是完全二叉树
	while (!QueueErase(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//出到非空就不是完全二叉树
		if (front)
		{
			//这里最容易忘记return之前要对销毁
			QueueDestroy(&q);
			return false;
		}
		
	}
	QueueDestroy(&q);
	return true;
}
//二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (!root)
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

test.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
50
51
c复制代码#define _CRT_SECURE_NO_WARNINGS 1

#include"BinaryTree.h"
#include"Queue.h"


//创建树 我们不学二叉树的增删查改原因就在这，我们想要啥树自己链一个就行，没必要增删查改
BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;
	return nodeA;
}

int main()
{
	BTNode* root = CreatBinaryTree();
	//PreOrder(root);
	//InOrder(root);
	PostOrder(root);
	printf("\n");
#if CountMode
	int n1 = 0;
	BinaryTreeSize(root, &n1);
	printf("%d ",n1);
#elif !CountMode

	printf("%d\n",BinaryTreeSize(root));
#endif
	printf("%d\n", BinaryTreeLeafSize(root));
	printf("%d\n", BinaryTreeLevelSize(root,3));
	printf("%d\n", BinaryTreeDepth(root));
	BTNode* ret1 = BinaryTreeFind(root,'C');
	printf("%p\n", ret1);
	BTNode* ret2 = BinaryTreeFind(root, 'H');
	printf("%p\n", ret2);
	BinaryTreeLevelOrder(root);
	printf("%d\n", BinaryTreeComplete(root));
	BinaryTreeDestory(root);
	root = NULL;
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第27天，活动详情查看：2021最后一次更文挑战

前言

作为一个经常写文章的你来说，没有一个自己的图床可真是太不应该了，今天我就带你手把手的搭建一个属于自己的免费图床。

Typroa

首先，我们需要下载 Typora 这是一款简洁到你不敢相信的编辑器，但是功能还是非常的强大，与 markdown 无缝的配合，推荐使用。

自行下载安装哈，但是我们在使用 typora 的时候，所有的图片都是保存在本地的，如果你想要发布到网上还需要单独对图片进行处理。所以我就搭建了一个免费的图床，这里选择了 gitee.

图床的意思就是专门用来存放图片，同时允许你把图片对外连接的网上空间，不少图床都是免费的。设置图床后，在博客中插入的图片链接就可以随时随地在线预览。

那如何把一个本地图片转化为上传到 gitee 呢？这里我们需要另外一个工具 PicGo， 就是自动把本地图片转换成链接的一款工具，网络上有很多图床工具，就目前使用种类而言，PicGo 算得上一款比较优秀的图床工具。

下载 PicGo

选择合适自己的版本进行下载即可，我使用的 windows 下载如下文件即可。

image-20211127164842842

配置 PicGo - 前置条件

首先创建一个公开的 repository 作为图片存储空间，创建 master 分支，readme 文件，以为为例，我创建了一个名为 image 的公开仓库。然后我又在仓库下新建了一个文件 img 作为图片目录。

image-20211127165607818

这里要注意看哈，我的 repo 地址是 gitee.com/kelisi_kris… 因为我们可以自定义域名空间的，这里我就是自定义的 kelisi_kris

我们需要登录到 gitee, 得到自己的 token

image-20211127165059683

点击私人令牌 - 生成新令牌，这里描述可以看着写 “PicGo 使用” 之类的。然后直接点击提交即可。

image-20211127165250834

记得要保存生成的 token，后面要使用。

配置 PicGo

添加插件

打开 PicGo 的插件设置，搜索 gitee 据说是只需要一个 gitee 插件就行，这里我就全部点击了下载。另外就是下载 gitee 插件，需要本地有 node 的环境，因为需要用到 npm 这个工具，所以要先安装 node 哈，下载地址在这里

image-20211127170043860

打开 PicGo 的图床设置，找到 gitee 图传

image-20211127165906149

这里的配置一定要和上一步新建的 repo 地址对应上哈 gitee.com/kelisi_kris… 不然是找不到的。这里还要注意哈，要点击一下设为默认图床。

Typora 的配置

点击文件 - 偏好设置

image-20211127170743580

这样就设置好了，我们直接把图片复制到 Typora 中之后会有提示是否上传，点击上传即可。我们在 gitee 的 repo 中就可以看到图片了。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战」

目的

安装Spark

在spark-shell中运行代码

编写Spark独立应用程序

基础环境

Spark支持4种不同类型的部署方式，包括：
Local模式：单机模式
Standalone模式：使用Spark自带的简单集群管理器
YARN模式：使用YARN作为集群管理器
Mesos模式：使用Mesos作为集群管理器

Spark可以独立安装使用，也可以和Hadoop一起安装使用。安装了Hadoop后，就可以让Spark使用HDFS存取数据。不安装Hadoop，Spark只能访问本地文件系统数据。需要说明的是，当安装好Spark以后，里面就自带了scala环境，不需要额外安装scala。

本次实验采用Hadoop（伪分布式）+Spark（local）模式。安装Spark之前需要安装Linux系统、Java环境 ，Hadoop。

下载安装

Spark安装包下载地址： spark.apache.org

进入下载页面后，点击主页右侧的“Download Spark”按钮进入下载页面，下载页面中提供了几个下载选项，主要是Spark release及Package type的选择，如下图所示。第1项Spark release一般默认选择最新的发行版本，截至2018年4月份的最新版本为2.3.0（本教程采用2.1.0）。第2项package type则选择“Pre-build with user-provided Hadoop [can use with most Hadoop distributions]”，可适用于多数Hadoop版本。选择好之后，再点击第4项给出的链接就可以下载Spark了。

解压安装包spark-2.1.0-bin-without-hadoop.tgz至路径 /usr/local：

通过运行Spark自带的示例，验证Spark是否安装成功。
cd /usr/local/spark
bin/run-example SparkPi
执行时会输出非常多的运行信息，输出结果不容易找到，可以通过 grep 命令进行过滤（命令中的 2>&1 可以将所有的信息都输出到 stdout 中，否则由于输出日志的性质，还是会输出到屏幕中）:
bin/run-example SparkPi 2>&1 | grep “Pi is”

image.png
Spark Shell可以以实时、交互的方式来分析数据，也可以使用sbt或者maven编译打包运行。推荐初学使用第一种。
Spark Shell支持Scala和Python，由于Spark框架本身就是使用Scala语言开发的，所以使用spark-shell命令会默认进入Scala的交互式执行环境。如果要进入Python的交互式执行环境，则要执行pyspark命令。

在spark-shell中运行代码

执行如下命令启动Spark Shell（默认是local模式）：
image.png
启动Spark Shell成功后在输出信息的末尾可以看到“Scala >”的命令提示符

image.png

可以在里面输入scala代码进行调试：

image.png

可以使用命令“:quit”退出Spark Shell：

image.png

或者，也可以直接使用“Ctrl+D”组合键，退出Spark Shell

编写Spark独立应用程序

1.安装sbt

sbt是一款Spark用来对scala编写程序进行打包的工具，Spark 中没有自带 sbt，需要下载安装

下载sbt安装包以后，执行如下命令拷贝至 /usr/local/sbt 中：

cp ~/下载/sbt-launch.jar .

接着在 /usr/local/sbt 中创建 sbt 脚本（vim ./sbt），添加如下内容：

1
2
3
shell复制代码!/bin/bash
SBT_OPTS="-Xms512M -Xmx1536M -Xss1M -XX:+CMSClassUnloadingEnabled -XX:MaxPermSize=256M"
java $SBT_OPTS -jar `dirname $0`/sbt-launch.jar "$@"

保存后，为 ./sbt 脚本增加可执行权限：

最后运行如下命令，检验 sbt 是否可用（需要几分钟时间）（请确保电脑处于联网状态，首次运行会处于 “Getting org.scala-sbt sbt 0.13.11 …” 的下载状态，请耐心等待。笔者等待了 7 分钟才出现第一条下载提示）：

查看版本

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

RK算法的全称叫Rabin-Karp算法，是由它的两位发明者Rabin和karp的名字命名的。算法理解不算难，就是BF的升级版。

7.1 RK算法思路

在上一节介绍的BF算法的时候，我们是每次都检查主串和模式串是否匹配，需要依次对比每个字符，所以BF算法的时间复杂度很高，是O(n*m)。我们对暴力解法稍加改造，引入哈希算法，时间复杂度就会降低。

RK算法的思路是这样的，我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，（因为在暴力解法当中，也是跟n-m+1个子串进行比较），然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串的一样，（为了防止哈希碰撞，这时候我们再单独对比一下字符串）。因为这两个值都是数字，所以比较是否相等会非常快速，所以模式串和子串比较的效率就提高了。

在这里插入图片描述

但是如果需要遍历子串中的每个字符去计算哈希值，算法整体效率并没有提高，有什么办法提交效率？

7.2 哈希算法

这样的话，我们就需要重新设计一个哈希算法了。我们假设要匹配的字符串字符集中包含K个字符，我们可以用K进制数来表示一个子串，这个K进制数转化成十进制数，作为子串的哈希值。

我们就按照上面的图来计算一下哈希值：（上面只有26个小写字母，我们可以看成26进制）

在这里插入图片描述

看了图应该懂了吧。就是按平常计算十进制的时候计算的。

虽然是这个样子，但好像我们写代码的时候也是需要遍历的，如果是这样，那我们为什么提议这个哈希算法呢？

根据我们看图，h1 和 h2就有很明显的关系。

hi=ciRM−1+ci+1RM−2+…+ci+M−1R0(R是进制，M是子串长度)h_i = c_iR^{M-1}+c_{i+1}R^{M-2}+…+c_{i+M-1}R^{0} (R是进制，M是子串长度)hi​=ci​RM−1+ci+1​RM−2+…+ci+M−1​R0(R是进制，M是子串长度)
hi+1=ci+1RM−1+ci+2RM−2+…+ci+M−1R1+ci+1+M−1R0h_{i+1} = c_{i+1}R^{M-1}+c_{i+2}R^{M-2}+…+c_{i+M-1}R^{1}+c_{i+1+M-1}R^{0}hi+1​=ci+1​RM−1+ci+2​RM−2+…+ci+M−1​R1+ci+1+M−1​R0
这两个公式有什么关系呢？我的直觉告诉我是很有关系的

在这里插入图片描述

中间画了红线的部分 ci 这部分是一样的，只不过R的指数hi+1 比 hi 乘以R。

所以我们把公式转换一下：

hi−ciRM−1=ci+1RM−2+…+ci+M−1R0h_i - c_iR^{M-1} = c_{i+1}R^{M-2}+…+c_{i+M-1}R^{0}hi​−ci​RM−1=ci+1​RM−2+…+ci+M−1​R0
hi+1=(hi−ciRm−1)R+ci+1+M−1R0=hi∗R−ciRm+ci+1+M−1R0h_{i+1} = (h_i - c_iR^{m-1})R + c_{i+1+M-1}R^{0} = h_i *R - c_iR^m + c_{i+1+M-1}R^{0}hi+1​=(hi​−ci​Rm−1)R+ci+1+M−1​R0=hi​∗R−ci​Rm+ci+1+M−1​R0
这样我们就可以通过一次遍历，就把子串的哈希值计算出来，真的好巧妙啊。

7.3 代码

上一个代码先，虽然思想已经懂了，但是还是多写代码，熟悉一下，有刷过leetcode的应该都记得，这种用哈希来保存题很多，所以就借这这次来实现一个代码。

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
c复制代码// 计算模式串的哈希值
long RK::hash_base(std::string pat, int M, int R)
{
    // 计算
    long RM = 0;
    for(int i = 0; i < M; i++)
    {
        
        RM += (pat.at(i) - 'a') * pow(R, M-1-i);
        // printf("pat.at(%d) - 'a' = %d %lf %ld\n", i, pat.at(i) - 'a', pow(R, M-1-i), RM);
    }

    // printf("Rm %ld\n", RM);
    return RM;
}


// 准备主串的哈希值
int RK::string_hash(std::string txt, int M, int R, std::unordered_map<long, int> &mymap)
{
    int N = txt.length();
    long h = hash_base(txt, M, R);      // 计算前面M个哈希值
    mymap[h] = 0;
    //printf("h = %ld\n", h);
    for(int i = 1; i< N-M+1; i++)
    {
        //printf("ddd %ld %d %d\n", h * 26, (txt.at(i-1) - 'a') * pow(R, M) , (txt.at(i-1+1+M-1) - 'a'));
        h = h * R - (txt.at(i-1) - 'a') * pow(R, M) + (txt.at(i-1+1+M-1) - 'a');
        
        mymap[h] = i;
       //mymap.insert(std::make_pair(h, i));
       //printf("h = %ld\n", h);
    }

    return 0;
}


int RK::search(std::string pat, std::string txt, int R)
{
    int N = txt.length();
    int M = pat.length();
    std::unordered_map<long, int> mymap;
    printf("search %d %d\n", N, M);

    long pat_hash = hash_base(pat, M, 26);
    printf("pat_hash %d\n", pat_hash);
    string_hash(txt,  M, R, mymap);
    
    // for(std::unordered_map<long, int>::iterator it = mymap.begin(); it != mymap.end(); it++) {
    //         std::cout << "one " << it->first << "  two " << it->second << std::endl;
    // }


    auto itr = mymap.find(pat_hash);
    if(itr != mymap.end())
    {
        // 这里可以判断一下，然后处理哈希碰撞问题
        printf("itr %d %d\n", itr->first, itr->second);
        return itr->second;
    }

    printf("return 0");

    return 0;
}

写了代码之后才发现确实不熟练，还是需要多加练习。

代码路径：RK.cpp

7.4 总结

代码写完了，接下来看看时间复杂度是多少了。（其实可以不用存到哈希中，只要计算模式字符串的哈希，然后主串主要计算前面一个值，然后等到模式串匹配的时候再计算，这个是《算法4》中采用的）

整个RK算法分两部分：第一部分就是计算主串的哈希值，明显可以看出是O(n)，然后对比的时候，我是使用存储到哈希中，用find函数，所以也是O(1)，整体的复杂度为O(n)。

还有一个问题：如果模式串很长，响应的主串也很长，通过上面的哈希计算函数得到的哈希值很大，如果超出了计算机的整形数据范围，那该如何解决？

这是我们上面设计的哈希算法的问题，因为是用进制的方式计算的，当然很大了，所以我们需要考虑允许一些哈希碰撞，《算法4》中提议的是随机一个素数Q，把计算出来的哈希值模Q,这样也是一个方法，感觉还不错。如果哈希碰撞了，怎么办，上面我也提过了，如果真的哈希值一样，我们可以对比一个模式串和子串的值就可以了。这也消耗不了太多时间。

所以需要控制哈希算法的冲突概率，如果存在大量冲突，就会导致RK算法时间复杂度退化。严重会退化到O(n*m)。一般情况下，冲突不会很多，RK算法效率很是比BF算法高的。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战」

MySQL 数据库中一共去定义了四类数据类型，而且它们都有不同的取值范围，也就是合法的取值区域。对于业务开发来说，选择合适的数据类型往往是很简单的。比如你存储姓名，肯定是用字符串，存储年龄你会选择整形数字等等。所以这里的焦点其实是各个数据类型的取值范围对业务发展的影响。

字符串

字符串类型是MySQL中最常用的数据类型，也是比较灵活的数据类型，学习字符串数据，也会讨论到字符集与转义字符等知识，因为比较复杂。MySQL的字符串类型都可以用于去存储字符串。

MySQL的字符串数据类型可以分为 二进制字符串类型 和 非二进制字符串类型两种。

二进制字符串类型

数据类型定义 存储空间占用量范围 用途
BINARY 0-255 bytes 固定长度二进制字符串
VARBINARY 0-65535 bytes 可变长度二进制字符串
TINYBLOB 0-255 bytes 不超过 255 个字符的二进制字符串
BLOB 0-65 535 bytes 二进制形式的长文本数据
MEDIUMBLOB 0-16 777 215 bytes 二进制形式的中等长度文本数据
LONGBLOB 0-4 294 967 295 bytes 二进制形式的极大文本数据

非二进制字符串类型

数据类型定义 存储空间占用量范围 用途
CHAR 0-255 bytes 定长字符串
VARCHAR 0-65535 bytes 变长字符串
TINYTEXT 0-255 bytes 短文本字符串
TEXT 0-65 535 bytes 长文本数据
MEDIUMTEXT 0-16 777 215 bytes 中等长度文本数据
LONGTEXT 0-4 294 967 295 bytes 极大文本数据

它们不仅仅在取值范围上有不同的取值区域，更大的区别是它们存储数据的方式。对于取值范围来说，我们当然不可能都把它们都记住。MySQL 也想到了这个问题，提供了 help 命令，然后我们可以去查询数据类型的使用范围。

这里给大家去演示一下使用 help 命令去看一看 char 数据类型。查看命令如下：

1
scss复制代码help char

使用 help 帮助命令查看 char 数据类型的结果如下所示。

image-20210321225219832

我们可以从 MySQL 给出的描述中，可以看到 char 数据类型的用于去定义一个固定长度的字符串。而且它的长度范围是从 0到 255 之间，且必须是在创建表的时候去指定的。它有一个特殊的情况，这个存储字符串的时候，如果没有达到一个指定的长度，MySQL 会使用空格去填充指定长度。如果我们想要去存储不同记录的字符串的长度差别比较大，就会造成比较大的空间浪费。

如果我们存储的数据长度浮动范围非常大，就可以考虑使用到 varchar 去存储，这种数据类型是你需要多少空间就会使用多少空间，而 varchar 的取值范围是1~65535，不过 varchar 的最大长度一般小于 65535，因此 MySQL 中数据行的最大长度也是65535，何况 varchar 还需要额外两个字节来记录其目前的存储长度。

BINARY 和 VARBINARY 类似于 CHAR 和 VARCHAR，不同的是它们包含二进制字符串而不要非二进制字符串。也就是说，它们包含字节字符串而不是字符字符串。这说明它们没有字符集，并且排序和比较基于列值字节的数值值。

BLOB 是包含 TINYBLOB、BLOB、MEDIUMBLOB、LONGBLOB 系列数据类型的家族，用于存储二进制字符串，比如图片、声音等数据，而 TEXT 是包含 TINYTEXT、TEXT、MEDIUMTEXT、LONGTEXT 系列数据类型的家族用于存储非二进制字符串，所以 TEXT 系列的类型存储与解析与字符集有关。使用 MEMORY 存储引擎的数据表不支持 BLOB 和 TEXT 这两种数据类型。

ENUM是一种特殊的字符串类型，占用1或2个字节，也就是说 ENUM 类型可以设置 65535 个成员，ENUM 类型与一般的字符串类型不同，设置为 ENUM 类型的字段，只能存储预先定义好的字符串值。

当我们需要存储的数据量比较大的时候，就应该考虑使用到文本。这里我给出一个建议，如果当你所要存储的数据量超过五百个字符的时候，就应该考虑去使用文本。另外文本类型不能有默认值。 而且在创建索引的时候，需要去指定它前多少个字符是成为索引的。

日期和时间

类型 大小 格式 范围
DATE 3 bytes YYYY-MM-DD 1000-01-01 ~ 9999-12-31
TIME 3-6 bytes HH::MM:SS[.微秒] -838:59:59 ~ 838:59:59
YEAR 1 bytes YYYY 1901 ~ 2155
DATETIME 5-8 bytes YYYY-MM-DD HH:MM:SS[.微秒值] 1000-01-01 00:00:00 ~ 9999-12-31 23:59:59 UTC
TIMESTAMP 4-7 bytes YYYY-MM-DD HH:MM:SS[.微秒值] 1970-01-01 00:00：00 ~ 2038-01-19 03:14:07 UTC

根据表格可以得出大致的区别以及适用范围了。

DATE 数据类型用于存储日期，占用3个字节，，默认零值为0000-00-00，通常只想用来存储如 “2021-03-02” 这种格式的日期字段时，可以选择使用 DATE 类型。

TIME 类型占用3个字节，注意 TIME 类型并不是表示时分秒，而表示逝去的一段时间，即表示两个事件之间的时间间隔，所以 TIME 类型可以为负值。通常只想用来存储如 “04:31:22.33” 这种格式的时间字段时，可以选择使用 TIME 类型。

DATETIME 数据类型则是 DATE 和 TIME 两个种数据类型的一个组合格式，它是最常见于用途最广的数据类型。通常只想用来存储如 “2020-02-02 02:02:02.02” 这种格式的日期字段时，可以选择使用 DATETIME 类型。

TIMESTAMP 数据类型是用于保存日期与时间的组合值的，与时区相关，默认是以UTC （世界标准时间）的格式存储的，当我们从数据中查询 TIMESTAMP 的数据列，会根据我们当前的时区自动转换值，它与 DATETIME 的这个存储的数据格式是一样的，主要区别它会比这个 DATETIME 的存储的这个时间范围要小一些，而且前者提供的值与时区有关系，后者则保留文本表示的日期和时间。

YEAR 类型为日期类型，通常只想用来存储如 “2021” 这种格式的日期字段时，可以选择使用 YEAR 类型。

数值类型

MySQL 支持所有标准 SQL 数值数据类型。其实对于数值类型来说,类型可分为整数类型、定点型类型、浮点数类型、位类型四种类型。

类型 大小 用途
TINYINT 1 byte 小整数值
SMALLINT 2 bytes 大整数值
MEDIUMINT 3 bytes 大整数值
INT或INTEGER 4 bytes 大整数值
BIGINT 8 bytes 极大整数值
FLOAT 4 bytes 单精度 浮点数值
DOUBLE 8 bytes 双精度 浮点数值
DECIMAL 对DECIMAL(M,D) ，如果M>D，为M+2否则为D+2 小数值

整数类型用于存储整数，根据其存储的字节大小可分为 TINYINT，SMALLINT，MEDIUMINT、INT、BIGINT。

TINYINT为小整数类型，有符号范围-128 ~ 127，无符号范围 0 ~ 255，此类型通常在数据库中表示类型的字段，如某一字段 TYPE 表示学科,其中 “type=1” 表示语文，“type=2” 表示数学, “type=3” 表示英语，此时 TYPE 字段即可使用 TINYINT这种存储空间比较小的类型。

SMALLINT为小整数类型，有符号范围 -32768 ~ 32767，无符号范围 0 ~ 65535，当遇到最大值不超过 65535 的整数类型字段时，可使用无符号 SMALLINT 类型。

MEDIUMINT为中整数类型，有符号范围 -8388608 ~ 8388607，无符号范围 0 ~ 16777215，当遇到最大值不超过 16777215 的整数类型字段时，可使用无符号 MEDIUMINT类型。

INT为整数类型，无符号范围 0 ~ 49294967295，当遇到最大值不超过 49294967295 的整数类型字段时，可使用无符号 INT类型，通常自增主键 id 使用 INT类型。

BIGINT 为大整数类型，存储空间8个字节(64位)，有符号范围 -9223372036854775808 ~ 9223372036854775807，无符号范围 0 ~ 18446744073709551615，当遇到最大值不超过 18446744073709551615 的整数类型字段时，可使用无符号 BIGINT 类型，通常自增主键 id 使用 INT无法满足时，可以使用 BIGINT类型。

FLOAT 和 DOUBLE 属于浮点类型。FLOAT 为单精度浮点类型，支使用标准的浮点运算进行近似计算，若想知道浮点运算是怎么计算的，则需要研究操作系统的浮点数方式，通常对小数精度要求不那么高的字段可使用 FLOAT 类型。DOUBLE 为双精度浮点类型，相比 DOUBLE 有更高精度和更大的范围，通常对小数精度要求不那么高，但比 DOUBLE 要求更高的字段可使用 double 类型。

DECIMAL 属于定点的数据类型，保存的是精确的值，通常用于这个精度要求非常高的计算中。若使用 FLOAT 类型来取代一些需要精确小数点类型的字段时，大的数据量会导致数据错误，比如金额,若使用 FLOAT 类型，可能会丢失精度，此时对于金额这样对精度要求很高的字段来说，可以选择使用 DECIMAL 类型。

二进制数据类型

二进制数据类型，理论上可以存储任何数据，可以是文本数据，也可以存储图像或者其他多媒体数据。二进制数据类型相对于其他的数据来一起来说，使用频率是比较低的。

MySQL 数据库一共提供了四种二进制类型，分别是 TITYBLOB，BLOB, MEDIUMBLOB，LONGLOB. 它们的区别是在于这个存储范围的不同。我们可以根据名字去判断区分.

需要注意,虽然 MySQL 提供并且支持大文件的存储，但是这样会急剧降低数据库的性能。所以应该谨慎使用这些数据类型，能够不用的情况下呢，就尽量不用。

MySQL 提供的最常用的数据类型以及它们的特性适用场景的介绍完毕了。除了要记住这些特性之外，更多的是不断的尝试应用和总结，得出你自己的结论。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%