DBSCAN算法实现
DBSCAN算法
支持二维坐标点聚类,参考:密度聚类算法DBSCAN
1 | import numpy as np |
eps=10, MinPts=5
输出
eps=10, MinPts=6
输出
支持二维坐标点聚类,参考:密度聚类算法DBSCAN
1 | import numpy as np |
eps=10, MinPts=5
输出
eps=10, MinPts=6
输出
事务是一系列操作组成的逻辑工作单位,事务中的操作只能全部成功或全部失败。
事务有4个特征
int &a = b;
,a是b的别名,具有相同地址,只在创建时引用其他左值int &&a = 3;
const int &a = 3;
std::move()
std::move()
的功能是将传入的左值强制转换为右值返回。
在STL的许多容器中,都定义了移动语义:
1 | class A { |
STL中移动语义可以在某些情况下避免拷贝内存,提升性能,但是一般在move
并赋值之后,被移动的对象会清空,相当于调用了默认构造函数。
性质:
缺陷:每次插入、删除都需要大量的左旋右旋操作
红黑树弥补了平衡二叉树插入删除的问题
性质:
STL中红黑树(map, set
)的迭代器实现:
整体过程类似中序遍历
B树是一种多路查找树,节点中有多个key,表示子节点值的区间。插入与删除时,会改变节点中key的数目
B+树:
与红黑树比较:B树/B+树时多叉的,查询时间复杂度都为O(logn)
,不过当数据块在磁盘上时,B+树的磁盘IO数目更少,应为用链表串起来了
虚拟地址到物理地址的映射,由操作系统维护
页表访问失败:
软件产生的中断,例如进程调度,缺页中断等
由硬件产生的中断,例如磁盘,网卡等等
进程切换开销:
线程切换开销:
虚拟内存切换十分慢,因此线程切换开销远小于进程切换开销
互斥锁,信号量
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 | A *p = new A(); |
调用顺序:
operator new
申请空间,一般STL实现中new
申请堆内存,可重载为自定义的空间constructor A()
,初始化内存deconstructor ~A()
,析构内存operator delete
释放由new
申请的空间new
与malloc()
建立连接一般由客户端发起,共3步:
图片来自《UNP》
终止连接两端都可以主动发起,假设A主动向B发起,共4步:
图片来自《UNP》
初始为CLOSED
初始为CLOSED
图片来自《UNP》
序列号、确认应答、超时重传
每个数据包有序列号,如果没收到确认,发送方在超时后会重传
滑动窗口
窗口内的数据包都可以立刻发送,最早发送的包被确认后,窗口向前滑动
拥塞控制
慢启动:窗口初始大小为1,每次收到确认,窗口大小乘2
拥塞避免:设置窗口大小阈值,达到阈值后,不再乘2,改为增加1;发生超时重传时,阈值除以二,窗口设置为1,重新慢启动
有五种进程间通信的方式:
管道是进程间通信的一种方式,普通的管道只能在父进程与子进程之间通信。
pipe
需要传入两个文件描述符fd
,其中pipefd[0]
用于读,pipefd[1]
用于写。
父进程fork
子进程后,内存也被复制了一份,已打开的管道仍然是能相互通信的。
一般fork
之后,进程关闭两个fd
中的一个,留下另一个用于通信。
1 | #include <unistd.h> |
用于执行一个shell命令,同时返回的文件描述符连接到那个shell命令的stdin
或stdout
。
若type = "r"
,则连接到命令的stdout
;type = "w"
则连接到stdin
。
1 | #include <stdio.h> |
unix中调用date
命令,可以获取当前时间,并格式化字符串:
1 | string date_string; |
命名管道可用于两个无关的进程间通信。
机制同pipe,pathname
指定了FIFO的路径,也是命名管道的名称。
mode
与系统调用open
一样,可指定读写等。
1 | #include <sys/types.h> |
消息的链表,由内核维护,有最大容量
信号量保证一定数量的进程能够访问临界区。二元信号量类似互斥锁,不过是在进程间互斥。
信号量由内核维护。
也叫共享内存。共享内存效率非常高,因为内存访问速度一般很快。进程间共享内存也会产生读写同步问题,因此需要信号量来保护共享内存。
select
函数,可以传入想观察的fd_set
类型的三个集合,分别表示读、写、异常的fd。nfds
表示监听的最大fd值+1,可以设置为FD_SETSIZE
表示最大值。
返回已就绪的fd数量,它是三个集合中已就绪的fd数之和。
select对于n
个fd,其时间复杂度为O(n)
1 | #include <sys/select.h> |
poll
函数与select
类似,不过不分成3个fd集合,而合并成一个pollfd
结构。event
表示关心的事件,例如读、写。revent
表示返回的事件,其中除了包含关心的时间外,还包含了fd是否出错、挂断、是否打开一个文件等。
poll
同样具有O(n)
时间复杂度
1 | #include <poll.h> |
select poll
都采用轮询fd的方式确认是否有IO准备就绪,在网络中,如果fd数量非常多,则效率比较低下。
epool中,每个fd对应一个回调函数,当IO就绪时,对应的fd调用回调函数,将fd加入一个链表,epoll会检查这个链表,若有fd已就绪,则在epoll_wait
函数处返回。
epoll有两种模式
可以接受多个TCP请求,并输出每个连接中读出的内容。
struct events
中data成员可以理解为每个fd的上下文,在代码中将其设置为指针,指向堆中的struct Context
。必须注意连接关闭后,delete
掉对应内存。结构体的定义:
1 | struct epoll_event |
1 | #include <sys/epoll.h> |