0%

人生只有贪心,没有动态规划。

数据结构

  • 数组
  • 栈,先进后出
  • 队列,先进先出
    • 双端队列,双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两边进行。
    • 环形队列,环形队列是一种特殊的队列结构,保证了元素也是先进先出的,但与一般队列的区别是,他们是环形的,即队列头部的上个元素是队列尾部,通常是容纳元素数固定的一个闭环。
  • 堆,一种特别的树状数据结构。堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
  • 链表
    • 单向链表。
    • 双向链表。
    • 跳表,一种带多级索引的链表。
  • 散列表,是根据键而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。
    • 二叉树,二叉树是一个连通的无环图,并且每一个顶点的度不大于3。
    • 红黑树,是一种自平衡二叉查找树。
    • 字典树(Trie)
  • 图,图(Graph)是由顶点的有穷非空集合和顶点之间的边的集合组成。
  • 布隆过滤器,一个概率型数据结构,可以用来判断一个元素是否在一个集合中。判断某个元素在,可能会被误判;判断某个元素不在,那么一定不在。

算法思想

分治法

分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

例子:快排、归并排序、MapReduce

贪心算法

贪心算法就是在每一步的选择中都按照当前最优的选择,从而希望最终结果得到最优解。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

例子:最小生成树、哈夫曼编码

动态规划(Dynamic Programming)

动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。
若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

递归+记忆=递推

适用情况:

  1. 具有最优子结构性质。
  2. 无后效性,子问题确定后不会再改变。
  3. 子问题重叠的性质。

例子:背包问题
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
https://www.zhihu.com/question/23995189/answer/613096905

回溯法(backtracking)

回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  1. 找到一个可能存在的正确的答案
  2. 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。

例子:八皇后问题

https://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://www.cnblogs.com/zuzZ/p/8178950.html

分支界限法

与贪婪算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。

概率算法

例子:
数值随机化算法
蒙特卡罗(Monte Carlo)算法
拉斯维加斯(Las Vegas)算法
舍伍德(Sherwood)算法

https://zhuanlan.zhihu.com/p/42619498

发现自己没玩过的事情好多,上周末便实施了一次露营⛺️之路,叫上小伙伴一起报了个户外团,第一次去选择的比较休闲级别的,然后自带了几十斤装备在山上扎营看天。

去之前连帐篷都没有打开过,不过好在很好弄,去到了迅速选择好营地很快就扎好了。然后在山顶四处转了转。第一次出来玩还是挺兴奋的,但没多久就冻得回帐篷换上了衣服,对比去的时候早上北京的天气超级闷热。

周围也有好多同行的人在扎营,还有两只🐶子互相溜着玩,和它们的主人一样的兴奋。

到了傍晚,就开始下起了大雾,一直持续到了第二天早上,后来想想从山脚下看来这应该是☁️吧,那就是身在云中了。在这么个野外环境下,找厕所也是很方了,哈哈哈。

下了这么一晚上的雾,有点遗憾的是没能看到星空🌃,而且没能选到一个防露水的帐篷晚上被滴醒好几次😶。。。

早上还是挺可以的,看到了日出🌅和云海,还有四处觅食的🐂。其实云海肉眼看上去不太明显,但是做成一个加速的短视频就很好看了。

露营前简单做的攻略

说明:

  1. 加粗为必备
  2. 标 A 的说明已准备好

装备:

帐篷A防潮垫A睡袋A、气垫(防咯)、头灯A、手电A、登山包A充电宝A、手机

雨衣A、雨鞋套A、登山鞋或运动鞋长袖防风衣物、羽绒服、头巾、棉帽

暖贴A、水杯、水5L A湿巾A纸巾A、洗漱用品、垃圾袋A、耳塞(风声吵)、眼罩

自发热小火锅A、八宝粥、面包、筷子、红牛、便携气炉

药物(快客、思密达+ 、藿香正气、创可贴、防虫喷雾、布洛芬)、风油精 AAAAA

银行卡一张A、工具刀A、备用手机A

这里说一些注意点

  1. 帐篷一定要四季防雨防露水的,赶上下雨就惨了
  2. 防潮垫一定要有,并且根据情况准备厚点的防咯
  3. 暖贴可以准备一些晚上睡觉冷贴身上
  4. 垃圾袋还是多带点将垃圾带走
  5. 工具刀准备一下防止意外保护安全
  6. 如果带气炉的话要注意地铁不让进
  7. 吃的尽量带一些高热量食物,自发热小火锅我觉得必备

最后附上一张小朋友拍的很棒的照片。

在这几年的微服务开发过程中遇到过两次因为网络问题导致的系统故障,并且没有做好降级策略,导致系统的不可用时间增加,所以今天专门整理一篇关于网络故障的问题分析处理以及开发中需要注意的地方。

基础部分

TCP 连接,先抛大图:

a

主要分为三部分:

  1. 建立连接
  2. 传输数据
  3. 关闭连接

原理不做过多介绍,主要说说常见的异常和模拟方式。

常见的异常类型

b
上面的异常是一些常见的功能性异常,其它性能方面的异常不在本文讨论范围。

实施手段

需要的工具

  • python 脚本
  • iptables,对网络流量进行规则过滤
  • tcpkill,用来断开网络构造异常
  • curl,发起 http 访问请求

Python脚本

主要作用是启动一个TCP监听,然后将接收到的数据在转发回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#! /usr/bin/python
# -*- coding:utf-8 -*-
import socket
import sys
def start_tcp_server(ip, port):
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server_address = (ip, port)
print('Starting listen on ip %s, port %s' % server_address)
sock.bind(server_address)
try:
sock.listen(1)
except socket.error as exc:
print('Fail to listen on port %s' % exc)
return
while True:
print("Waiting for connection")
client, addr = sock.accept()
data = client.recv(1000)
client.send(data)
client.close()
print(data)
if __name__ == '__main__':
start_tcp_server('0.0.0.0', 12345)

iptables 基本使用

1
2
3
4
5
// 查看当前生效规则
iptables -L -n
// 清空所有规则
iptables --flush
iptables -F

tcpkill 基本使用

https://yq.aliyun.com/articles/59308

1
2
3
4
// 安装
sudo apt-get install dsniff
// 使用
...

curl 超时设置

使用 curl 有两个超时时间,一个是连接超时时间,另一个是数据传输的最大允许时间。
连接超时时间用 --connect-timeout 参数来指定,数据传输的最大允许时间用 -m 参数来指定。

1
curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"

实施过程

  1. A机器启动Python脚本,监听12345端口。
  2. B级器通过curl命令进行访问。
  3. 在访问过程中通过配置iptables来实现网络的各种异常情况。
  4. 通过 tcpkill 来实现连接中断的异常情况。

正常访问

1
2
3
4
5
xyz@xyz-pc:~$ curl "http://192.168.1.110:12345"
GET / HTTP/1.1
Host: 192.168.1.110:12345
User-Agent: curl/7.58.0
Accept: */*

查看和清除规则

1
2
3
4
5
6
7
8
9
10
11
12
13
xyz@xyz-pc:~$ sudo iptables -L -n
[sudo] xyz 的密码:
Chain INPUT (policy ACCEPT)
target prot opt source destination

Chain FORWARD (policy ACCEPT)
target prot opt source destination

Chain OUTPUT (policy ACCEPT)
target prot opt source destination
DROP tcp -- 0.0.0.0/0 0.0.0.0/0 tcp dpt:12345 flags:0x17/0x02

xyz@xyz-pc:~$ sudo iptables -F

连接超时

1
2
3
xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp --syn --dport 12345 -j DROP
xyz@xyz-pc:~$ curl --connect-timeout 10 "http://192.168.1.110:12345"
curl: (28) Connection timed out after 10001 milliseconds

读取数据超时

1
2
3
xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp -m state --state ESTABLISHED --dport 12345 -j DROP
xyz@xyz-pc:~$ curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"
curl: (28) Operation timed out after 20001 milliseconds with 0 bytes received

拒绝连接

1
2
3
xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp --dport 12345 -j REJECT
xyz@xyz-pc:~$ curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"
curl: (7) Failed to connect to 192.168.1.110 port 12345: 拒绝连接

连接被重置

这里需要将Python脚本的 client.close() 注释掉。

1
2
3
4
5
6
7
xyz@xyz-pc:~$ sudo tcpkill -iwlp8s0 port 12345
xyz@xyz-pc:~$ curl --connect-timeout 10 "http://192.168.1.110:12345"
GET / HTTP/1.1
Host: 192.168.1.110:12345
User-Agent: curl/7.58.0
Accept: */*
curl: (56) Recv failure: 连接被对方重设

总结

在越来越多的企业微服务化进程中,肯定会遇到网络请求的各种问题,当我们在做一个基础组件或者进行网络通信请求时需要考虑到这些异常情况,最好还是将各种常见的情况模拟实施一下,来保证服务的稳定性。首先要说的是请求的超时设置,不论是在进行 HTTP 访问还是封装后的 RPC 请求,超时设置是最基本的。
基于不同语言的不同组件实现质量来说。曾经遇到过一个问题是,一个服务处于假死状态,Java 的客户端中默认超时和多线程可以使主线程服务不会受到过多影响,golang 中的客户端默认设置了一个很长的超时时间,服务在一定程度上受到了影响,而Python的客户端超时时间也是很长,还有就是Python只有一个主线程再跑,所以此时服务会被 hang 住了。
所以这里还有一个问题就是服务降级,当前服务如果出现问题,重试几次后仍然失败,那么是否降级来保证当前服务的可用性,其实考虑的是异常服务对于当下的重要性,是否在整个核心服务链路当中,否则的话进行降级处理。
还有一个关键点是慎用重试,偶然的网络波动导致的异常在重试下会很有效,但是当遇到服务性能导致的超时问题时,就遇到大量的客户端重试导致请求翻倍,很可能会直接把服务打挂,所以不要轻易使用重试,可以通过一些额外的补偿机制来提高服务稳定性。

未防止爬虫盗爬我的文章,在末尾打个广告。这篇文章首发在我的个人博客 知一的指纹 http://noogel.xyz ,有需要技术交流的朋友可以加我个人微信:zhi2012666

参考

https://blog.csdn.net/llianlianpay/article/details/79768890
https://www.cnblogs.com/gl1573/p/10129382.html
https://blog.csdn.net/wangyiyungw/article/details/85004905

从北京出发一路向北有个坝上草原,趁着七月天热的时候去避避暑,看惯了城市的生活,周末偶尔出去放松一下也是好的。便约了几个同事一起自驾过去玩的。

去的前一天预报说下雨☔️,结果当天也只是一路阴天☁️,等到了坝上草原也没有下,恰巧那天晚上北京下的,完美避过。下面这张是在去的时候怀柔拍的,这边的山⛰相对高耸一点,夏天还有点绿色,冬天就真的是凸凸的。

等到了坝上草原这边,真的是天高云阔空气清新。而且也有点冷🥶,哈哈哈也就二十度左右,所以带件外套真的是很有必要的。

在丰宁,一路上都是这样子的。

整个旅途并没有排的很紧凑,而是自驾的舒适随意。导航到了一个草原的入口,然后爬上山坡一路向草原深处走去。顺着一条小路走过一个又一个山丘,草原的广阔无垠尽收眼底。同时,七月的日子里草原也是超级冷的,小风飕飕的,所以准备穿着冲锋衣来是最明智的选择了。

在草原,远远望去会看到一个个的村庄,彼此离得很远感觉出村的路就那么一条,不过生活在这样的地方应该会很惬意。

要说印象最深的还是说草原的夕阳🌇了吧,在城市里因为高楼的遮挡可能早早的就见不到太阳了。而草原的夕阳可以在很晚,直到太阳落到地平线以下。拍下面这张图的时间是在傍晚 7 点半。草原的能见度真的很高,远处的山⛰感觉要几十公里外了。

来这样的环境下偶尔放松放松,心情真的也会很好了。还有一张像极了 Windows 经典的桌面背景,蓝天白云绿草地。

下面👇是去之前简单做的攻略:

要带的东西:

防晒霜、太阳镜、帽子、雨伞

防蚊虫叮咬的、创可贴、风油精、快客

野餐垫、食物、水果、红牛

身份证!!!!!

手机、充电宝、

纸质现金

昼夜温差大(28 - 15度)带一件春秋外套

穿户外登山、运动鞋!!!

摄影装备(选填)

玩点:

看日出

柳树沟(50元)

情人谷(免费)

草原娱乐场(滑草??、射箭、CS、骑马)

烤串

草原天路

路线图:
(需要的可以找我要~)

首先要说的是重构最基本的定义:重构是在不敢编软件可观察行为的前提下改善其内部结构。

每一个开发人员肯定都经历过『坏代码』的味道。在一个古老又庞大的项目中,这里面一些函数的作用和逻辑变的很难理解,没有人了解这里的所有 case,加上没有足够的注释,之前开发的人员离职等诸多因素,可维护性非常低,谁都不愿意碰,这时候再改动一个需求,会很容易引入一些 bug。当你遇到上面的这些情况时那么时候要把这摊『臭水坑』清理一番了。

我们知道要做重构这件事了,那么『工欲善其事必先利其器』,重构也是有诸多手段的,有许多被前人验证过的重构手法来帮助我们改善项目代码的健康状况。接下来讲讲一些小的也是简单实现的重构方式。

flight over Barcelona ...

小重构

重复的代码

重复代码的抽象有几种方式,一种是将重复的代码或者相似的代码,可以提取到一个扩展函数中,然后在多个地方调用;或者将多个相似类中的相同代码抽象到父类中,子类调用,但是按照组合优于继承的设计方式,不建议这样做;再有是对相似流程代码抽象出模板方法,子类实现差异化逻辑。

过长的函数

在计算机领域有这样一句名言:『计算机科学相信所有问题都可以通过添加一个间接层来解决』。如果我们没有良好的系统设计经验和深刻理解面向对象思想(业务系统主流的编程思想),就很容按照过程式的思想去写代码,就会出现职责庞大的函数或类,有着超多的分支判断逻辑,各种补丁代码块。这里一部分是系统设计的问题,另一方面没有很好的拆分职责。一个很好的办法就是将分支中的代码块抽离成小函数,把大类拆分成职责较为单一的小类。再有让小函数容易理解的关键是一个好名字(关于起名字这块可以单独说说);再有大函数中的临时变量可能阻碍你的拆分,可以把这些临时变量通过查询的方式获取,既提高了可读性又能共享给其它地方用。

过大的类

过大的类就像过长的函数,冗杂且难以理解。我们通俗的说这个类的职责太重了,导致里面又很多的实例变量。改造的办法是将多个实例变量分组,然后拆分不同的类去处理,这样来拆分出一些单一职责类。再有就是可以确定类的使用方式,提炼出来接口帮助理解这个类。

过长的参数列表

过长的参数列表可能是这样产生,最初定义接口只有两个参数,那么随着业务扩展,这个函数产生的职责越来越大,随之参数越加越多。这种的解决方案是搞一个参数对象,将原先的参数都保存到参数对象实例中,然后传递这个实例到函数中处理。

Pelee

然后呢

我把这写最基本的风险小的方式叫做小重构,可以让我们的代码变得稍微好一些。其实你在做小重构的过程中可以慢慢形成对于这个系统业务流程的理解,以及对于系统设计(大)重构方向上的思路。那么什么时候或者什么时机就要开始重构?

如果让我接需求改系统一个部分的代码,做完如果再次需求改动不是很容易改的时候,基于事不过三的原则,我会在需求中做一些重构来弥补设计上的缺陷;再有就是修复 bug 的时候,如果不是很好修复,我也是要先进行适当的重构的再去解决的;或者我们集中进行 codereview 的时候提出来需要进行的重构时。

一个好的项目是需要有一个好的设计基础,因为我们不能只想着今天做什么,还要想明天可能会做什么,只做好今天,而明天到来发现无法做到,那么也是失败的,想的多了就会出现过度设计,也是包袱。所以写好代码是一件挺难的事情,写之前多思考一下。今天先写这么多~