2024年2月

本文分享自华为云社区《
华为云短信服务教你用Rust实现Smpp协议
》,作者: 张俭。

协议概述

SMPP(Short Message Peer-to-Peer)协议起源于90年代,最初由Aldiscon公司开发,后来由SMPP开发者论坛维护和推广。SMPP常用于在SMSC(Short Message Service Center,短信中心)和短信应用之间传输短消息,支持高效的短信息发送、接收和查询功能,是电信运营商和短信服务提供商之间互通短信的主要协议之一。

SMPP协议基于客户端/服务端模型工作。由客户端(短信应用,如手机,应用程序等)先和SMSC建立起TCP长连接,并使用SMPP命令与SMSC进行交互,实现短信的发送和接收。在SMPP协议中,无需同步等待响应就可以发送下一个指令,实现者可以根据自己的需要,实现同步、异步两种消息传输模式,满足不同场景下的性能要求。

时序图

绑定transmitter模式,发送短信并查询短信发送成功

绑定receiver模式,从SMSC接收到短信

协议帧介绍

Untitled.png

在SMPP协议中,每个PDU都包含两个部分:SMPP Header和SMPP Body。

SMPP Header

Header包含以下字段,大小长度都是4字节:

  • Command Length:整个PDU的长度,包括Header和Body。
  • Command ID:用于标识PDU的类型(例如,BindReceiver、QuerySM等)。
  • Command Status:响应状态码,表示处理的结果。
  • Sequence Number:序列号,用来匹配请求和响应。

用Rust实现SMPP协议栈里的BindTransmitter

本文的代码均已上传到
smpp-rust

选用Tokio作为基础的异步运行时环境,tokio有非常强大的异步IO支持,也是rust库的事实标准。

代码结构组织如下:

├── lib.rs
├──
const.rs
├── protocol.rs
├── smpp_client.rs
└── smpp_server.rs
  • lib.rs
    Rust项目的入口点
  • const.rs
    包含常量定义,如commandId、状态码等
  • protocol.rs
    包含PDU定义,编解码处理等
  • smpp_client.rs 实现smpp客户端逻辑
  • smpp_server.rs 实现

利用rust原子类实现sequence_number

sequence_number是从1到0x7FFFFFFF的值,利用Rust的AtomicI32来生成这个值。

use std::sync::atomic::{AtomicI32, Ordering};
use std::num::TryFromIntError;
structBoundAtomicInt {
min: i32,
max: i32,
integer: AtomicI32,
}

impl BoundAtomicInt {
pub fn
new(min: i32, max: i32) ->Self {
assert
!(min <= max, "min must be less than or equal to max");
Self {
min,
max,
integer: AtomicI32::
new(min),
}
}

pub fn next_val(
&self) -> Result<i32, TryFromIntError>{
let next
= self.integer.fetch_update(Ordering::SeqCst, Ordering::SeqCst, |x|{
Some(
if x >= self.max { self.min } else { x + 1})
})
?;
Ok(next)
}
}

在Rust中定义SMPP PDU

pub structSmppPdu {
pub header: SmppHeader,
pub body: SmppBody,
}

pub
structSmppHeader {
pub command_length: i32,
pub command_id: i32,
pub command_status: i32,
pub sequence_number: i32,
}

pub
enumSmppBody {
BindReceiver(BindReceiver),
BindReceiverResp(BindReceiverResp),
BindTransmitter(BindTransmitter),
BindTransmitterResp(BindTransmitterResp),
QuerySm(QuerySm),
QuerySmResp(QuerySmResp),
SubmitSm(SubmitSm),
SubmitSmResp(SubmitSmResp),
DeliverSm(DeliverSm),
DeliverSmResp(DeliverSmResp),
Unbind(Unbind),
UnbindResp(UnbindResp),
ReplaceSm(ReplaceSm),
ReplaceSmResp(ReplaceSmResp),
CancelSm(CancelSm),
CancelSmResp(CancelSmResp),
BindTransceiver(BindTransceiver),
BindTransceiverResp(BindTransceiverResp),
Outbind(Outbind),
EnquireLink(EnquireLink),
EnquireLinkResp(EnquireLinkResp),
SubmitMulti(SubmitMulti),
SubmitMultiResp(SubmitMultiResp),
}

实现编解码方法

impl SmppPdu {
pub fn encode(
&self) -> Vec<u8>{
let mut body_buf
= match &self.body {
SmppBody::BindTransmitter(bind_transmitter)
=>bind_transmitter.encode(),
_
=> unimplemented!(),
};

let command_length
= (body_buf.len() + 16) asi32;
let header
=SmppHeader {
command_length,
command_id: self.header.command_id,
command_status: self.header.command_status,
sequence_number: self.header.sequence_number,
};

let mut buf
=header.encode();
buf.append(
&mut body_buf);
buf
}

pub fn decode(buf:
&[u8]) -> io::Result<Self>{
let header
= SmppHeader::decode(&buf[0..16])?;
let body
=match header.command_id {
constant::BIND_TRANSMITTER_RESP_ID
=> SmppBody::BindTransmitterResp(BindTransmitterResp::decode(&buf[16..])?),
_
=> unimplemented!(),
};
Ok(SmppPdu { header, body })
}
}

impl SmppHeader {
pub(crate) fn encode(
&self) -> Vec<u8>{
let mut buf
= vec![];
buf.extend_from_slice(
&self.command_length.to_be_bytes());
buf.extend_from_slice(
&self.command_id.to_be_bytes());
buf.extend_from_slice(
&self.command_status.to_be_bytes());
buf.extend_from_slice(
&self.sequence_number.to_be_bytes());
buf
}

pub(crate) fn decode(buf:
&[u8]) -> io::Result<Self>{if buf.len() < 16{return Err(io::Error::new(io::ErrorKind::InvalidData, "Buffer too short for SmppHeader"));
}
let command_id
= u32::from_be_bytes(buf[0..4].try_into().unwrap());
let command_status
= i32::from_be_bytes(buf[4..8].try_into().unwrap());
let sequence_number
= i32::from_be_bytes(buf[8..12].try_into().unwrap());
Ok(SmppHeader {
command_length:
0,
command_id,
command_status,
sequence_number,
})
}
}

impl BindTransmitter {
pub(crate) fn encode(
&self) -> Vec<u8>{
let mut buf
= vec![];
write_cstring(
&mut buf, &self.system_id);
write_cstring(
&mut buf, &self.password);
write_cstring(
&mut buf, &self.system_type);
buf.push(self.interface_version);
buf.push(self.addr_ton);
buf.push(self.addr_npi);
write_cstring(
&mut buf, &self.address_range);
buf
}

pub(crate) fn decode(buf:
&[u8]) -> io::Result<Self>{
let mut offset
= 0;
let system_id
= read_cstring(buf, &mut offset)?;
let password
= read_cstring(buf, &mut offset)?;
let system_type
= read_cstring(buf, &mut offset)?;
let interface_version
=buf[offset];
offset
+= 1;
let addr_ton
=buf[offset];
offset
+= 1;
let addr_npi
=buf[offset];
offset
+= 1;
let address_range
= read_cstring(buf, &mut offset)?;

Ok(BindTransmitter {
system_id,
password,
system_type,
interface_version,
addr_ton,
addr_npi,
address_range,
})
}
}

实现同步的bind_transmitter方法

pub asyncfn bind_transmitter(&mut self,
bind_transmitter: BindTransmitter,
)
-> io::Result<BindTransmitterResp>{if let Some(stream) = &mut self.stream {
let sequence_number
=self.sequence_number.next_val();
let pdu
=SmppPdu {
header: SmppHeader {
command_length:
0,
command_id: constant::BIND_TRANSMITTER_ID,
command_status:
0,
sequence_number,
},
body: SmppBody::BindTransmitter(bind_transmitter),
};
let encoded_request
=pdu.encode();
stream.write_all(
&encoded_request).await?;

let mut length_buf
= [0u8; 4];
stream.read_exact(
&mut length_buf).await?;
let msg_length
= u32::from_be_bytes(length_buf) as usize - 4;

let mut msg_buf
= vec![0u8; msg_length];
stream.read_exact(
&mut msg_buf).await?;

let response
= SmppPdu::decode(&msg_buf)?;if response.header.command_status != 0{
Err(io::Error::
new(
io::ErrorKind::Other,
format
!("Error response: {:?}", response.header.command_status),
))
}
else{//Assuming response.body is of type BindTransmitterResp match response.body {
SmppBody::BindTransmitterResp(resp)
=>Ok(resp),
_
=> Err(io::Error::new(io::ErrorKind::InvalidData, "Unexpected response body")),
}
}
}
else{
Err(io::Error::
new(io::ErrorKind::NotConnected, "Not connected"))
}
}

运行example,验证连接成功

use smpp_rust::protocol::BindTransmitter;
use smpp_rust::smpp_client::SmppClient;

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>>{
let mut client
= SmppClient::new("127.0.0.1", 2775);
client.connect().
await?;
let bind_transmitter
=BindTransmitter{
system_id:
"system_id".to_string(),
password:
"password".to_string(),
system_type:
"system_type".to_string(),
interface_version:
0x34,
addr_ton:
0,
addr_npi:
0,
address_range:
"".to_string(),
};
client.bind_transmitter(bind_transmitter).
await?;
client.close().
await?;
Ok(())
}

Untitled 1.png

相关开源项目

总结

本文简单对SMPP协议进行了介绍,并尝试用rust实现协议栈,但实际商用发送短信往往更加复杂,面临诸如流控、运营商对接、传输层安全等问题,可以选择华为云消息&短信(Message & SMS)服务,华为云短信服务是华为云携手全球多家优质运营商和渠道,为企业用户提供的通信服务。企业调用API或使用群发助手,即可使用验证码、通知短信服务。

点击关注,第一时间了解华为云新鲜技术~

转载至我的博客
https://www.infrastack.cn
,公众号:架构成长指南

背景

随着公司业务快速发展,对业务数据进行增长分析的需求越来越迫切,与此同时我们的业务数据量也在快速激增、每天的数据新增量大概在30w 左右,一年就会产生1 个亿的数据,显然基于传统MySQL数据库已经无法支撑满足以上需求

基于上述需求和痛点,决定提供一个灵活的多维实时查询和分析平台,帮助业务线做精细化运营。

业务分析

现有业务数据有以下特点,
查询多、更新少
,基本不会更新1 个月以前的数据,但是查询范围较大,有时需要查询几年前的数据,而且数据会以年、月等不同维度统计来进行增长分析

因此以上场景使用 OLTP 引擎不是特别适合,OLAP则更为适合

这里可能有些人员不懂什么是 OLAP,下面是一个OLAP与OLTP对比图

技术选型

实时数仓

以上场景确定后,我们就开始了框架选型,最终确定了 Doris,理由如下

  • 性能满足要求
  • 兼容MySQL 协议
  • 运维成本较低
  • 架构足够简单
  • 社区活跃,支持力度高

下面是一个选型对比,没有好坏,只是Doris适合我们

实时数据捕获

实时数据,采用
Fink CDC
进行捕获,
Fink CDC Connectors 是Apache Flink
的一组源连接器,使用变更数据捕获 (CDC) 从不同数据库中获取变更,而获取变更是通过Debezium监听Binlog 日志,获取到更新数据以后,可以对数据进行转换,然后在根据doris 提供的Flink 插件Doris flink connecto导入到 Doris 里面

具体示例,可以参考:
https://mp.weixin.qq.com/s/ssXocqCyoSVuRFBi2hzCKQ

为什么需要实时数据捕获?

Doris 只是一个数据仓库,他提供的功能是实时数据统计、查询和存储,他不支持主动实时抓取数据,需要借助第三方工具来进行实现,比如我们在 MySQL修改了一条数据,怎么让 Doris 进行更新?目前想到的答案是主动发送更新数据至Kafka,然后Doris订阅 KafKa 的 Topic 然后进行实时同步,虽然以上能实现我们想要的功能,但是有点复杂,业务每次操作都要发送 Kafka,同时要想对数据进行加工,工作量相对较,正因为有以上问题,所以我们采用Flink CDC

数据调度平台

数据调度平台,采用海豚调度器(DolphinScheduler),它也是国人开源的一款分布式可扩展的大数据调度平台,使用Java 语言开发,目前已经成为Apache 项目,它提供了强大的DAG可视化界面,所有流程定义都是可视化,通过拖拽任务完成定制DAG,同时支持 30+类型的任务,比如执行 SQL、shell 、DataX 等类型,官网地址:
https://dolphinscheduler.apache.org

为什么需要数据调度平台?

数据转换
:通过Flink 抽取的数据,如果还想对这些数据进行加工处理,比如实时同步的业务数据,需要再次转换为分钟级、小时级、天、月等维度的报表

非实时数据同步
:通过调度DataX,以分钟、小时、天为单位进行源数据同步

定时归档
:比如每晚同步业务数据库一个月前数据,同步完成之后,在执行删除任务,删除业务库一个月前的数据

数仓数据分层

数据仓库的分层是一种常见的设计模式,它将数据仓库划分为不同的层级,每个层级有不同的功能和用途。

数仓层内部的划分不是为了分层而分层,它是数据仓库经过了建模和 ETL 之后真正开始对外提供服务的地方,因此数仓层内的划分更应该符合使用者的思维习惯。 DW 内的分层没有最正确的,只有最适合你的。

ODS层

Operation Data Store 数据准备区,也称为贴源层。数据仓库源头系统的数据表通常会原封不动的存储一份,这称为ODS层,是后续数据仓库加工数据的来源。

DWD层

data warehouse details 细节数据层,是业务层与数据仓库的隔离层。主要对ODS数据层做一些
数据清洗和规范化
的操作,数据清洗:去除空值、脏数据、超过极限范围的

DWS层

data warehouse service 数据服务层,基于DWD上的基础数据,整合汇总成分析某一个主题域的服务数据层,一般是宽表。用于提供后续的业务查询,OLAP分析,数据分发等。

  • 用户行为,轻度聚合
  • 主要对ODS/DWD层数据做一些轻度的汇总。

注意:数仓层内部的划分不是为了分层而分层,它是数据仓库经过了建模和 ETL 之后真正开始对外提供服务的地方,因此数仓层内的划分更应该符合使用者的思维习惯。 DW 内的分层没有最正确的,只有最适合你的。

命名规范

系统架构

经过前面的技术选型,以及分层定义,我们最终架构如下

数据查询

假设语句已经同步到doris,那么怎么进行展现,这里有很多种方式,比如通过BI工具,例如:power bi、dataEase、Davinci等,同时Doris 支持mysql 协议,我们为了让之前的业务改动,对后端接口实现进行了替换,通过 mybatis 动态解析 sql,并调用 doris进行查询,架构如下

示例介绍

Flink实时同步

具体查看锋哥的文章,
https://mp.weixin.qq.com/s/ssXocqCyoSVuRFBi2hzCKQ

DolphinScheduler准实时同步

同步业务数据库mysql中register表至doris的ods_test_mysql_register_s表中,并对业务数据进行删除

1. 创建datax文件

在资源中心创建各个团队文件夹,并在文件夹中创建对应datax文件

2. 创建任务

进入项目管理/工作流定义目录,点击创建工作流

选择shell任务,worker分区选择datax,

datax组为自行创建,实际配置时,以本地执行环境为准

选择资源,并编写datax启动命令

如果迁移完,需要进行原数据删除,则新建sql任务,编写sql语句,进行清理

3. 依赖关系创建

第一步进行datax数据同步第二步进行原数据清理,如下图连线就是依赖关系

4. 全局参数设置

参数可以设置为动态参数,这里为了测试方便所以为固定值

例如:$[yyyy-MM-dd 00:00:00-15] 表示前15天,具体参考
dolphinscheduler内置参数说明

5. 启动任务

首选点击对应任务进行上线,在配置定时任务,如果测试连通性,则点击启动按钮可以立即测试

参考链接

基于 Flink SQL CDC 的实时数据同步方案

Apache Flink CDC 批流融合技术原理分析

详解数据仓库明星产品Doris背后的技术奥秘

Flink CDC结合Doris flink connector实现Mysql数据实时入Apache Doris

扫描下面的二维码关注我们的微信公众帐号,在微信公众帐号中回复◉加群◉即可加入到我们的技术讨论群里面共同学习。

\(\small{(本文统一将c[i]视作cost,w[i]视作worth,下面的代码用这两个变量表示费用和价值)}\)
\(\Large\textbf{1. 01背包}\)

  • \(\large\textbf{描述:}\)
    有n个物品,每个物品只有一件,第i个物品体积为vi,价格为ci。现在有一个体积为V的背包,请你从n件物品里选出若干件放进背包里,使得背包里的物品价值最大。
  • \(\large\textbf{思路:}\)
    01背包的特点是:每种物品只有一件,可以选择放或不放。
    我们可以根据此特点进行动态规划(DP),设f[i][j]表示前i件物品放入一个容量为j的背包中可以获得的最大价值,则易得
    状态转移方程
dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])

(详解:在“将前i个物品放入容量为j的背包中”的这个子问题中,由题意,我们只有
\(\textbf{放}\)

\(\textbf{不放}\)
两种选择,那么就转化为一个只与前i-1个物品有关的问题。如果不放第i件物品,那么就是“前i-1件物品放入容量为j的背包中”,最大价值为f[i-1][j];如果放第i件物品,那么就是“前i-1件物品放入剩下的容量为j-c[i]的背包中”,最大价值为f[i-1][j-c[i]]+w[i])

由此可得01背包的
\(\textbf{最原始}\)
代码

$\large\textbf{code}$
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define Elaina 0
int n,m,V,c[N],w[N],dp[N][N],ans=0;
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=V;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=c[i]){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
			}
		}
	}
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[n][V];
	return Elaina;
} 

以上代码的时间和空间的复杂度均为O(V*N),其中时间已经不能进一步优化了,但是空间可以

\(\textbf{滚动数组优化code}\)

code
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define Elaina 0
int n,m,V,c[N],w[N],ans=0;
int dp[2][N];//滚动数组优化 只开2行数组 
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=V;j++){
			dp[i&1][j]=dp[(i-1)&1][j];
			if(j>=c[i]){
				dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-c[i]]+w[i]);
			}
		}
	}
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[n&1][V];
	return Elaina;
}

\(\textbf{一维优化code}\)

code
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define Elaina 0
int n,m,V,c[N],w[N],ans;
int dp[N];//一维数组优化
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=V;j>=c[i];j--){
			dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
		}
	}
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[V];
	return Elaina;
}

\(\Large\textbf{2. 完全背包}\)

  • \(\large\textbf{描述:}\)
    设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和为最大。
  • \(\large\textbf{思路:}\)
    完全背包的特点是:每种物品有无数件,可以选择放若干件或不放。
    设k为取的物品的数量,依据01背包思路,易得状态转移方程为
dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*c[i]]+k*w[i])

完整代码为

$\large\textbf{code}$
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define Elaina 0
int n,m,V,c[N],w[N],dp[N][N],ans=0;
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=V;j++){
			for(int k=0;k*c[i]<=j;k++){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*c[i]]+k*w[i]);
			}
		}
	}
}
int main(){
	cin>>V>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[n][V];
	return Elaina;
}

\(\textbf{一维优化code}\)

code
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define Elaina 0
int n,m,V,c[N],w[N],dp[N],ans=0;
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=c[i];j<=V;j++){
			dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
		}
	}
}
int main(){
	cin>>V>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i];
	}
	bag();
	cout<<dp[V];
	return Elaina;
}

\(\Large\textbf{3. 多重背包}\)

  • \(\large\textbf{描述:}\)
    有N种物品和一个容量为V的背包。第i ii种物品最多有p[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
  • \(\large\textbf{思路:}\)
    这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有p[i]+1种策略:取0件,取1件……取p[i]件。令dp[i][j]表示前i种物品恰放入一个容量为j的背包的最大价值,则有状态转移方程:
dp[i][j]=max(dp[i][j],dp[i-1][j-k*c[i]]+k*w[i])
$\large\textbf{code}$
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define Elaina 0
int n,m,V,c[N],w[N],dp[N][N],s[N];
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=V;j++){
			for(int k=0;k<=s[i]&&k*c[i]<=j;k++){
				dp[i][j]=max(dp[i][j],dp[i-1][j-k*c[i]]+k*w[i]);
			}
		}
	}		            
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i]>>s[i];
	}
	bag();
	cout<<dp[n][V];
	return Elaina;
}

\(\textbf{一维优化code}\)

code
#include<bits/stdc++.h>
using namespace std;
#define N 1010
#define Elaina 0
int n,m,V,c[N],w[N],dp[N],s[N];
void bag(){
	for(int i=1;i<=n;i++){
		for(int j=V;j>=0;j--){
				for(int k=0;k<=s[i]&&k*c[i]<=j;k++){
					dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
				}
			} 
	}		            
}
int main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i]>>s[i];
	}
	bag();
	cout<<dp[V];
	return Elaina;
}

\(\Large\textbf{4. 混合背包}\)

  • \(\large\textbf{描述:}\)
    一个旅行者有一个最多能用V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

(就是把前01背包、完全背包、多重背包搓起来 搓吧搓吧就出来了(^_−)☆)

直接请出代码君

code
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define inf 0x3f3f3f3f
#define Elaina 0
int idx=0,n,V,c[N],w[N],dp[N],s[N],ans=inf;
void bag(){
	for (int i=1; i<=n; i++){
		if(s[i]==1){
			for(int j=V;j>=c[i];j--){
				dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
			}
		}
		else if(s[i]==0){
			for(int j=c[i];j<=V;j++){
				dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
			}
		}else{
			for(int j=V;j>=0;j--){
				for(int k=0;k<=s[i]&&k*c[i]<=j;k++){
					dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
				}
			} 
		} 
	}
}
int main(){
	cin>>V>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i]>>s[i];
	}
	bag();
	cout<<dp[V];
	return Elaina;
}

\(\Large\textbf{5. 分组背包}\)

  • \(\large\textbf{描述:}\)
    一个旅行者有一个最多能用V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大
  • \(\large\textbf{死路:}\)
    这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。设dp[k][j]表示前k组物品花费费用j的最大价值,则有状态转移方程为:
dp[k][j]=max(dp[k][j],dp[k-1][j-c[i]]+w[i]

\(\textbf{一维优化code}\)

code
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define ll long long
#define inf 0x3f3f3f3f
#define Elaina 0
int n,t,V,T,c[N],w[N],dp[N],g[N][N];
void bag(){
	for (int i=1; i<=T; i++){
		for(int j=V;j>=0;j--){
			for(int k=1;k<=g[i][0];k++){
				int x=g[i][k];
				if(j>=c[x]){
					dp[j]=max(dp[j],dp[j-c[x]]+w[x]);
				}
			}
		}
	}
}
int main(){
	cin>>V>>n>>T;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>w[i]>>t;
		g[t][++g[t][0]]=i;
	}
	bag();
	cout<<dp[V];
	return Elaina;
}

\(\Large\textbf{6. 二维背包}\)

  • \(\large\textbf{描述:}\)
    对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设第i ii件物品所需的两种代价分别为c[i]和g[i]。两种代价可付出的最大值(两种背包容量)分别为V和M。物品的价值为w[i]。
  • \(\large\textbf{死路:}\)
    费用加一维,状态也加一维即可。设dp[i][j][k]表示前i件物品付出的代价为j和k是的最大价值,易得状态转移方程为
dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-c[i]][k-g[i]]+w[i]

\(\textbf{二维优化code}\)

code
#include<bits/stdc++.h>
using namespace std;
#define N 10100
#define Elaina 0
int M,n,V,c[N],w[N],dp[N][N],g[N];
void bag(){
	for(int i=1;i<=n;i++)
	 	for(int j=V;j>=c[i];j--)
	  		for(int k=M;k>=g[i];k--)
	   	  		dp[j][k]=max(dp[j][k],dp[j-c[i]][k-g[i]]+w[i]);

}
int main(){
	cin>>n>>V>>M;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>g[i]>>w[i];
	}
	bag();
	cout<<dp[V][M];
	return Elaina;
}

\(\Large\textbf{7. 有依赖的背包(树上背包)}\)
鸽一会 咕咕 ヾ(o・ω・)ノ

有段时间没有更新IDEA了,早上看到 IntelliJ IDEA 2024.1 EAP 5发布的邮件提示,瞄了一眼,发现真的是越来越强了,其中不少功能对我来说还是非常有用的。也许这些能力对关注DD的小伙伴也有帮助,所以搞篇博客介绍和推荐一下。

Spring、Quarkus等主流框架的支持增强

  1. Search Everywhere功能中增加
    Endpoints
    选项卡

具体如下图所示:

开发者可以在这里直接搜索通过Spring、Quarkus、Micronaut、Ktor实现的接口来找到具体的代码实现位置。这个功能非常实用,尤其是对于接手老项目的开发者来说,可以快速的定位接口实现来完成开发任务或问题排查。

  1. 增强Spring Bean的自动补全和自动装配

IntelliJ IDEA 现在为应用程序上下文中的所有 Bean 提供自动补全功能,并自动连接它们。

如果 bean 通过构造函数具有自动装配依赖项,则相关字段也会通过构造函数自动装配。

同样,如果通过字段或 Lombok 的
@RequiredArgsConstructor
注释注入依赖项,则新 bean 会自动通过字段连接。

  1. 增强 Spring 模型图

在该版本中用户访问Spring模型图变得更加容易,可以如下图这样点击Spring标识的行标记直接跳转:

也可以使用快捷键
⌥⏎
(MacOS) 或
Alt+Enter
(Windows)来生成和跳转。

同时,该版本还引入了新的图标,增强了 Spring 模型图的可视化内容,如:
Components

Controllers

Repositories
。此外,您现在可以方便地切换库中 Bean 的可见性(默认情况下是隐藏的)。

HTTP Client的改进

HTTP Client现在提供更多身份验证选项,包括
PKCE
授权代码和设备授予流程。它还支持令牌和身份验证请求的额外参数。

现在它可以自动处理
code_challenge

passes code_verifier
的生成,以便在
PKCE
请求中检索令牌。

这个版本的HTTP Client 可以使用 Netty 作为其低级网络库。通过支持 SSL、代理和 HTTP/2,使我们能够在 HTTP 客户端中实现 HTTP/2 的支持。

此外,HTTP Client的工具栏外观,也与新的 UI 风格保持一致,提供更加美观的用户体验。

GitHub Action的支持增强

  1. Workflow 上下文的支持

现在可以为各种 GitHub Action上下文引入了广泛的自动完成支持,包括
github.*

env.*

steps.*

inputs.*

这个优化非常有用,可以有效的降低编写复杂工作流脚本的过程,开发人员不用再去频繁的搜索上下文中涉及的参数了。

该优化在
YAML
文件配置中也同样有效:


YAML
文件中,开发者还可以使用
branding
功能使用特定图标和颜色指示器自定义 GitHub 上操作的外观。

此功能使操作创建者能够在 GitHub Marketplace 和工作流程中直观地区分他们的操作,使它们更易于识别和用户友好。通过在
action.yml
文件中指定图标和颜色,开发人员可以一目了然地传达其操作的目的,从而增强整体用户体验。这种可视化定制有助于对操作进行分类,并帮助用户快速识别 CI/CD 管道所需的工具。

  1. Docker 镜像自动补全

此增强功能在 GitHub 工作流程文件中提供image和tag建议,从而更轻松地将 Docker 容器集成到您的操作中。

  1. JavaScript 文件路径补全

文件路径完成功能会自动建议文件路径,从而简化 JavaScript 操作的配置并简化工作流程执行。

其他更新

  • 优化JSON schema的处理: 优化了 JSON 模式验证和完成背后的代码。因此,IDE 现在可以更快地处理此任务并减少内存消耗。在使用 Azure Pipelines 的现实文件中,架构检查现在速度提高了 10 倍。

  • 现在可以在所有常见场景中轻松完成 HTTP Header,例如使用 Spring WebClient 和 RestAssured 测试。当遇到预期值时,会自动出现完成弹出窗口。

另外,DD最近把博客重新增加了板块,正在维护几个有意思的长期连载专栏,其中一个就是
《玩转IDEA》
,这次换了工具,直接采用电子文档的形式,阅读体验更好,​对这些内容感兴趣的,可以关注起来!

欢迎关注我的公众号:程序猿DD。第一时间了解前沿行业消息、分享深度技术干货、获取优质学习资源

卸载home

备份home分区文件

# 新系统无视
tar cvf /tmp/home.tar /home

修改fstab(这一步非常重要,千万别漏了)

准备卸载/home文件系统,centos启动时会对/etc/fstab的内容逐一检测,由于fstab默认有/home,如果不修改fstab,重启之后会发现centos跪了。
所以卸载之前,要先注释掉/home,不让系统开机检测/home。

#  编辑fstab, vim命令 Not Found Command 使用 vi命令
vim /etc/fstab
#  注释掉/home的内容,:wq保存
#/dev/mapper/centos-home /home                   xfs     defaults        0 0

安装psmisc

yum install -y psmisc

Psmisc软件包包含三个帮助管理/proc目录的程序,安装下列程序: fuser、 killall、pstree和pstree.x11(到pstree的链接)

  • fuser:显示使用指定文件或者文件系统的进程的PID。
  • killall:杀死某个名字的进程,它向运行指定命令的所有进程发出信号。
  • pstree:树型显示当前运行的进程。
  • pstree.x11:与pstree功能相同,只是在退出前需要确认。

卸载home文件系统

umount /home

如果提示无法卸载,是因为有进程占用/home,可以用下面的命令来停止占用的进程。

fuser -km /home/

删除/home所在的lv

lvremove /dev/mapper/centos-home

接着会出现确认的内容,输入“y”,回车。

扩大root

扩展/root所在的lv

vgdisplay命令查看卸载home后所空闲的盘符空间

[root@localhost ~]# vgdisplay
  --- Volume group ---
  VG Name               centos
  System ID             
  Format                lvm2
  Metadata Areas        1
  Metadata Sequence No  5
  VG Access             read/write
  VG Status             resizable
  MAX LV                0
  Cur LV                2
  Open LV               2
  Max PV                0
  Cur PV                1
  Act PV                1
  VG Size               <299.00 GiB
  PE Size               4.00 MiB
  Total PE              76543
  Alloc PE / Size       14816 / <57.88 GiB
  Free  PE / Size       61727 / 241.12 GiB
  VG UUID               DFiNzR-74ux-GIsE-Ta03-fPoC-cXfX-An0PLX

Free PE / Size 则是随即要扩展给/root的空间,记住后面的这个数字

lvextend -L + 241G /dev/mapper/centos-root


提示centos/root 从50.00 GiB 变成了291.00 GiB,逻辑卷centos/root调整成功,但别高兴的太早,此时运行df命令,你会发现/dev/mapper/centos-root,并没有变大

[root@localhost ~]# df
文件系统                   1K-块    已用     可用 已用% 挂载点
devtmpfs                 8120996       0  8120996    0% /dev
tmpfs                    8132952       0  8132952    0% /dev/shm
tmpfs                    8132952   17276  8115676    1% /run
tmpfs                    8132952       0  8132952    0% /sys/fs/cgroup
/dev/mapper/centos-root 52403200 1813004 50590196    4% /
/dev/sda1                1038336  185080   853256   18% /boot
tmpfs                    1626592       0  1626592    0% /run/user/0

接下来还有最重要的一步

扩展/root文件系统

xfs_growfs /dev/mapper/centos-root

检查root文件系统的空间

最后使用df -h 命令检查一下 /dev/mapper/centos-root 容量

[root@localhost ~]# df -h
文件系统                 容量  已用  可用 已用% 挂载点
devtmpfs                 7.8G     0  7.8G    0% /dev
tmpfs                    7.8G     0  7.8G    0% /dev/shm
tmpfs                    7.8G   17M  7.8G    1% /run
tmpfs                    7.8G     0  7.8G    0% /sys/fs/cgroup
/dev/mapper/centos-root  291G  1.8G  290G    1% /
/dev/sda1               1014M  181M  834M   18% /boot
tmpfs                    1.6G     0  1.6G    0% /run/user/0