大三寒假学习记录

2021年2月1日-3日

动态规划问题

编辑距离

最长递增子序列

俄罗斯套娃信封

最大子序和

最长公共子序列

2021年2月4日22:46:59

今天把博客整理了下分类

继续学习的动态规划算法两道题目

583. 两个字符串的删除操作

712. 两个字符串的最小ASCII删除和

2021年2月4日23:26:37 https://learngitbranching.js.org/?locale=zh_CN 学习Git的挺不错的网站 练习一遍

2021年2月5日11:18:56

上次改了改项目的BUG, 发布了1.1 release版本

继续算法

516. 最长回文子序列

整了一大下午 没想到是memcpy 的问题总算解决了虚拟机代码无法运行的问题

2021年2月20日

C++ 拷贝构造函数和赋值运算符 https://www.cnblogs.com/wangguchangqing/p/6141743.html

allocate deallocate
malloc free
new delete

STL allocate deallocate constructor deconstructor
std allocate

我理解的右值引用、移动语义和完美转发 https://www.jianshu.com/p/d19fc8447eaa

内存布局

TODO 异步回调 sync

TODO 聊聊同步、异步、阻塞与非阻塞 https://my.oschina.net/xianggao/blog/661085

多线程 多进程
同步 mutex线程锁, 条件变量, 信号量(生产者消费者) PV操作
数据共享 共享内存, 消息队列, 管道,

信号量可以设置多个初始资源 等多个初始资源消耗完毕后才会sleep

条件变量则是直接sleep等待一个个或者全部唤醒

https://blog.csdn.net/linraise/article/details/12979473

2021年2月22日 - AC5

更加的透彻 https://codinfox.github.io/dev/2014/06/03/move-semantic-perfect-forward/

移动语义和完美转发

移动构造函数
可以将源对象中的高消耗资源 转移到 新的对象中

而使用拷贝构造函数会导致生成两份高消耗资源 造成浪费

左值 右值
能够取到地址的为左值 否则是右值

std::move std::forward
move将一个左值T转换为右值 以此来调用对象的移动构造函数 转移内部资源, 否则由于T是左值将会调用拷贝构造函数 生成新的资源 浪费旧的资源

forward左值依然为左值 右值转换为右值. 当一个参数传入右值形参的时候 函数的实参实际为左值 使用forward可以将函数实参转换原本的右值

而当传入左值的时候forward转换后依旧是左值

void Foo(const int&)
在没有其他重载的情况下, const int&可以接收左值也可以接收右值 如果去掉const则只能接收右值

每个线程都是如何启动的, 各个线程的作用. 线程间的数据交互方式

TODO unique_lock lock_guard scope_lock lock 等的作用

条件变量虚假唤醒

整理了jsoncpp的代码明天看

2021年2月23日 - AC5

https://github.com/HiganFish/jsoncpp1.9.4-learn jsoncpp代码阅读

lower_bound + insert 比 find + insert 要高性能

insert会利用lower_bound的返回值

而find则没有此效果 总是需要进行O(log N)的查找位置

EventLoop* EventLoopThread::Start()
{
thread_.Start();

EventLoop* loop = nullptr;
{
MutexGuardLock guard(mutex_);
while (loop_ == nullptr)
{
cond_.Wait();
}
loop = loop_; // 为了等线程创建完毕后 才返回 否则这个函数只有第一句 线程未创建完毕就返回了
}
return loop;
}

void EventLoopThread::ThreadFunc()
{
EventLoop loop;
{
MutexGuardLock guard(mutex_);
loop_ = &loop;
cond_.WakeUpOne();
}
}

2021年2月24日

typename and class in template

class D
{
public:
typedef int INT;
};

template <class T> // mingw中和 template <typename T> 完全等效 必须在 T::INT 前加typename
class D1
{
public:
T::INT i1; // error: need 'typename' before 'T::INT' because 'T' is a dependent scope
typename T::INT i2; // true
};

int main()
{
D1<D> d_1;
}

额外发现

template <class T>
class A
{
public:
T t_;
};

template <class T>
class A1 : public A<T>
{
public:
A1()
{
// t_ = 1;
this->t_ = 1; // 这里需要使用this指针访问
A<T>::t_ = 1; // 可读性更好
}
};

二段名字查找

  1. 第一段: 模板定义阶段 在被定义时 只在模板中有独立的名字(和模板参数无关) 参与查找
  2. 第二段: 模板类实例化 非独立的名字参与查找

以成员变量为例 成员函数同理

  1. 在第一阶段, 首先处理A1遇到了class A1 : public A<T>. 此时父类A<T>依赖于模板参数 属于非独立 不参与查找

  2. 在之后遇到了t_这个变量, 由于没有查找基类 这里便认为t_是一个非成员变量

  3. 第二阶段这时候才处理A<T> 虽然这时已经可以知道t_是一个成员变量但是第一阶段编译器已经认定了t_是一个非成员变量

  4. 而对于一个非成员变量 编译器认为不需要去基类中查找, 所以就报错无法找到

  5. 使用this之后在第一阶段, 编译器就被明确的告知t_是一个成员变量

  6. 然后第二阶段, 编译器就会去基类中查找这个成员变量.

https://www.cnblogs.com/onepixel/articles/7674659.html

2021年2月25日 - AC1

开学了坐了一天车

A了一道题-_-

2021年2月26日 - AC6

偶然看到了一道面试题, 问的是如何从2.5亿数字中找到重复的数字

https://leetcode-cn.com/circle/discuss/6TtGra/

大佬云集..

TODO likely宏和__builtin_expect编译器函数性能评测

TODO string_view https://cloud.tencent.com/developer/article/1479005

void (TcpConnection::*fp)(const std::string_view&) = &TcpConnection::SendInLoop;
loop_->RunInLoop(std::bind(fp,
this,
std::string(data, length))); // OK

TcpConnection::SendInLoop;
loop_->RunInLoop(std::bind(&TcpConnection::SendInLoop,
this,
std::string(data, length)));

loop_->RunInLoop([this, str = std::string(data, length)]()
{
RunInLoop(str);
}); // HOW TO FIX ERROR ???

看到C++ Primer中一句话终于知道为什么第二种是错误的了, 因为存在函数重载, 所以必须显示的声明使用的是哪个函数

make_unique make_shared
使得对象空间和unique_ptr或者shared_ptr的控制块是连续的

TODO Warning: File “xxx” has modification time yyy s in the future

mutable

std::vector<EventLoopFunction> pending_func;
{
/**
* 减少锁持有的时间
*/
MutexLockGuard guard(pending_func_mutex_);
pending_func.swap(pending_func_);
}

Linux下查看进程线程数

lsof -Ptn -i tcp:4100 # -P 不解析port -n 不解析主机名 会解决lsof卡gethostbyaddr -t 只显示pid

pid=$(lsof -Pnt -i tcp:4100)

cat /proc/$pid/status | grep Threads
Threads: 5

top -Hp $pid # H 线程模式
107344 root 20 0 334464 6780 5192 S 0.0 0.2 0:00.74 LiveBroadcastSe
107361 root 20 0 334464 6780 5192 S 0.0 0.2 0:23.11 LiveBroadcastSe
107362 root 20 0 334464 6780 5192 S 0.0 0.2 0:00.70 LiveBroadcastSe
107363 root 20 0 334464 6780 5192 S 0.0 0.2 0:04.76 LiveBroadcastSe
107364 root 20 0 334464 6780 5192 S 0.0 0.2 0:04.79 LiveBroadcastS

pstree -p $pid
LiveBroadcastSe(107344)─┬─{LiveBroadcastSe}(107361)
├─{LiveBroadcastSe}(107362)
├─{LiveBroadcastSe}(107363)
└─{LiveBroadcastSe}(107364)

2021年2月27日 - AC5

TODO 手写最小堆

刚才看堆的用法的时候嫖到了一眼可以用最大堆+最小堆求中位数 没想到下道题就用到了…

连着两道算法做的头皮发麻, 写会项目

日志库写完了

/var/lib/systemd/coredump coredump默认目录

2021年2月28日 - AC5

TODO 自我介绍

把项目换成了新的日志库

TODO getaddrinfo

2021年3月1日 - AC2

HTTPS流程和基本原理

HTTPS https://segmentfault.com/a/1190000021494676

如果使用对称加密, 虽然传输过程中数据不会被解密 但是双方在交换密钥的时候 是明文进行交换的

所以使用非对称加密来保护对称加密的key 后续再使用对称加密进行通信 这样兼顾安全性和效率

HTTP的默认端口从80改到了443端口

客户端首先生成随机串CLIENT1, 服务器接收到后回复证书和SERVER1, 客户端验证证书后生成随机串CLIENT2并使用公钥加密, 服务器收到后解密出CLENT2

然后客户端和服务器根据上面的三个随机串使用相同的算法生成最终的对称加密密钥

对于证书合法性校验, 存在中间人攻击 如何解决的? https://zhuanlan.zhihu.com/p/43789231

服务器向CA申请证书后 得到了一份证书以及CA在hash证书后使用私钥对其加密的数字签名两个东西组成数字证书

当浏览器得到数字证书后可以从中得到证书数字签名 使用CA的公钥对数字签名解密得到T1. 然后使用证书中的算法对证书hash得到T2 比较T1T2

二者相等说明证书可信.

如果有人篡改了证书, 但是由于没有CA的私钥无法生成加密后的数字签名, 所以浏览器比较的时候T1和T2不相等

如果掉包整个证书, 由于证书中包含了域名, 直接比对域名就知道有没有被掉包了

五大I/O模型比较

同步IO

  • 阻塞IO: 数据就绪和数据拷贝均阻塞
  • 非阻塞IO: 数据就绪不阻塞 数组拷贝阻塞 内核仅通知数据就绪(非就绪需要一直轮询)
  • IO复用: 数据就绪不阻塞 数据拷贝阻塞 内核仅通知数据就绪
  • 信号驱动IO 数据就绪不阻塞 数据拷贝阻塞 内核仅通知数据就绪

异步IO

  • 异步IO: 数据就绪 和 数据拷贝 均不阻塞 内核通知数据拷贝完毕

poll相对select 增加了文件描述符的复用率和监听数量 需要每次奖所有描述符从进程复制到内核

epoll 则不在需要在每次调用epoll_wait时将所有描述符从进程复制到内核

epoll支持LT模式(通知直到数据被处理 水平模式) ET模式(仅通知一次 边缘模式)

select的精度高 可移植性好

poll同样可以执行好 相对select解决了一些问题

epoll 只能在Linux下使用, 如果连接数较少或者都是短连接 会使用epoll_ctl导致性能降低 epoll更加适用于长连接的管理

2021年3月2日 - AC2

dup2(fd, STDOUT_FILENO) 在exel系列函数执行前 执行这条语句可以将输出直接重定向到fd

https://github.com/HiganFish/Notes-CSAPP csapp TinyWebServer 总算写完了 format库用起来非常舒服 也练了练string中的CApi

C++协程库 (2021年3月3日15:46:37)

智能指针的实现 (2021年3月3日15:46:41)

2021年3月3日1 - AC2

尝试试用了下协程库

简单实现了下 智能指针150行不到的代码

2021年3月4日 - AC2

Protobuf相关原理

syntax = "proto2";

package tutorial;

message Person {
optional string name = 1;
optional int32 id = 2;
optional string email = 3;

enum PhoneType {
MOBILE = 0;
HOME = 1;
WORK = 2;
}

message PhoneNumber {
optional string number = 1;
optional PhoneType type = 2 [default = HOME];
}

repeated PhoneNumber phones = 4;
}

message AddressBook {
repeated Person people = 1;
}

protobuf编码数据后会生成字节流 组成方式为[key1][value1][key2][value2][key3][value3]....

如果需要了无法解析的kv就跳过, 所以旧版本代码依然能解析新版的字节流

key1=(key << 3) | type 这个type是proto中各种类型的代号. 这样就能通过增加有限的二进制位同时存储代号和类型 存储在一起也方便解析

value1则会根据不同的value类型进行对应形式的压缩. 对于变长类型会压缩其二进制位 比如int32 为 1的时候仅需要一个字节就好 字节之间通过首字节判断是否相连如果每个字节的

首二进制位是1说明后续依然有数据 直到首二进制位为0说明数据结束 这样就获取到了数字信息. 对于string类型则采用了length + char流没有对char流进行压缩


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。