STL

[TOC]

priority_queue

大根堆(top是max)优先队列

priority_queue<int, vector<int>, greater<int>> q; // 小根堆

top
push 和 pop
empty size
emplace(1,1) // priority_queue<PII> q;
// 相当于 push({1,1}) 

deque

双端队列:首尾都可以插入删除

应用:二叉树层次遍历

empty()
size()
front() 和 back()
push_front(x) 和 push_back(x)
pop_front() 和 pop_back()

unordered

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表

不支持 lower_bound()/upper_bound(), 迭代器的++,–

set

不允许重复,升序

erase(x) // 删除所有x或迭代器it
count() 
find() // set.find(1) == set.end() 没找到
lower_bound(x) 大于等于x的最小的数的it
upper_bound(x) 大于x的最下的数的it

multiset

允许重复,升序

map

<key, value> 根据key升序,key不允许重复

find
erase(pair)
[]
lower_bound 和 upper_bound

multimap

<key, value> 根据key升序,key允许重复

bitset

bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]

count()  返回有多少个1

any()  判断是否至少有一个1
none()  判断是否全为0

set()  把所有位置成1
set(k, v)  将第k位变成v
reset()  把所有位变成0
flip()  等价于~
flip(k) 把第k位取反

vector

支持按字典序比较运算

size
empty
clear
front 和 back
push_back 和 pop_back
insert emplace
[]

二维

vector<vector<int>> g(N,vector<int>(N,-1)); // 初始化为-1(N*N大小)

stack

top
push 和 pop

queue

front 和 back
push 和 pop

pair

升序?

unique

序列中不重复的相邻元素(即与前一个数不同)放在前面,需要先排序

int arr[] = {3,2,2,1,4}, n = sizeof arr/ sizeof 1;
for (int a : arr) cout<<a<<' ';
// 3 2 2 1 4 
sort(arr, arr+n);
// 1 2 2 3 4
n = unique(arr, arr+n) - arr;
for (int a : arr) cout<<a<<' ';
// 1 2 3 4 4
for (int i = 0; i < n; i++) cout<<arr[i]<<' ';
// 1 2 3 4 

greater

sort priority_queue
greater 从大到小 小顶堆
less 从小到大 大顶堆
ACM经验

优化

#pragma GCC optimize ("O1")
#pragma comment(linker, "/STACK:1024000000,1024000000")
//防止爆栈
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define r(i,a,b) for(int i=a,i<b;i++)
using ll = long long;
using namespace std;
const int N=100;
inline int read() {
    int s = 0, w = 1;//s是数值,w是符号
    char ch = getchar();
    while (ch < '0' || ch > '9') {//将空格、换行与符号滤去
        if (ch == '-') {//出现负号表示是负数
            w = -1;
            ch = getchar();//继续读入
        }
    }
    while (ch >= '0' && ch <= '9'){ //循环读取每一位的数字
        s = s * 10 + ch - '0';//将每一位的结果累加进s
        ch = getchar();
    }
    return s * w;//乘上符号
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}

编译器优化

-O0 表示无优化状态

-O1 表示对代码进行了优化

-O2 表示减小目标文件大小

-O3 表示减小代码段及栈空间的大小

#pragma GCC optimize (“O0”)

爆栈

#pragma comment(linker, “/STACK:1024000000,1024000000”)

全局变量自动初始化

ios::sync_with_stdio(false); // 关闭C++输入输出缓冲区同步
cin.tie(0); // 绑定缓冲区

关闭后cin不能与scanf,sscanf, getchar, fgets等混用,cout不能与printf,puts等混用

使用ios...和tie 130 ms
只使用ios... 676 ms
只使用tie 315 ms
无优化 885 ms

快读快出

scanf

scanf(“%控制格式”, &变量地址); 对于数组 变量本身就是地址

格式 字符意义
d 十进制整数
o 八进制整数
x 十六进制整数
u 无符号十进制整数
f或e 实型数(用小数形式或指数形式)
c 单个字符
s 字符串
l/h l表示长,h表示短,Eg:lf 读入doble
* 读入不赋值,EG:*d 读入int但不赋值
5(数字) 读入宽度
-/+ 左/右对齐
# 需要时给出小数点和前缀o或 0x
空格 需要时显示正负号

没有精度控制 scanf(“%5.2f”,&a);是非法的

要求给出变量地址 scanf(“%d”,a);是非法的

在碰到空格,TAB,回车或非法数据时认为该数据结束

printf

printf(“%控制格式”, 变量本身);

%a(%A) 浮点数、十六进制数字和p-(P-)记数法(C99)
%c 字符
%d 有符号十进制整数
%f 浮点数(包括float和double)
%e(%E) 浮点数指数输出[e-(E-)记数法]
%g(%G) 浮点数不显无意义的零”0”
%i 有符号十进制整数(与%d相同)
%u 无符号十进制整数
%x(%X) 十六进制整数0f(0F) e.g. 0x1234
%p 指针
%% “%”

读入空格

cin.get(x) 读入单个char

x = getchar( ) 读入单个char,对应putchar( ) 输出单个char

getline(x) 读入string

内联函数read

内联是将代码内嵌到调用者代码处

inline int read() {
    int s = 0, w = 1;//s是数值,w是符号
    char ch = getchar();
    while (ch < '0' || ch > '9') {//将空格、换行与符号滤去
        if (ch == '-') {//出现负号表示是负数
            w = -1;
            ch = getchar();//继续读入
        }
    }
    while (ch >= '0' && ch <= '9'){ //循环读取每一位的数字
        s = s * 10 + ch - '0';//将每一位的结果累加进s
        ch = getchar();
    }
    return s * w;//乘上符号
}

内联函数write

void write(int v) {
    if (v<0) {
        putchar('-');
        v=-v;
    }
    if (v>9) write(v/10);
    putchar(v%10+'0');
}
puts(""); //换行 

位运算

2^n 可以用 1<<n 来计算

异或 ^

时间复杂度

  1. n30, 指数级别, dfs+剪枝,状态压缩dp
  2. n100 => O(n3),floyd,dp,高斯消元
  3. n1000 => O(n2)O(n2logn),dp,二分,朴素版Dijkstra、朴素版Prim、Bellman-Ford
  4. n10000 => O(nn),块状链表、分块、莫队
  5. n100000 => O(nlogn) => 各种sort,线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
  6. n1000000 => O(n), 以及常数较小的 O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集,kmp、AC自动机,常数比较小的 O(nlogn) 的做法:sort、树状数组、heap、dijkstra、spfa
  7. n10000000 => O(n),双指针扫描、kmp、AC自动机、线性筛素数
  8. n109 => O(n),判断质数
  9. n1018 => O(logn),最大公约数,快速幂,数位DP
  10. n101000 => O((logn)2),高精度加减乘除
  11. n10100000 => O(logk×loglogk)k,高精度加减、FFT/NTT
Pytorch

加载数据类

获取数据和其对应的label值、总共有多少数据

from torch.utils.data import Dataset

GPU训练

将输入、输出、模型、损失函数都移到cuda上

设置环境变量

必须在import torch之前键入以下代码

import os
os.environ['CUDA_VISIBLE_DEVICES'] = '3'

然后都移动到cuda上

x = x.cuda()
y = y.cuda()
model = model.cuda()
loss_function = loss_function.cuda()

使用todevice

device = torch.device("cuda:0" if torch.cuda.is_available() else "cpu")

model.to(device)

Tensorboard

from torch.utils.tensorboard import SummaryWriter


writer = SummaryWriter("logs")
# y = x+1
for i in range(100):
    writer.add_scalar("y=x",i+1,i)
writer.close()

生成一个logs文件夹,终端进入logs文件夹的同级目录,输入

tensroboard --logdir=logs --port 6007

计算模型体量

进度条

from tqdm import tqdm  # 直接import tqdm会报错

loop = tqdm(enumerate(train_dataloader), total=train_data_size)
for step, data in loop:
  pass

保存模型

包含GPU tensors的模型,自动load到GPU上

保存整个模型

## 保存模型
torch.save(model, MODEL_PATH)

## 读取模型
model = torch.load(MODEL_PATH)

只保存参数

## 保存模型
torch.save(model.state_dict(), MODEL_PATH)
torch.save(optimizer.state_dict(), OPTIM_PATH)

## 读取模型
if os.path.exists(MODEL_PATH)
    model.load_state_dict(torch.load(MODEL_PATH))
if os.path.exists(OPTIM_PATH)
  optimizer.load_state_dict(optimizer.state_dict(), OPTIM_PATH)
Linux常见问题

[TOC]

进程

ll /proc/<pid>

kill -9 <pid>

网络测试

curl <url>

ping <ip>
ping -i <ip> <port>

lsof -i <port>

pip

pip show 包名
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple 包名

bash脚本

等号两边无空格

.bashrc和.bash_profile的区别

.bash_profile是在登陆的时候才会执行的,也叫.bash_login,在命令行再运行bash命令的时候不执行这个文件里面的命令。

.bashrc恰好相反,是在执行子shell(sub-shell)的时候才会执行里面的命令,可以通过source ~/.bashrc执行。

在.bash_profile中加入下面的代码,可以在登录时执行.bashrc里的代码,注意空格

if  [ -f ~/.bashrc ]; then
        . ~/.bashrc
        echo ".bash_profile call .bashrc"
fi

安装pytorch

正常清华源为anaconda | 镜像站使用帮助 | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror,其中不包含pytorch

添加pytorch清华源如下

  - https://mirrors.tuna.tsinghua.edu.cn/anaconda/cloud/pytorch/

vim无法保存

1、由于权限不够,即未使用sudo

2、用vim打开了一个目录,可以继续选择进入文件,打开文件后再退出

qa!可以退出,不能保存

CUDA命令

nvidia-smi
Perf Persistence-M Compute M Disp.A Uncorr. ECC Compute M
性能模式(P0到P12) 持续模式 计算模式 GPU的显示是否初始化 错误检查与纠正 计算模式

查看cuda版本 /usr/local/cuda/version.txt

查看配置和使用状态

nvidia-smi

top 监视进程

watch nvidia-smi 持续查看

free -m 查看存储空间

终端复用

screen

yum install -y screen  # 安装

screen -S 窗口名称  # 开启新的
Ctrl+A+C  # 在当前窗口开启新的窗口

Ctrl+A+D  # 非中断detached退出
按住Ctrl,依次再按a,d 可重连
按住Ctrl和a,放开a去按d 不可重连

Ctrl+A+K  # 杀掉当前

screen -r 窗口名称  # 恢复重连

exit  # 退出窗口

screen -X -S id号  # 杀死
screen -wipe  # 检查目前所有的screen作业,并删除已经无法使用的screen作业。

Tmux

启动tmux后,底部[0]表示第0个tmux伪窗口,再启动一个tmux伪窗口为[1]。

安装

# Ubuntu 或 Debian
$ sudo apt-get install tmux

# CentOS
$ sudo yum install tmux

常用命令

tmux ls

tmux attach -t 0  # 重连窗口

tmux detach  # 分离窗口
Ctrl+d或exit  # 退出Tmux窗口

tmux new -s <session-name>  # 新建有名字的窗口
tmux  # 用编号自动命名窗口

tmux kill-session -t <session-name>

conda

conda create -n 环境名 python=版本号
conda deactivate
conda info -e 或者 conda env list
conda remove -n 环境名 --all

Jupyter

由于服务器上必须

运行jupyter并强制指定执行程序内核为python

jupyter nbconvert --to notebook --execute --inplace 7.21CIFAR-10添加Dropout.ipynb --ExecutePreprocessor.kernel_name=python
深度学习Review【三】序列、RNN、LSTM(GRU)、DRNN

课程地址

一、序列模型

序列数据:实际中很多数据是随着时间变化而变化。

根据条件概率一直x1到xT的概率可以算出x的概率。
在这里插入图片描述
自回归模型:用的数据,预测现在的数据

马尔科夫假设

当前数据只和t个过去的数据相关
在这里插入图片描述

潜变量

引入潜变量h来表示过去的信息
绿色代表不同的潜变量h,每次在改变x后计算新的潜变量h
在这里插入图片描述

二、RNN 循环神经网络

适用于100以内的序列
用当前时刻的输入预测下一时刻的输出,“你好世界”,输出的“好”是由输入的“你”和“好”预测出来的。
在这里插入图片描述
W[hx]表示从x到h的权重

衡量语言模型

  • 平均交叉熵
    • 困惑度:指数(1表示完美,无穷表示垃)

梯度剪裁

可以防止梯度爆炸,如果梯度长度超过某个值,就拖回到这个值。
在这里插入图片描述

torch实现

import torch
from torch import nn
from torch.nn import functional as F
from d2l import torch as d2l

batch_size, num_steps = 32, 35 #句子长度为35
train_iter, vocab = d2l.load_data_time_machine(batch_size, num_steps)
#一个具有256个隐藏单元的单隐藏层的循环神经网络层 rnn_layer
num_hiddens = 256
rnn_layer = rnn.RNN(num_hiddens)
rnn_layer.initialize()

class RNNModel(nn.Module):
    """循环神经网络模型。"""
    def __init__(self, rnn_layer, vocab_size, **kwargs):
        super(RNNModel, self).__init__(**kwargs)
        self.rnn = rnn_layer #不包括输出层
        self.vocab_size = vocab_size
        self.num_hiddens = self.rnn.hidden_size
        # 如果RNN是双向的(之后将介绍),`num_directions`应该是2,否则应该是1。
        # 构造输出层
        if not self.rnn.bidirectional:
            self.num_directions = 1
            self.linear = nn.Linear(self.num_hiddens, self.vocab_size)
        else:
            self.num_directions = 2
            self.linear = nn.Linear(self.num_hiddens * 2, self.vocab_size)

    def forward(self, inputs, state):
        X = F.one_hot(inputs.T.long(), self.vocab_size)
        X = X.to(torch.float32)
        Y, state = self.rnn(X, state) # 中间隐藏层的Y
        # 全连接层首先将`Y`的形状改为(`时间步数`*`批量大小`, `隐藏单元数`)。
        # 它的输出形状是 (`时间步数`*`批量大小`, `词表大小`)。
        output = self.linear(Y.reshape((-1, Y.shape[-1])))#把时间和批量这两个维度和到一起
        return output, state

    def begin_state(self, device, batch_size=1):
        if not isinstance(self.rnn, nn.LSTM):
            # `nn.GRU` 以张量作为隐藏状态
            return  torch.zeros((self.num_directions * self.rnn.num_layers,
                                 batch_size, self.num_hiddens),
                                device=device)
        else:
            # `nn.LSTM` 以张量作为隐藏状态
            return (torch.zeros((
                self.num_directions * self.rnn.num_layers,
                batch_size, self.num_hiddens), device=device),
                    torch.zeros((
                        self.num_directions * self.rnn.num_layers,
                        batch_size, self.num_hiddens), device=device))

def train_ch8(net, train_iter, vocab, lr, num_epochs, device,
              use_random_iter=False):
    """训练模型(定义见第8章)。"""
    loss = nn.CrossEntropyLoss()
    animator = d2l.Animator(xlabel='epoch', ylabel='perplexity',
                            legend=['train'], xlim=[10, num_epochs])
    # 初始化
    if isinstance(net, nn.Module):
        updater = torch.optim.SGD(net.parameters(), lr)
    else:
        updater = lambda batch_size: d2l.sgd(net.params, lr, batch_size)
    predict = lambda prefix: predict_ch8(prefix, 50, net, vocab, device)
    # 训练和预测
    for epoch in range(num_epochs):
        ppl, speed = train_epoch_ch8(
            net, train_iter, loss, updater, device, use_random_iter)
        if (epoch + 1) % 10 == 0:
            print(predict('time traveller'))
            animator.add(epoch + 1, [ppl])
    print(f'困惑度 {ppl:.1f}, {speed:.1f} 词元/秒 {str(device)}')
    print(predict('time traveller'))
    print(predict('traveller'))
num_epochs, lr = 500, 1
d2l.train_ch8(net, train_iter, vocab, lr, num_epochs, device)

三、GRU 门控循环单元

是LSTM的简化,正常情况下效果差不多。

思路

由于并不是每个值都是同等重要的,所以设置更新门(关注的机制)和重置门(遗忘机制)来只记住相关的值(关键字、关键点、切换场景时的帧 )。

在这里插入图片描述
R和Z本质是用sigmoid对全连接层做激活
R(重置门):0到1之间的数,若为0表示之前的东西全不要
Z(更新门):0到1之间的数,若为1表示不用之前的东西更新
改进:多了几个可以计算的权重
H是候选隐含状态:根据X、R和W、之前的H输出当前候选隐含状态
H是隐含状态:根据Z、
H、之前的H的值输出新的隐含状态
在这里插入图片描述

torch实现

num_inputs = vocab_size
gru_layer = nn.GRU(num_inputs, num_hiddens)
model = d2l.RNNModel(gru_layer, len(vocab))
model = model.to(device)
d2l.train_ch8(model, train_iter, vocab, lr, num_epochs, device)

四、LSTM

先于GRU提出,四套W权重

遗忘门F:将值收缩为0
输入门I:决定是否忽略输入数据
输出门O:决定是否使用隐含状态( 当前的C)
候选记忆单元~C:包括了 前一个状态的H(相当于GRU中的 当前状态的H)
记忆单元C:C的数值区间比较大,是否使用 之前的C 和 ~C
隐含状态H:将C的值稳定在1和-1之间,根据O控制要不要输出
在这里插入图片描述

torch实现

num_inputs = vocab_size
lstm_layer = nn.LSTM(num_inputs, num_hiddens)
model = d2l.RNNModel(lstm_layer, len(vocab))
model = model.to(device)
d2l.train_ch8(model, train_iter, vocab, lr, num_epochs, device)

五、Deep RNN 深度循环

输入-隐藏层-输出
通过增加隐藏层的个数,来加深RNN,获得更多的非线性性,增大可处理的序列长度。
后一个隐藏层的输出是上一个隐藏层的输出,同时下一个时刻的输入是上一个时刻的输出。
在这里插入图片描述

torch实现

import torch
from torch import nn
from d2l import torch as d2l

batch_size, num_steps = 32, 35
train_iter, vocab = d2l.load_data_time_machine(batch_size, num_steps)
#num layers是隐藏层的个数
vocab_size, num_hiddens, num_layers = len(vocab), 256, 2
num_inputs = vocab_size
device = d2l.try_gpu()
# Pytorch的LSTM不带输出层
lstm_layer = nn.LSTM(num_inputs, num_hiddens, num_layers)
model = d2l.RNNModel(lstm_layer, len(vocab))
model = model.to(device)

num_epochs, lr = 500, 2
d2l.train_ch8(model, train_iter, vocab, lr, num_epochs, device)

六、BRNN双向循环网络

一个词取决于过去和未来的上下文,所以不能用于推测下一个词,只能做完词填空,对一个句子做特征提取,Eg:翻译、改写。

一个前向RNN隐藏层,一个后向RNN隐藏层,合并(concat)两个隐状态得到输出,两个隐藏层为一组,这两组隐藏层的权重不共享。
在这里插入图片描述

torch实现

import torch
from torch import nn
from d2l import torch as d2l

# 加载数据
batch_size, num_steps, device = 32, 35, d2l.try_gpu()
train_iter, vocab = d2l.load_data_time_machine(batch_size, num_steps)
# 通过设置'bidirective=True'来定义双向LSTM模型
vocab_size, num_hiddens, num_layers = len(vocab), 256, 2
num_inputs = vocab_size
lstm_layer = nn.LSTM(num_inputs, num_hiddens, num_layers, bidirectional=True)
model = d2l.RNNModel(lstm_layer, len(vocab))
model = model.to(device)
# 训练模型
num_epochs, lr = 500, 1
d2l.train_ch8(model, train_iter, vocab, lr, num_epochs, device)
深度学习Review【三】序列、RNN、LSTM(GRU)、DRNN

课程地址

一、编码-解码

编码(训练):处理输出,把输入编程成中甲你表达形式(特征)
解码(预测):生成输出,把特征解码成输出

from torch import nn

class Encoder(nn.Module):
    """编码器-解码器结构的基本编码器接口。"""
    def __init__(self, **kwargs):
        super(Encoder, self).__init__(**kwargs)

    def forward(self, X, *args):
        raise NotImplementedError
class Decoder(nn.Module):
    """编码器-解码器结构的基本解码器接口。"""
    def __init__(self, **kwargs):
        super(Decoder, self).__init__(**kwargs)

    def init_state(self, enc_outputs, *args):
        raise NotImplementedError

    def forward(self, X, state):
        raise NotImplementedError
class EncoderDecoder(nn.Module):
    """编码器-解码器结构的基类。"""
    def __init__(self, encoder, decoder, **kwargs):
        super(EncoderDecoder, self).__init__(**kwargs)
        self.encoder = encoder
        self.decoder = decoder

    def forward(self, enc_X, dec_X, *args):
        enc_outputs = self.encoder(enc_X, *args)
        dec_state = self.decoder.init_state(enc_outputs, *args)
        return self.decoder(dec_X, dec_state)

二、Seq2seq

在这里插入图片描述
训练过程,即Encode的过程(一个RNN)是双向的
解码器是单向的
RNN也不需要定长的序列作为输入输出

在这里插入图片描述
把编码器的RNN最后一层的输出放在解码器里,作为初始隐状态

torch

import collections
import math
import torch
from torch import nn
from d2l import torch as d2l

class Seq2SeqEncoder(d2l.Encoder):
    """用于序列到序列学习的循环神经网络编码器Encode"""
    def __init__(self, vocab_size, embed_size, num_hiddens, num_layers,dropout=0, **kwargs):
        super(Seq2SeqEncoder, self).__init__(**kwargs)
        # 嵌入层
        self.embedding = nn.Embedding(vocab_size, embed_size) 
        #对每个词embedding
        self.rnn = nn.GRU(embed_size, num_hiddens, num_layers,
                          dropout=dropout)
        #numlayers是RNN的层数 numhiddens是隐藏层的层数
    def forward(self, X, *args):
        # 输出'X'的形状:(`batch_size`, `num_steps`, `embed_size`)
        X = self.embedding(X)
        # 在循环神经网络模型中,第一个轴对应于时间步,交换batchsize和numstep
        X = X.permute(1, 0, 2)
        # 如果未提及状态,则默认为0
        output, state = self.rnn(X)
        # `output`的形状: (`num_steps`, `batch_size`, `num_hiddens`)
        # `state[0]`的形状: (`num_layers`, `batch_size`, `num_hiddens`)
        return output, state

encoder = Seq2SeqEncoder(vocab_size=10, embed_size=8, num_hiddens=16,
                         num_layers=2)
encoder.eval()
X = torch.zeros((4, 7), dtype=torch.long)
output, state = encoder(X)
#output和state的形状torch.Size([7, 4, 16]) torch.Size([2, 4, 16])

class Seq2SeqDecoder(d2l.Decoder):
    """用于序列到序列学习的循环神经网络解码器。"""
    def __init__(self, vocab_size, embed_size, num_hiddens, num_layers,
                 dropout=0, **kwargs):
        super(Seq2SeqDecoder, self).__init__(**kwargs)
        self.embedding = nn.Embedding(vocab_size, embed_size)
        self.rnn = nn.GRU(embed_size + num_hiddens, num_hiddens, num_layers,
                          dropout=dropout)
        self.dense = nn.Linear(num_hiddens, vocab_size)
        #分类

    def init_state(self, enc_outputs, *args):
        return enc_outputs[1] #enc_outputs[1]为state

    def forward(self, X, state):
        # 输出'X'的形状:(`batch_size`, `num_steps`, `embed_size`)
        X = self.embedding(X).permute(1, 0, 2)
        # 广播`context`,使其具有与`X`相同的`num_steps`
        context = state[-1].repeat(X.shape[0], 1, 1)
        X_and_context = torch.cat((X, context), 2)
        output, state = self.rnn(X_and_context, state)
        output = self.dense(output).permute(1, 0, 2)
        # `output`的形状: (`batch_size`, `num_steps`, `vocab_size`)
        # `state[0]`的形状: (`num_layers`, `batch_size`, `num_hiddens`)
        return output, state
decoder = Seq2SeqDecoder(vocab_size=10, embed_size=8, num_hiddens=16,
                         num_layers=2)
decoder.eval()
state = decoder.init_state(encoder(X))
output, state = decoder(X, state)
# output和state的shape(torch.Size([4, 7, 10]), torch.Size([2, 4, 16]))
深度学习Review【二】LeNet、AlexNet、VGG、NiN、GoogLeNet、ResNet、DenseNet

课程地址

一、LeNet

手写数字识别(MNIST)
在这里插入图片描述
使用了Conv2d、AvgPooling、Linear
高宽减半时通道数翻倍,保证信息能匹配更多的模式(将信息分配到多个通道)
输入超过100x100时MLP不如CNN,输入少时mlp更快

torch实现

import torch
from torch import nn
from d2l import torch as d2l
#使用类可以放在Sequential里
class Reshape(torch.nn.Module):
    def forward(self, x):
        return x.view(-1, 1, 28, 28)

net = torch.nn.Sequential(
    Reshape(),
    nn.Conv2d(1, 6, kernel_size=5, padding=2), nn.Sigmoid(),#窗口5x5,由于数据集是28x28和论文中32x32不同,所以padding了2
    nn.AvgPool2d(kernel_size=2, stride=2),#stride=2防止2x2的窗口重叠
    nn.Conv2d(6, 16, kernel_size=5), nn.Sigmoid(),
    nn.AvgPool2d(kernel_size=2, stride=2),#输出为16*5*5
    nn.Flatten(),#把16x5x5拉长变成1维的1x400
    nn.Linear(16 * 5 * 5, 120), nn.Sigmoid(),
    nn.Linear(120, 84), nn.Sigmoid(),nn.Linear(84, 10))#最后输出1*10的向量
    #去掉了高斯层
batch_size = 256
train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size=batch_size)

def evaluate_accuracy_gpu(net, data_iter, device=None):
    """使用GPU计算模型在数据集上的精度。"""
    if isinstance(net, torch.nn.Module):
        net.eval()  # 设置为评估模式
        if not device: #未设置device就看net的第一个参数的device
            device = next(iter(net.parameters())).device
    # 正确预测的数量,总预测的数量
    metric = d2l.Accumulator(2)
    for X, y in data_iter:
        if isinstance(X, list):
            # BERT微调所需的(之后将介绍)
            X = [x.to(device) for x in X]
        else:
            X = X.to(device)
        y = y.to(device)
        metric.add(d2l.accuracy(net(X), y), y.numel())
    return metric[0] / metric[1] #分类正确的个数/所有
#lr为学习率
def train_ch6(net, train_iter, test_iter, num_epochs, lr, device):
    """用GPU训练模型(在第六章定义)"""
    def init_weights(m): #初始化权重
        if type(m) == nn.Linear or type(m) == nn.Conv2d:
            nn.init.xavier_uniform_(m.weight) #线性回归和二维卷积自动初始化权重(卷积核)
    net.apply(init_weights)
    print('training on', device)
    net.to(device)#搬入GPU
    optimizer = torch.optim.SGD(net.parameters(), lr=lr)
    loss = nn.CrossEntropyLoss()
    #使用动画方便查看结果
    animator = d2l.Animator(xlabel='epoch', xlim=[1, num_epochs],
                            legend=['train loss', 'train acc', 'test acc'])
    timer, num_batches = d2l.Timer(), len(train_iter)
    for epoch in range(num_epochs):
        # 训练损失之和,训练准确率之和,范例数
        metric = d2l.Accumulator(3)
        net.train()
        for i, (X, y) in enumerate(train_iter):
            timer.start()
            optimizer.zero_grad()
            X, y = X.to(device), y.to(device)#把输入输出放在GPU上
            y_hat = net(X)
            l = loss(y_hat, y)
            l.backward()
            optimizer.step()
            with torch.no_grad():
                metric.add(l * X.shape[0], d2l.accuracy(y_hat, y), X.shape[0])
            timer.stop()
            train_l = metric[0] / metric[2]
            train_acc = metric[1] / metric[2]
            if (i + 1) % (num_batches // 5) == 0 or i == num_batches - 1:
                animator.add(epoch + (i + 1) / num_batches,
                             (train_l, train_acc, None))
        test_acc = evaluate_accuracy_gpu(net, test_iter)
        animator.add(epoch + 1, (None, None, test_acc))
    print(f'loss {train_l:.3f}, train acc {train_acc:.3f}, '
          f'test acc {test_acc:.3f}')
    print(f'{metric[2] * num_epochs / timer.sum():.1f} examples/sec '
          f'on {str(device)}')

图片的学习结果 http://poloclub.github.io/cnn-explainer/

二、AlexNet

数据集:ImageNet 自然物体彩色图片

特点

更深更大的LeNet
使用了丢弃法(正则化)、ReLU(减缓梯度消失)、MaxPooling(扩大梯度更容易训练)、隐藏全连接层后(Dense/FC 4096后)加入丢弃层
在这里插入图片描述

torch实现

import torch
from torch import nn
from d2l import torch as d2l

net = nn.Sequential(
    # 步幅为4,以减少输出的高度和宽度 输出通道 96
    nn.Conv2d(1, 96, kernel_size=11, stride=4, padding=1), nn.ReLU(),
    nn.MaxPool2d(kernel_size=3, stride=2),
    # 减小卷积窗口,使用填充为2来使得输入与输出的高和宽一致,且增大输出通道数
    nn.Conv2d(96, 256, kernel_size=5, padding=2), nn.ReLU(),
    nn.MaxPool2d(kernel_size=3, stride=2),
    # 使用三个连续的卷积层和较小的卷积窗口 除了最后的卷积层,输出通道的数量进一步增加。
    # 在前两个卷积层之后,汇聚层不用于减少输入的高度和宽度
    nn.Conv2d(256, 384, kernel_size=3, padding=1), nn.ReLU(),
    nn.Conv2d(384, 384, kernel_size=3, padding=1), nn.ReLU(),
    nn.Conv2d(384, 256, kernel_size=3, padding=1), nn.ReLU(),
    nn.MaxPool2d(kernel_size=3, stride=2),
    nn.Flatten(),
    # 这里,全连接层的输出数量是LeNet中的好几倍。使用dropout层来减轻过度拟合
    nn.Linear(6400, 4096), nn.ReLU(),
    nn.Dropout(p=0.5),
    nn.Linear(4096, 4096), nn.ReLU(),
    nn.Dropout(p=0.5), # 丢弃了50%
    # 最后是输出层。使用Fashion-MNIST,类别数为10,论文中是1000
    nn.Linear(4096, 10))

batch_size = 128
train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size, resize=224)

lr, num_epochs = 0.01, 10
#train_ch6定义在上
d2l.train_ch6(net, train_iter, test_iter, num_epochs, lr, d2l.try_gpu())

三、VGG

为了让模型更深更大,使用更多的卷积层,将卷积层组成块,重复使用这些卷积块
更深的模型 窗口更小 效果更好
在这里插入图片描述

结构

原始 VGG 网络有 5 个卷积块,其中前两个块各有一个卷积层,后三个块各包含两个卷积层。
第一个模块有 64 个输出通道,每个后续模块将输出通道数量翻倍,直到该数字达到 512。由于该网络使用 8 个卷积层和 3 个全连接层,因此它被称为 VGG-11

torch实现

import torch
from torch import nn
from d2l import torch as d2l

def vgg_block(num_convs, in_channels, out_channels):
    layers = []
    for _ in range(num_convs):
        layers.append(nn.Conv2d(in_channels, out_channels,
                                kernel_size=3, padding=1))
        layers.append(nn.ReLU())
        in_channels = out_channels
    layers.append(nn.MaxPool2d(kernel_size=2,stride=2))
    return nn.Sequential(*layers)

conv_arch = ((1, 64), (1, 128), (2, 256), (2, 512), (2, 512))

def vgg(conv_arch):
    conv_blks = []
    in_channels = 1
    # 卷积层部分
    for (num_convs, out_channels) in conv_arch:
        conv_blks.append(vgg_block(num_convs, in_channels, out_channels))
        in_channels = out_channels

    return nn.Sequential(
        *conv_blks, nn.Flatten(),
        # 全连接层部分 224
        nn.Linear(out_channels * 7 * 7, 4096), nn.ReLU(), nn.Dropout(0.5),
        nn.Linear(4096, 4096), nn.ReLU(), nn.Dropout(0.5),
        nn.Linear(4096, 10))

net = vgg(conv_arch)

ratio = 4 #将通道数除以4 以方便训练
small_conv_arch = [(pair[0], pair[1] // ratio) for pair in conv_arch]
net = vgg(small_conv_arch)

lr, num_epochs, batch_size = 0.05, 10, 128
train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size, resize=224)
d2l.train_ch6(net, train_iter, test_iter, num_epochs, lr, d2l.try_gpu())

四、NiN

网络中的网络

思路、结构

全连接层会导致过拟合,用卷积层替代全连接层
使用NiN块,一个卷积层+两个卷积层(卷积核为1x1、步幅为1、无填充、输出形状和卷积层输出一致(不改变输出和通道数)),来代替全连接层
交替使用NiN块和步幅为2的最大池化层(逐步减小高宽 增大通道数),最后用全局平均池化层替代非常大的全连接层得到输出
在这里插入图片描述

torch实现

import torch
from torch import nn
from d2l import torch as d2l

def nin_block(in_channels, out_channels, kernel_size, strides, padding):
    return nn.Sequential(
        nn.Conv2d(in_channels, out_channels, kernel_size, strides, padding),nn.ReLU(),
        #输入输出通道数相同
        nn.Conv2d(out_channels, out_channels, kernel_size=1), nn.ReLU(),
        nn.Conv2d(out_channels, out_channels, kernel_size=1), nn.ReLU())

net = nn.Sequential(
    nin_block(1, 96, kernel_size=11, strides=4, padding=0),
    nn.MaxPool2d(3, stride=2),
    nin_block(96, 256, kernel_size=5, strides=1, padding=2),
    nn.MaxPool2d(3, stride=2),
    nin_block(256, 384, kernel_size=3, strides=1, padding=1),
    nn.MaxPool2d(3, stride=2),
    nn.Dropout(0.5),
    # MNIST的类别数是10,输出降到10即可
    nin_block(384, 10, kernel_size=3, strides=1, padding=1),
    nn.AdaptiveAvgPool2d((1, 1)),
    # 将四维的输出转成二维的输出,其形状为(批量大小, 10)
    nn.Flatten())

lr, num_epochs, batch_size = 0.1, 10, 128
train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size, resize=224)
#内含有Softmax
d2l.train_ch6(net, train_iter, test_iter, num_epochs, lr, d2l.try_gpu())

五、GoogLeNet

并行连接的网络

Inception块

将输入的通道分为4份
为每个通道使用不同窗口大小和padding的卷积层
最后的输出高宽相同
减少计算量
在这里插入图片描述

GoogLeNet

保留更多高宽
9个Inception块
每个Stage将高宽减半
使用全局平均池化
在这里插入图片描述
Stage1&2:更小的核 更小的输出通道
在这里插入图片描述

Stage3:输出通道增加
在这里插入图片描述

Stage4&5:增加通道数 最后输出1024维特征

在这里插入图片描述

Inception变种

Inception-BN(V2) 加入batch normalization

Inception-V3 替换卷积层,消耗内存较多,精度提升
把Inception块中的 5x5 替换为多个 3x3 的卷积层(或者1x7和7x1)、把 3x3 换为 1x3 和 3x1 的卷积层
在这里插入图片描述
在这里插入图片描述

Inception-V4 添加残差块连接

torch实现

import torch
from torch import nn
from torch.nn import functional as F
from d2l import torch as d2l

class Inception(nn.Module):
    # `c1`--`c4` 是每条路径的输出通道数
    def __init__(self, in_channels, c1, c2, c3, c4, **kwargs):
        super(Inception, self).__init__(**kwargs)
        # 线路1,单1 x 1卷积层
        self.p1_1 = nn.Conv2d(in_channels, c1, kernel_size=1)
        # 线路2,1 x 1卷积层后接3 x 3卷积层
        self.p2_1 = nn.Conv2d(in_channels, c2[0], kernel_size=1)
        self.p2_2 = nn.Conv2d(c2[0], c2[1], kernel_size=3, padding=1)
        # 线路3,1 x 1卷积层后接5 x 5卷积层
        self.p3_1 = nn.Conv2d(in_channels, c3[0], kernel_size=1)
        self.p3_2 = nn.Conv2d(c3[0], c3[1], kernel_size=5, padding=2)
        # 线路4,3 x 3最大汇聚层后接1 x 1卷积层
        self.p4_1 = nn.MaxPool2d(kernel_size=3, stride=1, padding=1)
        self.p4_2 = nn.Conv2d(in_channels, c4, kernel_size=1)
    def forward(self, x):
        p1 = F.relu(self.p1_1(x))
        p2 = F.relu(self.p2_2(F.relu(self.p2_1(x))))
        p3 = F.relu(self.p3_2(F.relu(self.p3_1(x))))
        p4 = F.relu(self.p4_2(self.p4_1(x)))
        # 在通道维度上拼接输出
        return torch.cat((p1, p2, p3, p4), dim=1)

b1 = nn.Sequential(nn.Conv2d(1, 64, kernel_size=7, stride=2, padding=3),
                   nn.ReLU(),
                   nn.MaxPool2d(kernel_size=3, stride=2, padding=1))
b2 = nn.Sequential(nn.Conv2d(64, 64, kernel_size=1),
                   nn.ReLU(),
                   nn.Conv2d(64, 192, kernel_size=3, padding=1),
                   nn.MaxPool2d(kernel_size=3, stride=2, padding=1))
b3 = nn.Sequential(Inception(192, 64, (96, 128), (16, 32), 32),
                   Inception(256, 128, (128, 192), (32, 96), 64),
                   nn.MaxPool2d(kernel_size=3, stride=2, padding=1))
b4 = nn.Sequential(Inception(480, 192, (96, 208), (16, 48), 64),
                   Inception(512, 160, (112, 224), (24, 64), 64),
                   Inception(512, 128, (128, 256), (24, 64), 64),
                   Inception(512, 112, (144, 288), (32, 64), 64),
                   Inception(528, 256, (160, 320), (32, 128), 128),
                   nn.MaxPool2d(kernel_size=3, stride=2, padding=1))
b5 = nn.Sequential(Inception(832, 256, (160, 320), (32, 128), 128),
                   Inception(832, 384, (192, 384), (48, 128), 128),
                   nn.AdaptiveAvgPool2d((1,1)),
                   nn.Flatten())

net = nn.Sequential(b1, b2, b3, b4, b5, nn.Linear(1024, 10))
lr, num_epochs, batch_size = 0.1, 10, 128
train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size, resize=96)
d2l.train_ch6(net, train_iter, test_iter, num_epochs, lr, d2l.try_gpu())

六、批量归一化

对于很深的神经网络,损失出现在最后,但数据在底部;当底部层发生变化所有层都要跟着改变,因此最后的那些层会重新学习很多次,导致loss收敛变慢。
一般作用在全连接层和卷积层的输出上,激活函数之前;全连接层和卷积层输入上
对于全连接层,作用在特征维;对于卷积层,作用在通道维。
由于是在每个小批量里加入噪音控制模型复杂度,因此不必和Dropout混用。

思想

固定小批量里的均值和方差,然后学习出适合的偏移和缩放,以加快收敛
在这里插入图片描述
方差和均值是可学习的参数,控制着做小量的调整(线性变换)
在这里插入图片描述

七、残差网络ResNet

加更多的层不一定能距离最优点更近

残差块

加入快速通道来得到 f(x) = x + g(x),由于g(x)在反向传播,层层求梯度之后可能变得非常小,所有将x加在这里,防止变成0而消失。
在这里插入图片描述
也可以用1x1的Conv调整通道和分辨率
在这里插入图片描述

可以有各种各样的排列形式
在这里插入图片描述
多个块拼接成ResNet,每个块高宽减半(strides = 2)
在这里插入图片描述

torch实现

import torch
from torch import nn
from torch.nn import functional as F
from d2l import torch as d2l


class Residual(nn.Module):  #@save
    def __init__(self, input_channels, num_channels,
                 use_1x1conv=False, strides=1):
        #use1x1是否使用1x1的卷积层
        super().__init__()
        self.conv1 = nn.Conv2d(input_channels, num_channels,
                               kernel_size=3, padding=1, stride=strides)
        self.conv2 = nn.Conv2d(num_channels, num_channels,
                               kernel_size=3, padding=1)
        if use_1x1conv:
            self.conv3 = nn.Conv2d(input_channels, num_channels,
                                   kernel_size=1, stride=strides)
        else:
            self.conv3 = None
        self.bn1 = nn.BatchNorm2d(num_channels)
        self.bn2 = nn.BatchNorm2d(num_channels)
        self.relu = nn.ReLU(inplace=True)

    def forward(self, X):
        Y = F.relu(self.bn1(self.conv1(X)))
        Y = self.bn2(self.conv2(Y))
        if self.conv3:
            X = self.conv3(X)
        Y += X
        return F.relu(Y)
b1 = nn.Sequential(nn.Conv2d(1, 64, kernel_size=7, stride=2, padding=3),
                   nn.BatchNorm2d(64), nn.ReLU(),
                   nn.MaxPool2d(kernel_size=3, stride=2, padding=1))
#num residuals是表示使用几个block组成一个Stage
def resnet_block(input_channels, num_channels, num_residuals,
                 first_block=False):
    blk = []
    for i in range(num_residuals):
        if i == 0 and not first_block:
            blk.append(Residual(input_channels, num_channels,
                                use_1x1conv=True, strides=2))
        else:
            blk.append(Residual(num_channels, num_channels))
    return blk
b2 = nn.Sequential(*resnet_block(64, 64, 2, first_block=True))
b3 = nn.Sequential(*resnet_block(64, 128, 2))
b4 = nn.Sequential(*resnet_block(128, 256, 2))
b5 = nn.Sequential(*resnet_block(256, 512, 2))
net = nn.Sequential(b1, b2, b3, b4, b5,
                    nn.AdaptiveAvgPool2d((1,1)),
                    nn.Flatten(), nn.Linear(512, 10))

各块输出的Shape
Sequential output shape: torch.Size([1, 64, 56, 56])
Sequential output shape: torch.Size([1, 64, 56, 56])
Sequential output shape: torch.Size([1, 128, 28, 28])
Sequential output shape: torch.Size([1, 256, 14, 14])
Sequential output shape: torch.Size([1, 512, 7, 7])
AdaptiveAvgPool2d output shape: torch.Size([1, 512, 1, 1])
Flatten output shape: torch.Size([1, 512])
Linear output shape: torch.Size([1, 10])

lr, num_epochs, batch_size = 0.05, 10, 256
train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size, resize=96)
d2l.train_ch6(net, train_iter, test_iter, num_epochs, lr, d2l.try_gpu())

DenseNet 稠密连接网络

用更高阶的泰勒展开,每一层都加上x
在这里插入图片描述

结构

由 稠密块(dense block)和 过渡层 (transition layer)构成。 前者定义如何连接输入和输出,而后者则通过 1×1 的卷积层来减小通道数,并使用步幅为 2 的平均池化层减半高和宽,控制通道数量。

torch实现

import torch
from torch import nn
from d2l import torch as d2l

def conv_block(input_channels, num_channels):
    return nn.Sequential(
        nn.BatchNorm2d(input_channels), nn.ReLU(),
        nn.Conv2d(input_channels, num_channels, kernel_size=3, padding=1))
# 稠密层        
class DenseBlock(nn.Module):
    def __init__(self, num_convs, input_channels, num_channels):
        super(DenseBlock, self).__init__()
        layer = []
        for i in range(num_convs):
            layer.append(conv_block(
                num_channels * i + input_channels, num_channels))
        self.net = nn.Sequential(*layer)

    def forward(self, X):
        for blk in self.net:
            Y = blk(X)
            # 连接通道维度上每个块的输入和输出
            X = torch.cat((X, Y), dim=1)
        return X
blk = DenseBlock(2, 3, 10)
X = torch.randn(4, 3, 8, 8)
Y = blk(X)
Y.shape
# 过渡层
def transition_block(input_channels, num_channels):
    return nn.Sequential(
        nn.BatchNorm2d(input_channels), nn.ReLU(),
        nn.Conv2d(input_channels, num_channels, kernel_size=1),
        nn.AvgPool2d(kernel_size=2, stride=2))
blk = transition_block(23, 10)
blk(Y).shape
# DenseNet
b1 = nn.Sequential(
    nn.Conv2d(1, 64, kernel_size=7, stride=2, padding=3),
    nn.BatchNorm2d(64), nn.ReLU(),
    nn.MaxPool2d(kernel_size=3, stride=2, padding=1))

num_channels, growth_rate = 64, 32
num_convs_in_dense_blocks = [4, 4, 4, 4]
blks = []
for i, num_convs in enumerate(num_convs_in_dense_blocks):
    blks.append(DenseBlock(num_convs, num_channels, growth_rate))
    # 上一个稠密块的输出通道数
    num_channels += num_convs * growth_rate
    # 在稠密块之间添加一个转换层,使通道数量减半
    if i != len(num_convs_in_dense_blocks) - 1:
        blks.append(transition_block(num_channels, num_channels // 2))
        num_channels = num_channels // 2
#最后加上池化和全连接
net = nn.Sequential(
    b1, *blks,
    nn.BatchNorm2d(num_channels), nn.ReLU(),
    nn.AdaptiveMaxPool2d((1, 1)),
    nn.Flatten(),
    nn.Linear(num_channels, 10))
lr, num_epochs, batch_size = 0.1, 10, 256
train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size, resize=96)
d2l.train_ch6(net, train_iter, test_iter, num_epochs, lr, d2l.try_gpu()) 
深度学习Review【一】线性回归、Softmax、感知机、卷积

课程地址

一、线性回归

线性模型:y = ax + b
在这里插入图片描述
单层神经网络(输出层不看做是一层)
在这里插入图片描述

1 损失函数

比较真实值和预估值
以下几种损失函数比较

  • 0-1损失函数(zero-one loss)
  • 绝对值损失函数
  • log对数损失函数
  • 平方损失函数
  • 指数损失函数(exponential loss)
  • Hinge 损失函数
  • 感知损失(perceptron loss)函数
  • 交叉熵损失函数 (Cross-entropy loss function)

语音的几种损失函数

2 参数学习

选取不同的w和b,根据输入X,计算y的损失
最小化损失

3 梯度下降 GD

在这里插入图片描述
学习率:每次计算loss后调整的步长

小批量随机梯度下降 SGD:通过随机采样b个样本计算近似损失,以减少计算梯度求导的消耗
这里的b 就是batchsize,并行进入神经网络的样本数量

3 torch实现

# `nn` 是神经网络的缩写
from torch import nn
#Sequential是存放网络的list
#全连接层(单层网络)输入维度是2 输出为1
net = nn.Sequential(nn.Linear(2, 1))
#初始化网络参数
net[0].weight.data.normal_(0, 0.01)
net[0].bias.data.fill_(0)
#损失函数 均方误差
loss = nn.MSELoss()
#定义优化算法 小批量随机梯度下降 传入net的参数w和b 指定学习率lr
trainer = torch.optim.SGD(net.parameters(), lr=0.03)
#训练
num_epochs = 3
for epoch in range(num_epochs):
    for X, y in data_iter:
        l = loss(net(X) ,y)
        trainer.zero_grad() #梯度清零以计算backward
        l.backward() 
        trainer.step() #更新模型
    l = loss(net(features), labels)
    print(f'epoch {epoch + 1}, loss {l:f}')
w = net[0].weight.data
print('w的估计误差:', true_w - w.reshape(true_w.shape))
b = net[0].bias.data
print('b的估计误差:', true_b - b)

二、Softmax分类

预测离散的类型,通常有多个输出,输出 i 是预测为第 i 类的置信度
在这里插入图片描述
对每个类别进行一位有效编码(==One-Hot==),编码后为向量y作为输入,每个类别的置信度分数(即每个类别的概率)作为输出(输出向量的每个元素非负,元素和为1)
使用均方损失函数训练

1 损失函数

橙色为导数,绿色为最大似然函数,蓝色为损失函数
在这里插入图片描述
随着预测值和真实值相差不同,进行不同的优化
在这里插入图片描述
不管预测值和真实值相差多远,都能稳定优化
在这里插入图片描述
在预测值和真实值相差不大时,减少优化

2 torch实现

import torch
from torch import nn
from d2l import torch as d2l

batch_size = 256
train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size)

# PyTorch不会隐式地调整输入的形状 在线性层前定义展平层(flatten)调整网络输入的形状
#输入为784 输出为10
net = nn.Sequential(nn.Flatten(), nn.Linear(784, 10))
#初始化为均值为0方差为0.01的随机值
def init_weights(m):
    if type(m) == nn.Linear:
        nn.init.normal_(m.weight, std=0.01)
net.apply(init_weights);

loss = nn.CrossEntropyLoss()

trainer = torch.optim.SGD(net.parameters(), lr=0.1)
#训练模型
num_epochs = 10
def train_ch3(net, train_iter, test_iter, loss, num_epochs, updater):  
    animator = Animator(xlabel='epoch', xlim=[1, num_epochs], ylim=[0.3, 0.9],
                        legend=['train loss', 'train acc', 'test acc'])
    for epoch in range(num_epochs):
        train_metrics = train_epoch_ch3(net, train_iter, loss, updater)
        test_acc = evaluate_accuracy(net, test_iter)
        animator.add(epoch + 1, train_metrics + (test_acc,))
    train_loss, train_acc = train_metrics
    assert train_loss < 0.5, train_loss
    assert train_acc <= 1 and train_acc > 0.7, train_acc
    assert test_acc <= 1 and test_acc > 0.7, test_acc
d2l.train_ch3(net, train_iter, test_iter, loss, num_epochs, trainer)

三、感知机 Perceptron

1 二分类的感知机

二分类问题,x为给定输入,w为权重,b为偏移
在这里插入图片描述
线性回归输出的是实数,softmax回归输出的是概率,这里只输出0和1(或者-1和1)是二分类问题
在这里插入图片描述
y为实际值,wx+b为预测值,以下所有wx为w和x的混合积

w=b=0;
while(所有分类正确): 
    if (y*[wx+b]<=0) w+=y*x,b+=y;

等价于使用batchsize为1的梯度下降,其中loss=max(0,-y*wx)
根据收敛定理,对于正确的数据一定可以得到一条直线,将两类样本点分开
局限:普通感知机不能拟合XOR函数,必须使用多层感知机

2 多层感知机MLP

两个分类器做乘法(用与门和或门实现与或门)
在这里插入图片描述

单隐藏层-单分类

Hidden-layer隐藏层是 mxn 的矩阵
在这里插入图片描述
使用线性==激活函数==会导致多个连接层摞在一起,变成单层感知机;应当使用Sigmoid、Tanh、ReLU

多隐藏层多分类

在这里插入图片描述
结果 y = ==softmax== (o)

在这里插入图片描述
每次计算出隐藏层结果之前都要使用非线性激活函数,最后一层可以直接通过softmax得到y

3 torch实现

import torch
from torch import nn
from d2l import torch as d2l

net = nn.Sequential(nn.Flatten(),
                    nn.Linear(784, 256),
                    nn.ReLU(),
                    nn.Linear(256, 10))
# 将三维flatten成二维
def init_weights(m):
    if type(m) == nn.Linear:
        nn.init.normal_(m.weight, std=0.01)

net.apply(init_weights);

batch_size, lr, num_epochs = 256, 0.1, 10
loss = nn.CrossEntropyLoss()#交叉熵损失
trainer = torch.optim.SGD(net.parameters(), lr=lr)

train_iter, test_iter = d2l.load_data_fashion_mnist(batch_size)
d2l.train_ch3(net, train_iter, test_iter, loss, num_epochs, trainer)

四、卷积层

1 卷积操作

卷积是具有平移不变性(权重共享)和局部性的全连接
以下以二维卷积为例
二维交叉相关:w为权重,v为重新构建索引后的w
在这里插入图片描述
平移不变性:换不同的位置 卷积的计算方式不改变
在这里插入图片描述

局部性:卷积核在局部进行运算即可
在这里插入图片描述

2 卷积层

在这里插入图片描述
填充:通过填充保证卷积后矩阵尺寸不会太小
在这里插入图片描述

步长(步幅):矩阵太大,跳过一些以控制输出
在这里插入图片描述

3 gif

动图地址

正卷积 Convolution

No padding, no strides Arbitrary padding, no strides Half padding, no strides Full padding, no strides
No padding, strides Padding, strides Padding, strides (odd)

转置卷积 Transposed Convolution

No padding, no strides, transposed Arbitrary padding, no strides, transposed Half padding, no strides, transposed Full padding, no strides, transposed
No padding, strides, transposed Padding, strides, transposed Padding, strides, transposed (odd)
空洞卷积 Dilated convolution ![在这里插入图片描述](https://cdn.jsdelivr.net/gh/liting1024/PicImage/PicgoGithub/405a4c3d348d42d98f83aedcae5648b5.gif)

4 多输入输出通道channls

意义

多个输出out通道可以识别特定的模式,Eg:RGB图片三通道可以按照颜色分别识别
多个输入in通道可以识别并组合输入中的模式,Eg:在识别猫的图片时,分别识别出猫的脚和身体,然后组合

实现

多输入in:在每个通道各自卷积后加权求和(降维)为一个通道
多输出out:使用多个卷积核,每个卷积核生成一个输出通道

5 1x1的卷积层

不识别空间模式,只是融合不同通道的信息,对不同的通道进行加权求和
Eg:语音分离
在这里插入图片描述
将input拉成一维的向量就变成全连接层

五、ConvTranspoes 转置卷积

增大输入的高宽,一般用于恢复形状,但输出的信息比较抽象,不能被人直接分辨,也用于上采样。
输入中的每一个值与卷积核的每一个值做乘法,把重合的部分相加。
padding是去掉输出的外层。
在这里插入图片描述

六、池化层(汇聚层) Pooling

卷积层做边缘检测时,对边缘太敏感,检测时往往会不准确

最大池化:在滑动窗口时,返回窗口中的最大值
平均池化:返回窗口中各元素的均值

特点

超参数有窗口大小、填充和步幅
没有可学习的参数
输出通道数=输入通道数
在每个输入通道都用池化层来分别获得输出,不进行多通道融合

torch实现

2x3大小的窗口

pool2d = nn.MaxPool2d((2, 3), padding=(1, 1), stride=(2, 3))
pool2d(X)
基础算法

基础算法

排序

快速排序 - 分治

分治:不断把数据分成两部分,一半小于另一半

  1. 确定分界(4种方法):取q[l], q[(l + r) / 2], q[r], 随机点

  2. 调整区间:小于分界点的在左区间,其余在右区间

    ​ 使用两个数组作为左右区间

    ​ 使用两个指针(i = l - 1,j = r + 1),如果a[i]>x,a[i]<x,交换a[i] a[j]

  3. 递归:给左右排序

void quick_sort(int q[], int l, int r) {
    if (l >= r) 
      return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j); quick_sort(q, j + 1, r);
}

归并排序 - 分治(稳定)

合并:两个有序数组

双指针:比较两个数组里待合并的数,将较小的放入新数组

  1. 确定分界点 mid = (l + r) / 2 数组的中心
  2. 递归
  3. 归并两个有序数组(用双指针合并)
void merge_sort(int q[], int l, int r) {
    if (l >= r) return;

    int mid = l + r >> 1; // 用mid将原数组一分为二
    // 先递归到底
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) 
        // 双指针i和j分别对mid左右的两个数组遍历
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    // 将剩余的部分加入数组
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

二分

有单调性 一定可以 二分

求范围,让答案在收缩的区间里

向左收缩和向右收缩mid的取值不同

IMG_67CE3ECA2B0B-1.jpeg

// 整数二分
bool check(int x) {} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:向左收缩
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    } // 结束时l和r相等
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:向右收缩
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;//防止死循环 多加1
        if (check(mid)) l = mid; // arr[mid]=x 时需要取边界
        else r = mid - 1;
    }
    return l;
}

对于浮点数 将while里停止的条件改为 r - l > 1e-6

while控制的精度最好小于输出保留位数两位,防止精度不够

Eg:输出小数点后四位,这里控制为1e-6

// 实数二分
bool check(double x) {} // 检查x是否满足某种性质

double bsearch_3(double l, double r) {
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度

用数组存大整数,低地址存低位(小端),0存个位

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B) {
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ) {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

A < B => -(B - A)

// C = A - B, 满足A >= B, A >= 0, B >= 0
bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size()-1; i >= 0; i--) 
        if (A[i] != B[i]) return A[i] > B[i];
    return true; // 
}
vector<int> sub(vector<int> &A, vector<int> &B) { //引用 节省时间
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ ) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
          // 只防止负数 不会改变结果 
        //(1+10)%10 = 1 (10+10)%10 = 0
        if (t < 0) t = 1;
        else t = 0;
    }
        // 去除多个 0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
// 主函数
if (cmp(A, B)) C = sub(A, B);
else {
    C = sub(B, A);
    cout<<'-';
}

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;

    for (int i = 0, t = 0; i < A.size() || t; i ++ ) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

IMG_CF57C855FBAC-1.jpeg

// A / b = C ... r, A >= 0, b > 0
// 引用直接修改原来的r
vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- ) {
        r = r * 10 + A[i]; // 借位
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

前缀和

应用:计算前缀和

存前缀和的下标从1开始,将数组下标为0的值设为0

一维

IMG_D9E1403749B2-1.jpeg

二维

96221_82a4b4b87a-IMG_57AF8F31A5F1-1.jpg

// 一维
s[i] = s[i-1] + a[i];
s[j] - s[i-1];

// 二维
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];

差分

应用:在[ l , r ]之间的每个数加上 c

前缀和的逆运算

一维

IMG_C86BC0DC46CD-1.jpeg

二维

IMG_66D0BEAAF6CD-1.jpeg

// 一维
// a存b的前缀和
b[i] = a[i]-a[i-1]

void insert(int l, int r,int c) {
  b[l] += c;
  b[r+1] -= c;
}
// 求前缀和 得到操作后的a数组
b[i] += b[i-1];

// 二维
void insert(int x1,int y1,int x2,int y2,int c) {
    b[x1][y1] += c;
    b[x2+1][y1] -= c;
    b[x1][y2+1] -= c;
    b[x2+1][y2+1] += c;
}
// 求前缀和 把b还原成加了c之后的a
b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];

双指针

核心:将两个指针 n^2 优化到 n , 没思路可以先写一个 n^2 找规律

两个序列:合并;归并排序的归并、快速排序的划分;KMP

一个序列:确定区间的开头结尾,如:滑动窗口;判断环

for (i = 0, j = 0; i < n; i++) {
    while(j < i && check(i, j)) j++;
}

位运算

n>>k&1:n(二进制)的第k位(从第0位开始)

1<<n:2的n次方

lowbit(x) { return x&-x;}:x&(~x+1),即返回x的最后一位1,可以计算1的个数

异或

不进位加法,相同为0,不同为1

运算 功能
0^x = x 0异或还是原数
1^1010 = 1011 1异或末尾取反
x^x = 0 异或自己得0
a^b == 0 判断a和b是否相等

交换a和b:a = a ^ b, b = b ^ a, a = a ^ b

交换律: a ^ b = b ^a, a ^ b ^ a = b 可以用于找奇数个数的数

离散化

离散化:稀疏数组中,10^5个数,值域为 0 ~ 10^9,将值域映射到 0 ~ n

难点:可能存在重复元素,并能及时得到离散化后的值

应用:稀疏数组即数组下标很大,但数组中很多值是空的

IMG_DA2CAA82DDB6-1.jpeg

// 用vector模拟set,可以用下标访问
vector<int> vec;
sort(vec.begin(), vec.end()); // 排序
vec.erase(unique(vec.begin(), vec.end()), vec.end()); // 去重
// 用二分找第一个大于等于x的,相当于lower_bound()
int find(int x) { 
    int l = 0, r = vec.size()-1;
    while (l < r) {
        int mid = l+r>>1;
        if (vec[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r+1; // 从1开始映射
}

数据结构

链表

单链表

/*
* head 头结点下标 存值
* e 存val
* ne 存next
* idx 表示e中当前位置
*/
int head, e[N], ne[N], idx;
// 头插
void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++;
}
// 下标为k的后面插x
void add(int k, int x) { 
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}
// 删k后的点 (-1后的点为0)
void remove(int k) {
    if (k == -1) head = ne[head];
    ne[k] = ne[ne[k]];
}
void init() {
    head = -1;
    idx = 0;
}

邻接表

int head[N];

双链表

优化某些问题

int head, tail;
int e[N], l[N], r[N], idx;
void init() {
    head = -1; 
    tail = -1;
    idx = 0;
}
// 在k右边插入 
// 在k左边插入 add(l[k], x);
void add(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
}
void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

单调栈

应用:找每个数左边第一个比它小/大的数、视野总和、柱状图中最大矩形

有序栈:如果栈为空入栈元素值小于栈顶元素值,则入栈;否则,如果入栈则会破坏栈的单调性,则需要把比入栈元素小的元素全部出栈。

思想:先考虑暴力,然后优化

IMG_75854B600D80-1.jpeg

// STL
for (int i = 0; i < n; i ++ ) {
    cin>>x;
    while (!stk.empty() && stk.top() >= x) stk.pop();
    if (!stk.empty()) cout<<stk.top();
    else cout<<-1;
    cout<<' ';
    stk.push(x);
}
// 数组
for (int i = 0; i < n; i ++ ) {
  cin>>x;
  while (tt && stk[tt] >= x) tt --;
  if (tt) cout<<stk[tt];
  else cout<<-1;
  cout<<' ';
  stk[++tt] = x;
}

队列

单调队列(滑动窗口)

思路:先暴力 再优化,根据单调性,去除不必要的数据和遍历

IMG_802D4A12F0EB-1.jpeg

// 数组模拟队列
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ) {
  while (hh <= tt && q[hh] < i-k+1) hh++;
  while (hh <= tt && a[q[tt]] >= a[i]) tt--;

    q[++tt] = i;
    if (i >= k-1) cout<<a[q[hh]]<<' ';
}
// 双端队列
deque<int> que;
for (int i = 0; i < n; i ++ ) {
  while (!que.empty() && que.front() < i-k+1) que.pop_front(); // 超出窗口大小出队
  // 次新的不如新的小 丢弃
  while (!que.empty() && a[i] <= a[que.back()]) que.pop_back();

  que.push_back(i);
  if (i >= k-1) cout<<a[que.front()]<<' ';
}
// 优先队列
priority_queue<PII, vector<PII>, greater<PII>> que1;
for (int i = 0; i < n; i ++ ) {
    while (!que1.empty() && que1.top().y < i-k+1) que1.pop();

  que1.push({a[i], i});
  if (que1.size() > k-1) cout<<que1.top().x<<' ';
}

KMP

应用:找子串

IMG_E8CB8965BF92-1.jpeg

// 求next
for (int i = 2, j = 0; i <= n; i ++ ) {
    while (j && p[i] != p[j+1]) j = ne[j];
  if (p[i] == p[j+1]) j++;
  ne[i] = j;
}

for (int i = 1, j = 0; i <= m; i ++ ) {
    while (j && s[i] != p[j+1]) { // 不能匹配或j无处可退
      j = ne[j];
  }
  if (s[i] == p[j+1]) j++;
  if (j == n) {
        // 匹配成功
    cout<<i-n<<' ';
    j = ne[j]; // 
  }
}

Trie树

高效存储查找字符串集合

IMG_F19C60B06C11-1.jpeg

// son每个结点的子节点
// cnt以当前点结尾的单词的数量
// 下标为0的点 空节点或者根节点
int son[N][26], cnt[N], idx; 
void insert(char str[]) {
    int p = 0;
    for (int i = 0; str[i] ;i++ ) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx; // 不存在字母u
        p = son[p][u];
    }
    cnt[p] ++;
}
int query(char str[]) { // 返回string出现的次数
    int p = 0;
    for (int i = 0; str[i] ;i++ ) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集 Union Find Set

合并两个集合、询问两个元素是否在一个集合中

基本:树根(代表元素)的编号是整个树的编号

路径压缩:所有孩子都直接指向根节点

按秩合并:将简单的树合并在复杂的树下(计算深度)

朴素并查集

int p[N]; //储存每个点的祖宗节点

int find(int x) { //返回x的祖宗节点 + 递归保证 路径压缩
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

for (int i = 1; i <= n; i ++ ) p[i] = i; //初始化

p[find(a)] = find(b); //合并a,b两个集合

维护size数组的并查集

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x){
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}
// 初始化,假定节点编号是1~n    
for (int i = 1; i <= n; i ++ ){
  p[i] = i;    
  size[i] = 1;
}
// 合并a和b所在的两个集合:先把size求和    
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

维护到祖宗节点距离的并查集

int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x){
    if (p[x] != x){
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
    p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量

完全二叉树

根结点小于等于左右子结点

IMG_06DCF7F7578D-1.jpeg

int h[N]; // 用完全二叉树存堆
// 从根往下调整
void down(int u) {
  int t = u;
  if (u*2 <= size && h[u*2] < h[t]) t = u*2;
  if (u*2+1 <= size && h[u*2+1] < h[t]) t = u*@+1;
  if (u != t) {
    swap(h[u], h[t]);
    down(t);
  }
}
void up(); // 向上调整
// 插入
heap[++size] = x; up(size);
// 求最值(堆顶)
head[1]
// 删除最值
heap[1] = heap[size]; size --; down(1);
// 删除任意元素(用最后一个代替原值并执行down或up,这里都写但实际不会都执行下去)
heap[k] = heap[size]; size --; down(k); up(k);
// 修改任意值
heap[k] = x; down(k); up(k);

搜索与图论

DFS

深搜

BFS

广搜

八皇后

拓扑排序

关键:广搜、入度

IMG_99F1477B4A0A-1.jpeg

bool topsort() {
    queue<int> que;
    for (int i = 1; i <= n; i++) // 初始化 将入度为0的点入队
        if (d[i] == 0) que.push(i);

    while(!que.empty()) {
        int tmp = que.front();
        ans.push_back(tmp);
        que.pop();

        for (auto e : edge[tmp]) {
            d[e] --;
            if (d[e] == 0) que.push(e);
        }
    }
    return ans.size() == n; // 全进入ans则存在拓扑
}

最短路径

n为点数,m为边数

分类

IMG_275108A5538C-1

朴素Dijkstra

稠密图用邻接矩阵

重边保留短边,忽略自环

IMG_E4D127BD4E5A-1

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra() {
    memset(dist, 0x3f, sizeof dist); //初始化 dist 为无穷
    dist[1] = 0;
    for (int i = 0; i < n - 1; i++) {
        int t = -1;     // 在还未确定最短路的点中,找距离最小的点
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        st[t] = true;
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化Dijkstra

稀疏图用邻接表

const int N = 510; // 太大会爆vector
typedef pair<int,int> PII;
int n, m, dist[N], weight[N][N];
memset(weight, 0x3f, sizeof weight);
vector<int> g[N];
bool st[N]; 
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    priority_queue<PII,vector<PII>,greater<>> heap; // 小顶堆
    heap.push({0,1}); // first->距离 second->点 用距离排序
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true
        for (auto vec : g[ver]) {
            if (dist[vec] > distance + weight[ver][vec]) {
                dist[vec] = distance + weight[ver][vec];
                heap.push({dist[vec], vec});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Bellman-Ford

数学

数论

质(素)数

大于等于2的整数中,只包含1和本身这两个约数

质数判断一试除法:

bool is_prime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n/i; i++) 
        if (n % i == 0)
        return false;
  return true;
}

质数判断二分解质因数:

从小到大枚举n的所有因数

Mac使用SecureCRT或终端直接连接跳板机访问内网

一、为什么使用跳板机

由于学校放假,使用跳板机可以连接布置在学校内网的服务器

二、为什么使用SecureCRT

在尝试过Item2写expect连接跳板机后毅然决然的使用了SecureCRT
在这里插入图片描述
没有的可以私信我

三、 连接方法

1、连接跳板机

Configuration => SSH2 => 按照图中输入跳板机数据 => OK保存后点Connect
在这里插入图片描述

2.tab显示绿色的对勾就表示连接成功

直接使用ssh连接内部服务器

ssh 用户名@服务器IP

会跳出一些验证,按提示回复yes即可


四、 终端直连

修改本地和跳板机上的ssh文件

仅第一次连接时需要修改

vim ~/.ssh./config
//添加以下内容
Host *
    ControlPersist yes
    ControlMaster auto
    ControlPath ~/.ssh/%n:%p

终端设置ssh隧道

//连接跳板机作为端口转发
ssh -N -f -L 6000:<内网服务器ip>:22 -p <跳板机端口> username@<跳板机ip> -o TCPKeepAlive=yes
//登录本地的6000端口访问内网服务器
ssh -p 6000 服务器用户名@localhost

五、使用PyCharm连接 编写代码

1、创建新项目
2、选择项目解释器时选择现有解释器,添加SSH解释器
在这里插入图片描述

3、设置好主机ip、端口和用户名
在这里插入图片描述

4、设置服务器与本地文件共享位置

点赞的码农无BUG!