0%

DBSCAN算法

支持二维坐标点聚类,参考:密度聚类算法DBSCAN

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 numpy as np
import matplotlib.pyplot as plt

# eps: 邻域半径
# MinPts: 核心样本的邻域中最少点数目
class Dbscan:
def __init__(self, eps: int = 5, MinPts: int = 3):
self.eps = eps
self.MinPts = MinPts
self.points = None
self.group = None
self.group_counter = 1

def get_neighbors(self, idx: int):
neighbors = ((self.points - self.points[idx]) ** 2).sum(axis=1) <= (self.eps ** 2)
neighbors[idx] = False
return neighbors

def expand(self, idx: int):
if self.group[idx] != 0:
return
self.group[idx] = self.group_counter
neighbors = self.get_neighbors(idx)
if neighbors.sum() >= self.MinPts:
for i, is_neighbor in enumerate(neighbors):
if not is_neighbor:
continue
self.expand(i)

def fit(self, points: np.array):
self.points = points
self.group = np.zeros(points.shape[0], dtype=np.int32)
for idx, p in enumerate(self.points):
if self.group[idx] != 0:
continue
neighbors = self.get_neighbors(idx)
if neighbors.sum() >= self.MinPts:
self.expand(idx)
self.group_counter += 1
return self.group

# 随机生成二维坐标点
points = np.random.rand(150, 2) * 100

# 调参比较效果
grp = Dbscan(eps=10, MinPts=5).fit(points)
plt.scatter(points[:, 0], points[:, 1], c=grp)
plt.show()

# 邻域中要求的点数目越多,形成的聚簇数目越少
grp = Dbscan(eps=10, MinPts=6).fit(points)
plt.scatter(points[:, 0], points[:, 1], c=grp)
plt.show()

eps=10, MinPts=5输出

eps=10, MinPts=6输出

事务

事务是一系列操作组成的逻辑工作单位,事务中的操作只能全部成功或全部失败。

ACID

事务有4个特征

  • Atomicity:原子性,事务中的操作要么全部成功,要么全部失败且不更新数据
  • Consistency:一致性,数据库状态从一个状态转换到另一个状态
  • Isolation:隔离性,在处理数据时一个事务不能被其他事务干扰,不同事务之间并发运行互不影响
  • Durability:事务一旦完成,对数据库的影响是永久的,即使数据库故障也不会丢失数据

数据库引擎

  1. InnoDB
  • 支持事务,满足ACID
  • 支持行级锁
  • 只有InnoDB支持Foreign key
  • 并发性能高
  • B+树作为索引
  • 不保存行数
  1. Mylsam
  • 查询快

左值,右值

  • 左值可以位于等号左边,可以取左值的地址
  • 右值只能位于等号右边,不能取右值地址

左值引用,右值引用

  • 左值引用形式为 int &a = b;,a是b的别名,具有相同地址,只在创建时引用其他左值
  • 右值引用形式为 int &&a = 3;
  • 常量左值引用也可以 const int &a = 3;

std::move()

std::move()的功能是将传入的左值强制转换为右值返回。

在STL的许多容器中,都定义了移动语义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class A {
public:
A(const A& _a) {} // 拷贝构造
A& operator=(const A& _a) {} // 赋值
A(A&& _a) {} // 移动构造
A& operator=(A&& _a) {}// 移动赋值
};

int main() {
A a1, a2;
a1 = A(std::move(a2)); // 调用了移动构造
a1 = std::move(a2); // 调用了移动赋值
exit(0);
}

STL中移动语义可以在某些情况下避免拷贝内存,提升性能,但是一般在move并赋值之后,被移动的对象会清空,相当于调用了默认构造函数。

平衡二叉树

性质:

  • 每个节点最多有2个子节点
  • 左右子树高度差不超过1
  • 当前节点值大于左孩子,小于右孩子

缺陷:每次插入、删除都需要大量的左旋右旋操作

红黑树

红黑树弥补了平衡二叉树插入删除的问题

性质:

  • 根节点为黑色
  • 红节点的子节点必为黑色
  • 从根节点到任意一个节点,包含相同数目的黑色节点

STL中红黑树(map, set)的迭代器实现:

  1. 第一个节点是树中最小的节点
  2. 如果存在右子树,则下一个节点是右子树的最小节点
  3. 如果不存在右子树,则向上寻找。找到一个节点其右节点未被遍历过,则这个节点是下一个节点,找不到意味着完成遍历

整体过程类似中序遍历

B树与B+树

B树是一种多路查找树,节点中有多个key,表示子节点值的区间。插入与删除时,会改变节点中key的数目

B+树:

  • 只有叶子节点包含数据
  • 每个非叶子节点的key数目相同,插入删除时不改变非叶子节点数目
  • 叶子节点用一个链表串起来,方便快速遍历

与红黑树比较:B树/B+树时多叉的,查询时间复杂度都为O(logn),不过当数据块在磁盘上时,B+树的磁盘IO数目更少,应为用链表串起来了

虚拟内存

  • 不同进程之间通过虚拟内存隔离
  • CPU通过连续的虚拟地址访问物理地址
  • 虚拟内存大小可以比当前空闲物理内存大

页表

虚拟地址到物理地址的映射,由操作系统维护

页表访问失败:

  1. 访问的地址不在虚拟地址中,出现段错误
  2. 访问的地址还没有被映射为物理地址,或者被置换出物理内存,出现缺页中断,需要为其分配内存,更新页表

中断

软中断

软件产生的中断,例如进程调度,缺页中断等

硬中断

由硬件产生的中断,例如磁盘,网卡等等

进程切换 线程切换

进程切换开销:

  • 切换虚拟内存(栈,堆,bss,全局数据,代码段)
  • 切换硬件上下文,例如寄存器等
  • 调度器执行

线程切换开销:

  • 线程的栈
  • 调度器执行

虚拟内存切换十分慢,因此线程切换开销远小于进程切换开销

生产者消费者模型

互斥锁,信号量

sort使用的排序算法

  • 数据量大时使用快速排序
  • 数据量小时使用插入排序
  • 递归层数很深时使用堆排序。递归层数深可能时随机分区不规律引起的。

四种类型转换

static_cast

  • 基础数据类型之间的转换
  • 任意类型指针与void *之间的转换
  • 父子类之间的转换,无类型检查

const_cast

非常量转换为常量

dynamic_cast

父子类之间转换,有类型检查。

reinterpreted_cast

任意类型转换,不抛出异常

四种智能指针

auto_ptr

C++11中已弃用

unique_ptr

只能有一个指针有对象所有权。用构造函数或std::move()来转移所有权

shared_ptr

有多个指针可以有对象所有权,当所有指针都销毁时,销毁对象

weak_ptr

必须配合shared_ptr使用,能访问对象,但不具备所有权,解决了循环引用问题

运行原理

1
2
A *p = new A();
delete p;

调用顺序:

  1. operator new申请空间,一般STL实现中new申请堆内存,可重载为自定义的空间
  2. 调用A的constructor A(),初始化内存
  3. 调用A的deconstructor ~A(),析构内存
  4. operator delete释放由new申请的空间

newmalloc()

[区别]

TCP协议

建立连接

建立连接一般由客户端发起,共3步:

  • 客户端发送SYN j
  • 服务端回复SYN k, ACK j +1,客户端收到后客户端认为连接建立
  • 客户端回复 ACK k + 1,服务端收到后服务端认为连接建立

图片来自《UNP》

终止连接

终止连接两端都可以主动发起,假设A主动向B发起,共4步:

  • A发送FIN M
  • B回复ACK M + 1,B关闭读,A关闭写
  • B发送FIN N
  • A回复ACK N + 1 B关闭写,A关闭读

图片来自《UNP》

状态转移

客户端

初始为CLOSED

  1. SYN_SENT: 发送SYN
  2. ESTABLISHED:收到ACK,发送SYN ACK
  3. FIN_WAIT_1:发送FIN,主动关闭
  4. FIN_WAIT_2:收到ACK
  5. TIME_WAIT:收到FIN,发送ACK
  6. CLOSED:超时

服务端

初始为CLOSED

  1. LISTEN:被动打开
  2. SYN_RCVD:收到SYN,发送ACK
  3. ESTABLISHED:发送SYN ACK
  4. CLOSE_WAIT:收到FIN,发送ACK,被动关闭
  5. LAST_ACK:发送FIN
  6. CLOSED:收到ACK

图片来自《UNP》

TCP可靠性机制

  1. 序列号、确认应答、超时重传
    每个数据包有序列号,如果没收到确认,发送方在超时后会重传

  2. 滑动窗口
    窗口内的数据包都可以立刻发送,最早发送的包被确认后,窗口向前滑动

  3. 拥塞控制
    慢启动:窗口初始大小为1,每次收到确认,窗口大小乘2
    拥塞避免:设置窗口大小阈值,达到阈值后,不再乘2,改为增加1;发生超时重传时,阈值除以二,窗口设置为1,重新慢启动

进程间通信

有五种进程间通信的方式:

  • 管道
  • FIFO
  • 消息队列
  • 信号量
  • 共享存储器

管道

管道是进程间通信的一种方式,普通的管道只能在父进程与子进程之间通信。

pipe

pipe需要传入两个文件描述符fd,其中pipefd[0]用于读,pipefd[1]用于写。

父进程fork子进程后,内存也被复制了一份,已打开的管道仍然是能相互通信的。

一般fork之后,进程关闭两个fd中的一个,留下另一个用于通信。

1
2
#include <unistd.h>
int pipe(int pipefd[2]);

popen pclose

用于执行一个shell命令,同时返回的文件描述符连接到那个shell命令的stdinstdout

type = "r",则连接到命令的stdouttype = "w"则连接到stdin

1
2
3
#include <stdio.h>
FILE *popen(const char *command, const char *type);
int pclose(FILE *stream);

unix中调用date命令,可以获取当前时间,并格式化字符串:

1
2
3
4
5
6
7
8
9
10
11
12
string date_string;
char buf[128];
int n;
FILE *pf = popen("date +%c", "r");
while ((n = fread(buf, sizeof(char), 127, pf)) > 0) {
buf[n] = '\0';
date_string += string(buf);
}
fclose(pf);
// date_string 最后会有一个换行符'\n'
cout << date_string;
// Fri Jun 25 17:31:24 2021

FIFO(命名管道)

命名管道可用于两个无关的进程间通信。

机制同pipe,pathname指定了FIFO的路径,也是命名管道的名称。

mode与系统调用open一样,可指定读写等。

1
2
3
#include <sys/types.h>
#include <sys/stat.h>
int mkfifo(const char *pathname, mode_t mode);

消息队列

消息的链表,由内核维护,有最大容量

信号量

信号量保证一定数量的进程能够访问临界区。二元信号量类似互斥锁,不过是在进程间互斥。

信号量由内核维护。

共享存储器

也叫共享内存。共享内存效率非常高,因为内存访问速度一般很快。进程间共享内存也会产生读写同步问题,因此需要信号量来保护共享内存。

select

select函数,可以传入想观察的fd_set类型的三个集合,分别表示读、写、异常的fd。nfds表示监听的最大fd值+1,可以设置为FD_SETSIZE表示最大值。

返回已就绪的fd数量,它是三个集合中已就绪的fd数之和。

select对于n个fd,其时间复杂度为O(n)

1
2
3
 #include <sys/select.h>
int select(int nfds, fd_set *readfds, fd_set *writefds,
fd_set *exceptfds, struct timeval *timeout);

poll

poll函数与select类似,不过不分成3个fd集合,而合并成一个pollfd结构。event表示关心的事件,例如读、写。revent表示返回的事件,其中除了包含关心的时间外,还包含了fd是否出错、挂断、是否打开一个文件等。

poll同样具有O(n)时间复杂度

1
2
3
4
5
6
7
8
#include <poll.h>
int poll(struct pollfd *fds, nfds_t nfds, int timeout);

struct pollfd {
int fd; /* file descriptor */
short events; /* requested events */
short revents; /* returned events */
};

epoll

select poll 都采用轮询fd的方式确认是否有IO准备就绪,在网络中,如果fd数量非常多,则效率比较低下。

epool中,每个fd对应一个回调函数,当IO就绪时,对应的fd调用回调函数,将fd加入一个链表,epoll会检查这个链表,若有fd已就绪,则在epoll_wait函数处返回。

epoll有两种模式

  • LT模式下,fd就绪,被读取后,如果fd中还有未读完的信息,则epoll会将它放回链表,下次还会报告这个fd
  • ET模式,fd就绪,被读取后,就算有未读完的信息,epoll也不再监听这个fd,因此必须每次读完fd中的内容。这种方式效率更高。

epoll示例

可以接受多个TCP请求,并输出每个连接中读出的内容。

  • 使用了ET模式,客户端socket必须为非阻塞模式
  • struct events中data成员可以理解为每个fd的上下文,在代码中将其设置为指针,指向堆中的struct Context。必须注意连接关闭后,delete掉对应内存。

结构体的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
struct epoll_event
{
uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
}

typedef union epoll_data
{
void *ptr;
int fd;
uint32_t u32;
uint64_t u64;
} epoll_data_t;
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
#include <sys/epoll.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <fcntl.h>
#include <unistd.h>
#include <signal.h>

#include <string>

#define MAX_EVENTS 16
#define READ_SIZE 4096

int epollfd;

static void sigint_handler(int signo) {
printf(" %d received.\n", signo);
close(epollfd);
exit(0);
}

// 每个fd所关联的上下文
typedef struct Context {
std::string ip;
uint16_t port;
int fd;
Context(const std::string &_ip, uint16_t _port, int _fd) :
ip(_ip), port(_port), fd(_fd) {}
} Context;

int main(int argc, char * argv[]) {
int listen_sock, conn_sock, nfds;
struct epoll_event ev, events[MAX_EVENTS];

struct sockaddr_in sa;
sa.sin_family = AF_INET;
inet_pton(AF_INET, "0.0.0.0", &sa.sin_addr.s_addr);
sa.sin_port = htons(19000);

listen_sock = socket(AF_INET, SOCK_STREAM, 0);
if (-1 == bind(listen_sock, (struct sockaddr *)&sa, sizeof(sa))) {
perror("bind");
exit(EXIT_FAILURE);
}

if (-1 == listen(listen_sock, 1024)) {
perror("listen");
exit(EXIT_FAILURE);
}

// 来自epoll手册的建议框架
epollfd = epoll_create(MAX_EVENTS);
if (epollfd == -1) {
perror("epoll_create");
exit(EXIT_FAILURE);
}
ev.events = EPOLLIN;
ev.data.fd = listen_sock;
if (epoll_ctl(epollfd, EPOLL_CTL_ADD, listen_sock, &ev) == -1) {
perror("epoll_ctl: listen_sock");
exit(EXIT_FAILURE);
}

for (;;) {
int nfds = epoll_wait(epollfd, events, MAX_EVENTS, 300);
if (nfds == -1) {
perror("epoll_wait");
exit(EXIT_FAILURE);
}

for (int n = 0; n < nfds; ++n) {
if (events[n].data.fd == listen_sock) {
// 收到连接请求
struct sockaddr_in addr;
uint32_t addrlen = sizeof(addr);
conn_sock = accept4(listen_sock, (struct sockaddr *) &addr, &addrlen, SOCK_NONBLOCK);
if (conn_sock == -1) {
perror("accept");
exit(EXIT_FAILURE);
}

char charip[20];
inet_ntop(AF_INET, &addr.sin_addr.s_addr, charip, 20);
std::string ip(charip);
uint16_t port = ntohs(addr.sin_port);
printf("accept: %s:%d\n", ip.data(), port);
fflush(stdout);

ev.events = EPOLLIN | EPOLLET;
ev.data.ptr = (void *)new Context(ip, port, conn_sock);
if (epoll_ctl(epollfd, EPOLL_CTL_ADD, conn_sock, &ev) == -1) {
perror("epoll_ctl: conn_sock");
exit(EXIT_FAILURE);
}
} else if (events[n].events == EPOLLIN) {
// fd可读
Context *ctx = (Context *)events[n].data.ptr;
std::string row_request;
char buf[READ_SIZE];
int read_n;
while ((read_n = recv(ctx->fd, buf, READ_SIZE - 1, 0)) > 0) {
buf[read_n] = '\0';
row_request += std::string(buf);
}

if (row_request.size() == 0) {
// 读取大小为0代表客户端关闭
printf("%s:%u closed.\n", ctx->ip.data(), ctx->port);
fflush(stdout);
close(ctx->fd);
delete ctx;
} else {
printf("from %s:%u recv %lu bytes, content: %s\n", ctx->ip.data(), ctx->port,
row_request.size(), row_request.data());
fflush(stdout);
}
}
}
}
for (auto &e : events) {
if (e.data.ptr)
delete (Context *)e.data.ptr;
}
close(epollfd);

return 0;
}