image frame

张俊杰的博客

冒泡排序 与 插入排序

排序算法在面试和工作中其实使用的地方还是蛮多的，一个人在上海空闲时间巨大。这边整理一批常用的算法解法，做做笔记记录下来~

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。


思路

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

经过优化的冒泡算法

  1. 右边已经为有序，所以每次子循环会跳过 count-i
  2. 如果一次循环下来没有需要交换的元素，证明已经完成排序，所以直接break掉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func sortArray(nums []int) []int {
	count := len(nums)
	for i := 0; i < count; i++ {
		flag := false
		for j := 0 ; j < (count-i-1); j++ {
			if nums[j] > nums[j+1] {
				temp := nums[j]
				nums[j] = nums[j+1]
				nums[j+1] = temp
				flag = true
			}
		}
		if (!flag) {
			break
		}
	}
	return nums
}
是否稳定算法 平均时间复杂度 空间复杂度
是 o(n^2) o(1)

遍历法

这个方法是我自己取的，因为我没在排序算法中找打它的描述。但是它在我看来的确是最简单的排序方法。大概思路就2个循环，第一个循环控制数组元素的移动，第二个做比对，如果条件表达式不满足就交换个位置。其实一开始我认为这种排序方法就是冒泡的，但是冒泡的定义是 比较相邻的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
func sortArray(nums []int) []int {
	count := len(nums)
	for i := 0; i < count; i++ {
		for j := i ; j < count; j++ {
			if nums[j] > nums[i] {
				temp := nums[j]
				nums[j] = nums[i]
				nums[i] = temp
			}
		}
	}
	return nums
}
是否稳定算法 平均时间复杂度 空间复杂度
是 o(n^2) o(1)

插入排序

插入排序就是把一个数组分配成左右2部分，左边和右边。左边是排序好的右边是未排序的。
类似 4,5,6,3,2,1 字符串。我们分别为左右2边，4,5 | 6,3,2,1 排序时用右边的第一个数 6 和左边的数依次做对比，如果满足条件表达式就把 左边的数依次后移然后把6插入进去

技巧：其实算法本身的思路很好理解，关键点是如何用程序去实现。在这个算法中我们只要理解下面几个表达式基本上就理解了插入排序的精髓了

  • for i:=1; i<count ; i++ 数组为0开头，这边 赋值为1 主要目的是忽略第一位直接从第2位元素开始比较

  • heard := nums[i] 这边的heard变量是一个临时变量，因为在找到插入位后。左边的数组会依次后移，这样原先的比较位（右1 会被覆盖掉

  • j := i-1 是为了取到 4,5 | 6,3,2,1 左边最后一位的小标。即 i=2，j=2-1, j = 1,下标对应的值是5,然后 j– , 5 -> 4 ->end 依次去寻找插入位。

  • 为什么heard > nums[j] 一旦不满足就马上跳出循环，因为插入排序左边的数都是有序的，有一个不满足都表示缘分未到（不是当前排序位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func sortArray(nums []int) []int {
	count := len(nums)
	for i:=1; i<count ; i++ {
		heard := nums[i]
		j := i-1
		for ; j >= 0; j -- {
			if (heard > nums[j]) {
				nums[j+1] = nums[j]
			} else  {
				break
			}
		}
		nums[j+1] = heard
	}
	return nums
}
是否稳定算法 平均时间复杂度 空间复杂度
是 o(n^2) o(1)

图片来源：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

2019年终结

2019还有3天就结束了，理一理今年的经历。对照去年的flag复盘下，惨不忍睹 啪啪打脸。唯一好的是，养成了记笔记在博客的习惯。

阅读

今年一共读完了16本书，有√标识的是给我带来较大映象和收获的书籍。

###技术

语言
嗨翻C语言 √
深入理解C指针 √
GO 语言实战√
GO WEB编程√

协议
图解HTTP
图解TCP/IP

架构
大型网络技术架构 √

创业

创业36条军规
低风险创业 √
合伙人制度——有效激励而不失控制权是怎样实现的 √
增长黑客

理财

工作前5年，决定你一生的财富 √
小狗钱钱

管理

奈飞文化手册
非暴力沟通
见识√

技能

  • C语言语法特性堆,栈,指针（能读懂,能写demo
  • Go的语法特性 beego框架（能开发
  • Mysql的底层原理
  • HTTP,TCP/IP协议（稍微知识扎实了一点

经济

  • 买房
  • 装修
  • 结婚的钱勉强搞定了

出去玩

  • 上海水族馆
  • 上海迪士尼
  • 枸杞岛看了海上的日出
  • 东方明珠看了城市的日落

《低风险创业》

读书笔记

樊登读书这个APP我比较喜欢，也经常在通勤的路上使用。后面看见APP上再推这本书，加上深知打工出路两茫茫所以买来细品下

因为经历过创业团队，并且团队已经壮大。前半部分感觉樊老师总结的真的是颇有细节和条理

  • 低风险创业的基本逻辑

    主要阐述了创业前的准备，家庭和事业间作者的一些见解。带着愉快且有使命感的心情创业，比打工者吃饭的心情创业成功率会高很多

  • 创业找到好的问题开始

    茅舍顿开的一点是樊老师对用户痛点的概括即创业的根本是解决一个社会型问题这一章作者分享了一些他寻找痛点的方式方法（从抱怨中寻找解决点，找到足够大的蛋糕要干就干最肥的市场，在客户最痛的点上寻找赚钱的方法

  • 秘密是最好的抗风险武器

    这章有点迷，既要留一手又要告诉你这手后你也学不会。但是自己的感悟是产品要么不做，要么做到数一数二。试错期做个又大又全的产品试错成本太高，尽量做个最小化产品尝试市场。

  • 反脆弱结构设计

    那些杀不死你的总会让你变得更加强大，未雨绸缪做产品或者创业别过于依赖某一点。要多元化的分配资源配置自己的创业杠杆，保留选择权

  • 赋能生物态创业团队

    这章感同身受，能创业成功的团队肯定是目标一致充满干劲的生态管理团队。机械管理团队比较刻板化，能工厂化的交付产出但是确实创新精神（不求有功但求无过，混口饭吃等工作氛围会在机械管理团队尤为突出。

  • 最优客户发展方法

    口碑传播，这章感觉就是樊老师对《上瘾》一书的总结了。怎么病毒化的传播自己的产品

《见识-吴军》

读书笔记

吴军博士是一个把爱好做到学术的人，在没看这本书之前在喜马拉雅上听过他的硅谷来信。看了这本书过后更多的感觉是对硅谷来信的一些总结，如书名一样感觉开阔了见识并且有的地方产生了共鸣，但书中有部分观点不能完全认同可能是境界还没有到那样的高度吧。很喜欢，还会二刷吧

《创业36条军规》

读书笔记

出于对公司的创业文化很感兴趣，并且想了解创业到底会经历哪些过程，需要注意什么，哪些是推动创业成功比较重要的点。阅读了这本书，感觉对自身有帮助的主要是如下内容

1.创业是高风险没有回头路的生活方式
2.创业者除专业技能外还需要有大量的准备和心里承受能力目标感
3.创业内容的讲究
4.团队管理的注意事项

两数之和解题笔记

每日一刷，用PHP和GO分别实现了2种我能想到的和官方给出的最优解。

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题

PHP

穷举

思路 ： 2个循环遍历一一对应，简单暴力

1
2
3
4
5
6
7
8
9
10
11
12
function twoSum($nums, $target) {
    foreach ($nums as $k => $v) {
        foreach ($nums as $kk => $vv) {
            if ($v + $vv == $target) {
                if ($k != $kk) {
                    return [$k,$kk];
                }
            }
        }
    }
    return false;
}

时间复杂度 o(n^2),平均执行时间 1533.6ms 平均内存消耗15.96MB

使用array_search查找

思路：PHP提供了超多的数组函数，比其他语言方便了很多。

  1. 循环取数
  2. 求差
  3. array_search查找是否存在
1
2
3
4
5
6
7
8
9
10
11
12
function twoSum ($nums, $target) {
    foreach ($nums as $k => $v) {
          $temp = $target - $v;
          unset($nums[$k]);
          $kk = array_search($temp, $nums);
          if ($kk != false) {
              return [$k,$kk];
          }

    }
    return false;
}

时间复杂度 o(n),平均执行时间 116ms 平均内存消耗15.94MB

Hashmap

hash表其实就是键值对的形式，在php中可以用数组来实现

  1. 循环等量的 内容长度
  2. 生成一个 数值为键,下标为值的hashmap
  3. 在循环中查找hashmap是否有差值对应
  4. 有就返回，没有把当前值写入hashmap的key下标写入value

这样做虽然时间复杂度也是o(n),但是节省了array_search的函数开销，hashmap中查找的时间复杂度是o(1)

1
2
3
4
5
6
7
8
9
10
11
12
function twoSum ($nums, $target) {

    $diff = array();
    for ($i = 0; $i < count($nums); $i++) {
        $key = $diff[$target - $nums[$i]];
        if (!isset($key)) {
            $diff[$nums[$i]] = $i;
        } else {
            return [$key,$i];
        }
    }
}

时间复杂度 o(n),平均执行时间 18.4ms 平均内存消耗16.06MB

go

go 没有原生函数支持是否存在切片或者数组中，所以这边只试了2种解法

穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(nums []int, target int) []int {
  	for k,v := range nums{
		temp := target - v
		for kk,vv := range nums{
			if temp  == vv {
				if (k != kk){
					return []int{k,kk}
				}
			}
		}
	}
	return []int{}
}

时间复杂度 o(n^2),平均执行时间 36ms 平均内存消耗2.9MB

Hashmap

1
2
3
4
5
6
7
8
9
10
11
12
function twoSum ($nums, $target) {
    $diff = array();
    for ($i = 0; $i < count($nums); $i++) {
        $key = $diff[$target - $nums[$i]];
        if (!isset($key)) {
            $diff[$nums[$i]] = $i;
        } else {
            return [$key,$i];
        }
    }
}

时间复杂度 o(n),平均执行时间 4ms 平均内存消耗3.8MB

ps: 那个0ms应该是抽了就不算进去了

性能对比

算法 语言 平均执行时间 平均内存
穷举 PHP 1533.6ms 15.96MB
穷举 GO 36ms 2.9MB
Hashmap PHP 18.4ms 16.06MB
Hashmap GO 4ms 3.8MB
array_search PHP 116ms 15.94MB

回文数算法的实现 && PHP GO C 的性能对比

一直以来我都有一个疑问，大家说的编译型语言比脚本型语言效率高运行快是否属实。在书本知识上来理解，一种更接近底层，一种需要解释器进行转换感觉来说的确如此，周末闲不下来所以特地试试

目的

  1. 了解回文数，并写出回文数的几种解法
  2. 对比（PHP / GO / C）对单个回文数算法的执行数据

什么是回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

1
2
输入: 121
输出: true

示例 2:

1
2
3
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

1
2
3
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
  • 所有个位数都属于回文数

解题

因为主要从事PHP开发这边也想了3中用PHP进行解题的思路

PHP

一. 翻转字符串

1
2
3
function isPalindrome ($x) {
   return strrev($x) == $x ? true :  false;
}

翻转字符串

平均执行时间 30.4ms，平均内存消耗 14.88MB

二. 转换为字符串，截断字符串 对比前后

思路

  1. 统计字符串长度，除2得到中间那个数
  2. 除模2判断单双数
  3. 双数 -> 前部分|取(0,字符长度/2) 后部分|取（字符长度/2，字符长度/2）
  4. 单数 前后多取一位
  5. 对比
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function isPalindrome($x) {
        $len = strlen($x);
        $centre = floor($len / 2);
        if (($len % 2) == 0) {
            $before =  substr($x, 0, $centre);
            $after = substr($x, $centre, $centre);
            if ($before == strrev($after)) {
                return true;
            } else {
                return false;
            }
        } else {
            $position = $centre + 1;
            $before = substr($x, 0, $position - 1);
            $after = substr($x, $position, $len - 1);

            if ($before == strrev($after)) {
                return true;
            } else {
                return false;
            }
        }
    }

翻转字符串

平均执行时间 32.8ms，平均内存消耗 14.86MB

取模对比法

  1. 负数都是非回文数
  2. 取10模因此需要过滤掉他本身
  3. 个位数都是回文数需要过滤掉0
  4. x取模10得到个位数
  5. rev乘10加上尾数实现’反转’效果
  6. x除10 rev乘10判断中位数
  7. rev 除10去除单数时的中数

注： PHP 是弱类型语言会隐式转换为浮点数，在乘除取中位数时会有干扰，说以需要强制取整

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isPalindrome ($x) {

    if ($x < 0 || ($x % 10 == 0 && $x != 0)) {
        return false;
    }

    $rev = 0;
    while (floor($x) > $rev) {
        $rev = ($rev * 10) + ($x % 10);
        $x = floor($x) / 10;
    }


    return ( (floor($rev / 10) == floor($x)) || ($rev == floor($x))) ? true : false;

}

平均执行时间 42.4ms，平均内存消耗 14.86MB

GO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func isPalindrome(x int) bool {
	
	if (x < 0) || ((x%10) == 0 && x != 0) {
		return false
	}

	var rev int
	rev = 0

	for x > rev  {
		rev = (rev*10) + (x%10)
		x = x/10
	}

	 if (rev/10 == x) || (rev == x) {
	 	return  true
	 } else {
	 	return false
	 }
}

平均执行时间 16ms，平均内存消耗 5.2MB

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isPalindrome(int x){

    if( x<0 || (x%10 == 0 && x !=0)){
        return false;
    }

    int rev = 0;

    while (x > rev) {
        rev = rev*10 + x%10;
        x = x/10;
    }

    if ( (rev/10) == x || rev == x){
        return true;
    } else {
        return false;
    }
}

平均执行时间 14.4ms，平均内存消耗 7.12MB

性能比较

PHP

名称 平均耗时 平均内存消耗
翻转字符串 30.4ms 14.88MB
截断字符串,对比前后 32.8ms 14.86MB`
取模对比法 42.4ms 14.86MB

语言对比

语言 平均耗时 平均内存消耗
PHP 30.4ms 14.88MB
GO 16ms 5.2MB
C 14.4ms 7.12MB

总结

至此给我带来最大收获的可能会有如下几点

  1. GO的性能消耗无限接近C
  2. 脚本型语言性能弱于编译型
  3. PHP内部封装函数优于我们自己用PHP语言实现的各种花里胡哨的算法（1.开发小组或多或少会选择执行性能最好的解法。 2.底层C直接执行函数，效率远远高过脚本解释成二进制再去执行。)

这里浅浅的翻了下PHP strrev 函数的C实现是通过指针向前解引实现的（C的功力有限描述不出来了，2020年绝逼去深挖一波争取可以玩玩源码）

另外作为程序员我们该做到的不是去比较语言的性能，而是在适应的场景用适应的技术顺势而为。过分的执着语言本身的性能不能通盘考虑往往是单一语言的布道者，但不是一名合格的程序员和技术管理者。

《大型网站技术架构》

读书笔记

从极客时间上了解到了李智慧这个人，并且公司大佬提过一下这本书就买来读读了。

《大型网站技术架构》

理解

  1. 这本书把单体架构和分布式架构交代的明明白白
  2. 对于我个人来说算把我做现在这个项目的经历做了归纳总结，有形或无形中异曲同工
  3. 内审自己学过的分散知识，这算是一次点线成面的过程

同时，在我们内部系统中看见了很多人评价这本书入门级没用什么什么的。其实内心来说真的想鸣个不平，技术没有简单复杂的说法只有适用性和当前最优解（相对当前业务场景，公司形态）

邋遢的整理

粗略的整理了下这本书中讲到的知识点，结合自己浅薄的知识做出了一个整理。同样也是算当前阶段对自己的一个内审和总结吧类似《评估WEB网站架构的一些标准和处理方法》一样

张俊杰的博客-对架构的阶段性理解

资源

xmind下载

Supervisor 的使用和集群下的管理

项目中经常会有些需要常驻后台的服务，它的存活问题也成为了一个重点。在 php laravel 和 go 的 beego 中同时提到了 Supervisor。 项目中也刚好有使用（运维包干了），本着自己也会好沟通的原则进行了下面的尝试

Supervisor 是什么

Supervisor是一个客户端/服务器系统，允许其用户在类UNIX操作系统上控制多个进程。

我的理解就是它是一个可以提供web管理页面的守护进程工具

安装

CentOS

1
2
3
4
//安装
yum install supervisor
//生成配置文件
echo_supervisord_conf > /etc/supervisord.conf

安装成功后会有2个程序 supervisord 和 supervisorctl

supervisor d 负责监听进程
supervisor ctl 负责管理supervisord监听的进程,并且监听supervisord

测试运行

在 /etc/supervisord.conf 添加

1
2
[program:foo]
command=/bin/cat

如果只杀死主进程，子进程就可能变成孤儿进程。通过这两项配置来确保所有子进程都能正确停止

1
2
stopasgroup=true             ; send stop signal to the UNIX process group
killasgroup=true             ; SIGKILL the UNIX process group

运行

1
2
// -n 前台运行
supervisord -c /etc/supervisord.conf -n

测试图

可以看见我们Supervisor成功启动，并且拉起和监听了一个 PID 26540 的 cat进程

supervisorctl 使用

supervisorctl 需要使用 supervisord 一样的配置文件。在配置文件中我们可以添加一些分组信息来更好的区分和使用

1
2
3
[group:test]
programs=foo  ; each refers to 'x' in [program:x] definitions
priority=999                  ; the relative start priority (default 999)

下面我们运行 supervisorctl

1
supervisorctl -c /etc/supervisord.conf

会看见如下输出

可以看见我们 test 分组下的foo正常工作，并且进入交互模式。我们输入 help可以看见它支持的一些命令

1
2
3
4
default commands (type help <topic>):
=====================================
add    clear  fg        open  quit    remove  restart   start   stop  update
avail  exit   maintail  pid   reload  reread  shutdown  status  tail  version

在退出交互模式的情况下 正常 supervisorctl + commands 可当作shell使用，比如这个场景

我们发布Nginx反向代理下的go代码

  1. git push 到远程仓库
  2. rdc打包同步到服务器
  3. 服务器上使用 supervisorctl restart name 来重启这个进程完成代码的部署发布

安装web管理界面（集群管理）

这里我们使用官方推荐的 PHP monitor

  1. 创建目录下载项目源码
1
2
make monitor
git clone git@github.com:mlazarov/supervisord-monitor.git

2.修改 supervisord.conf http serve配置

1
2
3
4
[inet_http_server]         ; inet (TCP) server disabled by default
port=*:5555        ; (ip_address:port specifier, *:port for all iface)
username=zjj              ; (default is no username (open server))
password=zjj               ; (default is no password (open server))
  1. 修改PHP配置文件
1
2
3
4
cd ~/monitor/supervisord-monitor/application/config

cp supervisor.php.example supervisor.php

1
2
3
4
5
6
7
8
$config['supervisor_servers'] = array(
        '测试' => array(
                'url' => 'http://116.196.88.52:5555/RPC2',
                'port' => '5555',
                'username' => 'zjj',
                'password' => 'zjj'
        ),
);
  1. 配置Nginx vost
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
server {

         listen 5566;

         index index.html index.htm index.php;
         root  /opt/www/monitor/supervisord-monitor/public_html;

         location / {
                 try_files $uri $uri/
                 /index.php$is_args$query_string;
         }

         location /nginx_status
         {
            stub_status on;
            access_log   off;
         }

         location ~ .*\.(gif|jpg|jpeg|png|bmp|swf)$
         {
             expires      30d;
         }

         location ~ .*\.(js|css)?$
         {
             expires      12h;
         }


          location ~ \.php(.*)$ {
               fastcgi_pass   127.0.0.1:9000;
               fastcgi_index  index.php;
               fastcgi_split_path_info  ^((?U).+\.php)(/?.+)$;
               fastcgi_param  SCRIPT_FILENAME  $document_root$fastcgi_script_name;
               fastcgi_param  PATH_INFO  $fastcgi_path_info;
               fastcgi_param  PATH_TRANSLATED  $document_root$fastcgi_path_info;
               include        fastcgi_params;
          }
}
  1. 重启 supervisord 和 Nginx 让配置生效

ps:

  1. 集群管理才需要用到 monitor，非集群可以打开自带的 inet_http_server 模块功能够用
  2. monitor 没有权限验证可以再 Nginx 上加上 401保证安全

产考文档

https://www.rddoc.com/doc/Supervisor/3.3.1/zh/
http://supervisord.org/running.html

评估WEB网站架构的一些标准和处理方法

我司现有类比项目组代码是否优秀的指标有2个，一是听云中的响应时间，一是框架中的执行时间。一直感觉有所缺失，而且太过于看重面板数据少了一些说不出来的东西（犹如中国教育制度，只看答卷成绩。

衡量一个B/S应用是否优秀的方法有很多，除了简单的面板数据外应当具备以下7点

  • 性能
  • 伸缩性
  • 简单性
  • 可见性
  • 移植性
  • 可靠性/高可用
  • 可修改性

这7种特性会结合项目现状，公司形态，市场等众多情况有所平衡，如一张雷达图。

按照上面7点结合自己浅薄的工作经验，整理出了一张图。希望一年过后看见这张图的时候有更多新的认识

B/S架构标准

资源

下载xmind

请我喝杯咖啡吧~