首页 文章 精选 留言 我的

精选列表

搜索[构建环境],共10000篇文章
优秀的个人博客,低调大师

递推的思维构建与技巧实现

递推是一种用若干步可重复运算来解决复杂问题的方法。 1.一维递推 1.1 问题描述 有一个n层的楼梯,每次只可以向上爬1层或者2层,问爬完n层共有多少种不同的方式呢? 1.2 分析 设f(n)表示n层楼总共不同的方式。 假设此时位于第i层,因为每次只能爬1层或2层,所以到第i层只有2种方式。 从第i-1层爬上来。 从第i-2层爬上来。 所以得到递推公式为f(n)=f(n-1)+f(n-2)。前2项之和等于第3项,其实就是斐波那契数列,1,1,2,3,5,8,13,21... 1.3 代码实现 f[0]=1;f[1]=1; for(inti=2;i<n;i++){ f[i]=f[i-1]+f[i-2] } cout<<f[n-1]<<endl; 1.4 空间优化 每一步的递推只与前2步有关,所以只需要记录前2步的方案数,用滚动数组,而不需要开O(n)的空间。手动赋值 intf[3]; f[0]=1; f[1]=1; for(inti=2;i<10;++i){ f[2]=f[1]+f[0]; f[0]=f[1]; f[1]=f[2]; cout<<f[2]<<endl; } 取模滚动 intf[3]; f[0]=1; f[1]=1; for(inti=2;i<10;++i){ f[i%3]=f[(i-1)%3]+f[(i-2)%3]; cout<<f[i%3]<<endl; } 如果只与前一个状态有关,比如f[n]=f[n-1]+1,可以用0,1滚动,这个在动态规划中会比较常用。 intf[2],t=0; f[0]=1; for(inti=2;i<10;++i){ t=1-t; f[t]=f[1-t]+1; cout<<f[t]<<endl; } 递推和动态规划最大的区别:递推的每一步是所有方案数的加和,而动态规划在每一步递推中,需要用来选取一个最优策略。本质其实都是通过重复的小规模子问题推导出大规模的结果。 1.5 时间优化 斐波那契数列递推公式很简单,但数据很大时,效率就比较低,因为递推是O(n)复杂度。 通过矩阵公式变换可将加法变为乘法 如下将递推公式放入矩阵: 假设:则: 可以通过矩阵幂乘快速求出,时间复杂度为,再带入上式即可获得数列值。 具体可以看另一篇递推优化-矩阵幂乘 2.多维递推 2.1 问题描述 从原点出发,每次只能向东,向北,向西走,且不能走已经走过的地方,问走n步共有多少种不同的方式呢? 2.2 分析 假设已经走到第i步,因为不能走已经走过的地方,那这一步能走的方式只会与上一步有关。因为每次走一步,要保证不走回头路,就保证不走上一步走过的地方就行了。 每次有3个选择,即向东,向北,向西。 第i-1步向东走,那么第步只能向北、向东。 第i-1步向西走,那么第步只能向北、向西。 第i-1步向北走,那么第步可以向北、向东,向西。 一维的f[n]只能记录一个总数,而不能记录状态,所以要再多一维记录上一步走的状态。 设f[n][0], f[n][1], f[n][2]分别表示:第步向东、向西、向北走总共不同的方式。 则有如下递推关系: f[n][0] = f[n - 1][0] + f[n - 1][2]; f[n][1] = f[n - 1][1] + f[n - 1][2]; f[n][2] = f[n - 1][0] + f[n - 1][1] + f[n - 1][2]; 2.3 代码实现 intf[100][3]={0}; f[0][0]=1; f[0][1]=1; f[0][2]=1; for(inti=1;i<n;++i){ f[i][0]=f[i-1][0]+f[i-1][2]; f[i][1]=f[i-1][1]+f[i-1][2]; f[i][2]=f[i-1][0]+f[i-1][1]+f[i-1][2]; } cout<<f[n-1][0]+f[n-1][1]+f[n-1][2]<<endl; 2.4 进一步优化 设第n步的总方案数为s[n], s[n]=f[n][0]+f[n][1]+f[n][2]。 s[n]=2f[n-1][0]+2f[n-1][1]+3f[n-1][2]。 s[n]=2s[n-1]+f[n-1][2]。 而f[n-1][2]=f[n-2][0]+f[n-2][1]+f[n-2][2]=s[n-2]。 得s[n]=2s[n-1]+s[n-2]。 所以对公式变形,也可以通过一维的方式完成递推,但这个关系无法直接通过建模构造出来。 3.图递推 3.1 问题描述 在一个的二维地图中,一个人从左上角走到右下角,每次只能向右或者向下走,问到终点共有多少种不同的方式呢? 3.2 分析 假设已经位于某个位置,因为只能向右或者向下走,那上一步只能从上或者从左走过来。 设f[i][j]表示走到坐标总共的方案数。 则f[i][j]=f[i-1][j]+f[i][j-]。 3.3 代码实现 intf[10][10]={0}; f[0][0]=1; for(inti=0;i<n;++i){ for(intj=0;j<m;++j){ if(i-1>=0){ f[i][j]+=f[i-1][j]; } if(j-1>=0){ f[i][j]+=f[i][j-1]; } } } 3.4 进一步思考 要到达终点,一定要向下走n-1步,向右走m-1步。 把每一步组合在一起来看,其实问题就等价于在n+m-2步中选择n-1步向下走,或者选择m-1步向右走,通过排列组合公式就可以直接得到结果。 4.状态压缩递推 4.1 问题描述 在一个的棋盘中放置棋子,有一些地方不能放置。要求放置棋子时任意2个棋子不能在同1行或同1列,问放置k个棋子有多少种不同的方式呢? 4.2 分析 对于每1个位置,只会有2种情况,就是放或不放。在数据规模不大的情况下可以用DFS(深度优先搜索)枚举所有的情况就可以了。 那有没有更好的方法呢? 这个最终是要求方案总数,而不需要考虑每一步是否需要择优,所以是符合递推模型,接下来就是怎么找出递推关系。 先分析一些隐含的规律,把问题理得更清晰: 每1行或者每1列都只能放置1个棋子,所以按每一行来枚举放置方法。 在尝试第i行时,每一个位置(i,j)能不能放置,不只是跟上一行有关,而是跟之前的所有行都有关。这就说明需要记录之前放置的方法,也就是状态。 那怎么记录之前放置的方案状态呢,这就要用到状态压缩。状态压缩:本质就是用二进制记录对应位置的2种状态,0表示不放,1表示放。 对于n个位置,就可以用个十进制数来表示所有放置的方案。 继续回到上面的问题,在尝试第i行时,能否放置跟之前的i-1行都有关,意味着需要记录之前所有行放置的状态。 但看下面2种情况,图1和图2对于在尝试放置第3行时,其实是等价的,前2列都是不能放置。也就是说这2种方案数是可以直接合并的,因为每1列也只能放一个,所以放置的方案状态也可以直接合并成一行。 用f[i][j]表示前i行,放置方案为j总共的方案数。 第0行的过程如下: 第1行的过程如下: 如此递推求出n行,种放置方案的总数,。因为只能放置k个棋子,所以在种放置方案中找出刚好是k个棋子的方案,也就是对应的状态j转化为二进制时,有k个1。 4.3 二进制包含1的个数 目标数n,通过n&(n-1)运算,包含多少个1就刚好进行多少次该运算,可以快速求出1的个数。 4.4 代码实现 计算数n中包含1的个数 intcountOne(intn){ inttotal=0; while(n>0){ total++; n&=n-1; } returntotal; } 变量定义及初始化 inti,n,k,line[8],f[2][256],num[256]; for(i=0;i<256;++i)num[i]=countOne(i); memset(f,0,2*256*4); f[0][0]=1; intj,c,now=0; //棋盘读入 for(i=0;i<n;++i){ intt=0; for(intj=0;j<n;++j){ t<<=1; cin>>ch; if(ch=='.')t+=1; } line[i]=t; } 核心递推 for(i=0;i<n;++i){ now=1-now; for(j=0;j<256;++j) if(num[j]<=k){ //第i行不放棋子 f[now][j]+=f[1-now][j]; //第i行放棋子 for(c=0;c<n;++c){ if((j&1<<c)==0&&(line[i]&1<<c)==0){ f[now][j|1<<c]+=f[1-now][j]; } } } } //枚举所有包含k个棋子的方案数 intans=0; for(i=0;i<256;++i){ if(num[i]==k){ ans+=f[now][i]; } } cout<<ans<<endl; 5.总结 递推最重要的思想,就是通过每一小步,找出与下一步之间的关系。关键在于思考问题的本质,对问题进行建模。常用f[i][j][k]等类似数组来记录,多一维就可以多记录一维状态信息,要思考上一步真正有多少个因素会影响当前步,那一般这些就是一定要记录的信息。 关注我,涨知识,微信公众号:几何思维 往期精彩回顾 蚂蚁走迷宫 老鼠与毒药 通过6人介绍可以认识世界上任何一个人?

优秀的个人博客,低调大师

构建高大上的黑盒监控平台

概述 在监控体系里面,通常我们把监控分为:白盒监控和黑盒监控: 黑盒监控:主要关注的现象,一般都是正在发生的东西,例如出现一个告警,业务接口不正常,那么这种监控就是站在用户的角度能看到的监控,重点在于能对正在发生的故障进行告警。 白盒监控:主要关注的是原因,也就是系统内部暴露的一些指标,例如redis的info中显示redis slave down,这个就是redis info显示的一个内部的指标,重点在于原因,可能是在黑盒监控中看到redis down,而查看内部信息的时候,显示redis port is refused connection。 白盒监控:有很多种,有中间件,有存储,有web服务器例如redis可以使用info暴露内部的指标信息;例如mysql可以使用show variables暴露内部指标信息;例如nginx可以使用nginx_status来暴露内部信息,系统业务指标可以通过埋点或者命令进行采集。 Blackbox Exporter 在前面的知识中,我们介绍Prometheus下如何进行白盒监控:我们监控主机的资源用量、容器的运行状态、数据库中间件的运行数据,通过采集相关指标来预测我们的服务健康状态。在黑盒监控方面。Blackbox Exporter是Prometheus社区提供的官方黑盒监控解决方案,其允许用户通过:HTTP、HTTPS、DNS、TCP以及ICMP的方式对网络进行探测。 Blackbox_exporter 应用场景 HTTP 测试定义 Request Header 信息判断 Http status / Http Respones Header / Http Body 内容 TCP 测试业务组件端口状态监听应用层协议定义与监听 ICMP 测试主机探活机制 POST 测试接口联通性 SSL 证书过期时间 结合grafana 生成的相关模板: 1、首先看下我们这边的相关图表,门户多项指标与ssl监控: 2、线路监控: 3、接口状态监控: Blackbox Exporter 部署: 1、安装Exporter: [root@cinder1 src]# wget https://github.com/prometheus/blackbox_exporter/releases/download/v0.16.0/blackbox_exporter-0.16.0.linux-amd64.tar.gz [root@cinder1 src]#tar -zxvf blackbox_exporter-0.16.0.linux-amd64.tar.gz -C /usr/local [root@cinder1 src]#mv /usr/local/blackbox_exporter-0.16.0.linux-amd64 /usr/local/blackbox_exporter 2、添加到启动项: [root@cinder1 src]# cat /etc/systemd/system/blackbox_exporter.service [Unit] Description=blackbox_exporter After=network.target [Service] WorkingDirectory=/usr/local/blackbox ExecStart=/usr/local/blackbox/blackbox_exporter \ --config.file=/usr/local/blackbox/blackbox.yml [Install] WantedBy=multi-user.target 3、检测是否正常启动: [root@cinder1 src]# ss -tunlp|grep 9115 tcp LISTEN 0 128 :::9115 :::* users:(("blackbox_export",pid=2517722,fd=3)) icmp监控 通过icmp 这个指标的采集,我们可以确认到对方的线路是否有问题。这个也是监控里面比较重要的一个环节。我们要了解全国各地到我们机房的线路有哪条有问题我们总结了两种方案:1、全国各地各节点ping 和访问数据采集。这种类似听云运营商有提供这类服务,但是要花钱。2、我现在用的方法就是:找各地测试ping 的节点,我们从机房主动ping 看是否到哪个线路有故障,下面我们开始。 一、prometheus 添加相关监控,Blackbox 使用默认配置启动即可: - job_name: "icmp_ping" metrics_path: /probe params: module: [icmp] # 使用icmp模块 file_sd_configs: - refresh_interval: 10s files: - "/home/prometheus/conf/ping_status*.yml" #具体的配置文件 relabel_configs: - source_labels: [__address__] regex: (.*)(:80)? target_label: __param_target replacement: ${1} - source_labels: [__param_target] target_label: instance - source_labels: [__param_target] regex: (.*) target_label: ping replacement: ${1} - source_labels: [] regex: .* target_label: __address__ replacement: 192.168.1.14:9115 二、相关ping节点配置: [root@cinder1 conf]# cat ping_status.yml - targets: ['220.181.38.150','14.215.177.39','180.101.49.12','14.215.177.39','180.101.49.11','14.215.177.38','14.215.177.38'] labels: group: '一线城市-电信网络监控' - targets: ['112.80.248.75','163.177.151.109','61.135.169.125','163.177.151.110','180.101.49.11','61.135.169.121','180.101.49.11'] labels: group: '一线城市-联通网络监控' - targets: ['183.232.231.172','36.152.44.95','182.61.200.6','36.152.44.96','220.181.38.149'] labels: group: '一线城市-移动网络监控' #这些数据是从全国各地ping 网站进行采集,大家可以从那些网站获取 三、添加grafana 这个grafana是自己定义的,看到网上没有就自己定义了一个。大家可以从github上下载,再看看效果: http 相关指标监控: 一、prometheus 配置http_get访问: - job_name: "blackbox" metrics_path: /probe params: module: [http_2xx] #使用http模块 file_sd_configs: - refresh_interval: 1m files: - "/home/prometheus/conf/blackbox*.yml" relabel_configs: - source_labels: [__address__] target_label: __param_target - source_labels: [__param_target] target_label: instance - target_label: __address__ replacement: 192.168.1.14:9115 二、相关配置文件,类似举例如下: [root@cinder1 conf]# cat /home/prometheus/conf/blackbox-dis.yml - targets: - https://www.zhibo8.cc - https://www.baidu.com #配置相关URL 三、添加grafana模板: 可以选择模板的9965模板,这个模板我们也看到前面的,提供了相关的ssl 过期检测。 接口get请求检测 一、prometheus 配置,其实跟我们之前的配置一样,我们直接看配置文件: - job_name: "check_get" metrics_path: /probe params: module: [http_2xx] # Look for a HTTP 200 response. file_sd_configs: - refresh_interval: 1m files: - "/home/prometheus/conf/service_get.yml" relabel_configs: - source_labels: [__address__] target_label: __param_target - source_labels: [__param_target] target_label: instance - target_label: __address__ replacement: 192.168.1.14:9115 二、相关接口配置参考: [root@cinder1 conf]# cat service_get.yml - targets: - http://10.10.1.123:10000/pmkb/atc_tcbi - http://10.10.1.123:10000/pmkb/get_ship_lock_count - http://10.10.1.123:10000/pmkb/get_terminal_count_by_city - http://10.10.1.123:10000/pmkb/get_terminal_monitor?industry=1 - http://10.10.1.123:10000/pmkb/get_terminal_comparison?industry=1 - http://10.10.1.123:10000/pmkb/get_terminal_city_count_industry?industry=1 - http://10.10.1.123:10000/pmkb/industry_stat?industry=1 - http://10.10.1.123:10000/pmkb/get_company_car_count?industry=1 - http://10.10.1.123:10000/pmkb/get_terminal_month_countbyi?industry=1 labels: group: 'service' 三、grafana 和前面一样自己订制的,可以从github上下载。 接口post 请求状态检测: 一、这里首先我们要改一下post 相关接口的blackbox.yml配置,我们自己定义一个模块: [root@cinder1 blackbox]# cat blackbox.yml modules: http_2xx: prober: http http_post_2xx: #这个模块名称可以自己定义 prober: http http: method: POST headers: Content-Type: application/json #添加头部 body: '{"username":"admin","password":"123456"}' #发送的相关数据,这里我们以登录接口为例 二、添加到prometheus: - job_name: "check_service" metrics_path: /probe params: module: [http_post_2xx] # 这里要对应配置文件里,定义的模块 file_sd_configs: - refresh_interval: 1m files: - "/home/prometheus/conf/service_post.yml" relabel_configs: - source_labels: [__address__] target_label: __param_target - source_labels: [__param_target] target_label: instance - target_label: __address__ replacement: 192.168.1.14:9115 三、相关配置: [root@cinder1 conf]# cat service_post.yml - targets: - http://10.2.4.103:5000/devops/api/v1.0/login labels: group: 'service' 四、添加grafana相关配置,这个也是自己定义的,可以从github上下载。 tcp端口状态检测: 个人理解的是这个跟telnet差不多都是检测端口是否在线 一、prometheus 配置: - job_name: 'port_status' metrics_path: /probe params: module: [tcp_connect] #使用tcp模块 static_configs: - targets: ['10.10.1.35:8068','10.10.1.35:8069'] #对应主机接口 labels: instance: 'port_status' group: 'tcp' relabel_configs: - source_labels: [__address__] target_label: __param_target - target_label: __address__ replacement: 192.168.1.14:9115 二、图表: 图表可以集成到前面的grafana 9965模板: 告警规则定义: 一、业务正常性:icmp、tcp、http、post 监测是否正常可以观察probe_success 这一指标probe_success == 0 ##联通性异常probe_success == 1 ##联通性正常告警也是判断这个指标是否等于0,如等于0 则触发异常报警 二、通过http模块我们可以获取证书的过期时间,可以根据过期时间添加相关告警 probe_ssl_earliest_cert_expiry :可以查询证书到期时间。 #经过单位转换我们可以得到一下,按天来计算:(probe_ssl_earliest_cert_expiry - time())/86400 三、所以我们结合上面的配置可以定制如下告警规则 [root@cinder1 rules]# cat blackbox.yml groups: - name: blackbox_network_stats rules: - alert: blackbox_network_stats expr: probe_success == 0 for: 1m labels: severity: critical annotations: summary: "接口/主机/端口 {{ $labels.instance }} 无法联通" description: "请尽快检测" ##ssl检测 [root@cinder1 rules]# cat ssl.yml groups: - name: check_ssl_status rules: - alert: "ssl证书过期警告" expr: (probe_ssl_earliest_cert_expiry - time())/86400 <30 for: 1h labels: severity: warn annotations: description: '域名{{$labels.instance}}的证书还有{{ printf "%.1f" $value }}天就过期了,请尽快更新证书' summary: "ssl证书过期警告" 四、重启完成之后我们可以登录web界面查看下: 五、我们发现有个接口已经存在问题,这个时候我们也收到了一条相应的微信告警: 总结: 黑盒监控相较于白盒监控最大的不同在于黑盒监控是以故障为导向当故障发生时,黑盒监控能快速发现故障,所以我们监控时候以粒度比较细的,如端口、接口、线路等进行监控。通过Prometheus Blackbox Exporter可以快速实现和定制我们很多相关策略,大家可以按照上述流程测试一下。

资源下载

更多资源
Mario

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长,特征是大鼻子、头戴帽子、身穿背带裤,还留着胡子。与他的双胞胎兄弟路易基一起,长年担任任天堂的招牌角色。

腾讯云软件源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题,腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构,目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring

Spring框架(Spring Framework)是由Rod Johnson于2002年提出的开源Java企业级应用框架,旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念,提供核心容器、应用上下文、数据访问集成等模块,支持整合Hibernate、Struts等第三方框架,其适用范围不仅限于服务器端开发,绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能,例如代码缩略图,Python的插件,代码段等。还可自定义键绑定,菜单和工具栏。Sublime Text 的主要功能包括:拼写检查,书签,完整的 Python API , Goto 功能,即时项目切换,多选择,多窗口等等。Sublime Text 是一个跨平台的编辑器,同时支持Windows、Linux、Mac OS X等操作系统。

用户登录
用户注册