字节跳动和 Go 语言

字节跳动

2022年1月5日,我正式入职字节跳动,高级测试工程师,负责一个字节非常底层的网络库的质量保障工作。这次找工作没有选择开发岗位的一个原因是,开发工程师对于整个工程的控制力是比较弱的,一般来说基本相当于一个纯「产出单元」,没有宏观调度的能力与意愿。我想要做更多宏观的工作、加强自己对于工程的把握感,就只有QA、项目经理、产品经理这几个岗位,后两个岗位对我吸引力很低,QA 则刚好和我的个人履历与兴趣相结合。

绝大部分大厂对于 QA 的运用,基本上还是作为测试部门,以调研各种测试流程和技术为主,为「产出单元」们提供后勤保障工作。换言之,说是 QA,其实就是测试+一些 bug 数据统计+打包发版。

当然,并不是说,QA 应该彻底脱离测试、成为一个飘浮在半空中的岗位。但如果 QA 部门自己都不能深刻的理解「何为质量」这个命题,如何能带领整个团队进入下一个质量高潮呢?

以手工回归测试来说,这项工作用来了解产品特性还凑合,但了解产品最好的方式不是使用产品,而是开发产品——买的永远没有卖的精明。但业内的 QA 或测试工程师对产品源码一般来说没什么兴趣,精力都放在测试流程和技术上。国内高强度的工作方式,的确会抑制工程师们的想象力。

在和开发工程师的一次午餐中,我向大家阐述了自己的职业目标,以及我对「质量」二字的理解:

我个人永恒的职业目标,就是把自己当下的岗位「干没」。「干没」,意味着永久性的、终极的解决了这个岗位面临的一切问题——如果我是一个开发,那么我的目标就是减少掉自己这个开发;如果我是测试,就要让团队不再需要测试;如果我是 QA,就要让开发过程不再需要 QA 的校准;如果我是团队 leader,就要让团队不需要我这个 leader 也同样能高效运转。

这是非常终极的目标,有可能永远不可能达到,但应该有这样的追求。作为工匠,不必担心自己未来会失业,如果一个职场人能达到以上高度,那么一定有更重要的岗位等着你。

我对质量的理解,则是——「质量」不应该成为一个岗位,而是一种思想、一种意识形态。因为质量诞生于开发部门,而 QA 永远只能「揭示」质量、而非产出质量。既然「质量」是开发工程师的产出,那么应该让开发工程师来负责质量,才是最正确的事情。就像打铁铸剑,一个产品在诞生之时,其品质已经确定,后期再修补也无济于事。

在传统的「开发-测试-发版」流程中,如果测试发现质量有问题,就应该将之返回给开发团队,由开发团队去内部处理一切有关「质量」的问题。试想一下,这个世界上存在与质量相关、却不应该由开发亲自处理的事情吗?

换言之,「质量」是一个开发问题,而不是测试或 QA 问题。

那么 QA 这个岗位,还有存在的意义吗?

QA 仅存的意义,我认为是一个类似战锤40K中的「牧师」角色。

这就是战锤40K中的牧师,勇武更超普通星际战士

在战锤40K的作战小队中,队长负责战术指挥,牧师负责思想和信仰工作。当士气低落、信仰垂危时,牧师要首当其冲的站出来,挽狂澜于既倒,扶大厦于将倾,即便为了一线胜利而牺牲自己,也在所不惜。

这个牧师不是躲在堡垒中对战士们指指点点的文官,他本身就是一个和兄弟们冲锋在前的顶尖士兵。只是相比于其他人,他的信仰更坚定更执着,也更有大局观、更优秀。

战锤40K 的牧师,实际上就类似项目组中的 QA 角色,这样的 QA 拥有如下特点:

  1. 战斗于一线,而非文官(本身就是开发,而不是开发团队之外的「指导者」)
  2. 更具宏观思维,能超脱于实际战斗以外(视野超出普通开发,更关注整个团队的产出质量)
  3. 来自于团队内部,而非外部(从开发中遴选一个开发人员成为QA,而非在团队外部设置QA岗位)

在这几个原则的规范下,我们很容易确定团队中谁来成为 QA,同时将团队外部的 QA 岗位直接取消。

目前微软已经取消了测试和 QA 岗位,全部测试工作都由开发工程师来做。这种意义上,字节还相当于普通星界军、而微软已经人均星际战士了。

Go语言

早在几年前,我就开始关注 Go 语言,只是耽于舒适区,一直没有向前一步。最近做了下调研,发现除了 Shopee 之外,字节也大量使用 Go 作为后端开发语言;另外作为区块链开发的重要技术栈,Go 语言未来也可能越来越重要。

所以从本周开始,我利用工作和业余的一些零散时间,开始逐渐学习 Go 语法,了解生态现状。

和我最熟悉(应该是唯一熟悉)的语言 Python 相比,Go 的生态要小很多,但是他们的特点都非常显著:Python 生态强大,几乎可以做一切事情,代码编写灵活;Go 的目标就是一个轻量版 C 语言,在「灵活快捷」和「高性能」之间尽量寻找平衡点。

中国互联网企业,实在是没什么技术含量,如果硬说,那就剩下一个「高并发」独步全球。在解决这种并发问题上,Go 有天然优势,goroutine 的内存占用非常小,同时通过 Channel 进行安全的数据处理,避免了 Python 那种一团乱麻式的异步和锁。所以新兴互联网企业喜欢用 Go 来构造后端,是非常理性的。

Python 是当之无愧的王者,但其中势必包含大量的非专业工程师 Python 开发者(例如科学家,量化交易员,等等)

区块链同样面临性能问题,传统比特币、以太坊性能都令人无法接受,所有新型公链一定会号称解决了性能问题。毕竟,以「代币」为核心机制的新型互联网,如果不能解决性能问题,则毫无未来。Go 语言在这个领域可能是最优选择。未来如果有机会进入这个行业,Go 肯定是必修课。

Go 位列13名,已经是非常好的成绩,仅次于 SQL/Swift/PHP/R。

以目前的发展趋势来看,Go 断然不会成为 Python 这样的全能语言,但其后端领域的影响力很可能会在未来几年达到甚至超过 Python。所以对于有 Python 基础的人来说,应该尽快学会 Go 并掌握开发技巧,不仅会带来收入上的提升,还能更好的了解到技术界的新趋势。

所以,这篇文章也算是一个节点,看看我下一次更新博客的时候,能用 Go 写出什么样的东西来了。

祝我的读者们新年快乐,虎虎生威(下面弄两个小老虎凑合凑合吧)!

虎虎生威,新年快乐!

Tagged : / / / / /

树莓派3初体验之一:搭建 Python 开发环境

最近新买了一个树莓派3(购买前还考虑了 Orange Pi 等 Linux 开发板,但最终仍然选择了树莓派),主要目标是想通过折腾这个信用卡大小的 Linux 电脑,学习一下 Linux 系统知识,熟悉服务器的各项操作,顺便给自己搭建个 Web Server。
WechatIMG17
安装步骤很顺利,通过官网下载了 NOOBS 版的 Raspbian 系统,并复制到 TF 卡中,然后启动树莓派,一路 Next,很快就可以看到图形界面。然后看了一下树莓派内置的 Python 版本,发现是 2.7.9 以及 3.4.2,于是机智的我马上制定了第一个任务——把树莓派的系统自带 Python 3.4 升级到最新的 Python 3.6.2。
升级的过程是这样的:
1. 从 Python 官网下载 Python 3.6.2 的压缩包。
wget https://www.python.org/ftp/python/3.6.2/Python-3.6.2.tgz
2. 解压编译
cd ./Python-3.6.2
./configure
make
sudo make install

3. 将 /usr/bin/python 的原文件删除,然后link到刚编译好的Python3命令上
rm /usr/bin/python
ln -s /usr/bin/python ~/Python-3.6.2/python

结果是虽然我把原本是2.7.9版本的python命令变成了3.6.2,但是配套的pip等工具却乱套了,一运行就会报语法错误,看来这样生变过去是不行的,于是想恢复回去,几经尝试后失败,遂格式化TF卡,重装系统。
第二次我不再 link /usr/bin/python, 而是机智的换成了/usr/bin/python3,但是依然出错,具体什么错误已经不记得了。再次格盘重装。
第三次终于成功,在命令行输入python3指向了/usr/local/bin/python3,我还没搞明白是怎么弄得,反正搞定了,明天去问问同事在哪里设置……

后来才想起来,要改环境变量里面的$PATH……这是刚学 Python 时候就遇到的问题,现在居然都想不起来了……

WechatIMG16
此时又遇到了第二个坑——Rsapbian没有安装若干必要的库,需要手动安装。
顺利配置好 Python3.6 后,我试着pip3 install requests,结果出现ssl module in Python is not available的报错,几经搜寻,发现是由于 OpenSSL 等库没有预置在 Raspbian 中,而 pip 则需要访问 https 加密的地址,故而报错。
首先,apt-get 安装这些库:
sudo apt-get install libreadline-gplv2-dev libncursesw5-dev libssl-dev libsqlite3-dev tk-dev libgdbm-dev libc6-dev libbz2-dev
然后重新编译一次 Python 即可解决问题:
cd ~/Python-3.6.2
./configure
make
sudo make install

于是经过不知多少次编译,我终于装好了 Python3.6。后来又安装了 PyCharm,但实际运行中感觉延迟严重,所以这样大型的 IDE 可能无法在树莓派上顺畅运行,如果需要写代码,可以考虑轻量级编辑器(同时还有一个问题没有解决,就是如何卸载 PyCharm ……)。
最后说一下树莓派的整体感觉。
开箱之后的树莓派需要自己安装散热片、风扇、外壳,当然这些配件都需要另外购买。组装过程很简单,把散热片粘到处理器上,然后一层一层安装外壳,最后在外壳上方固定和连接风扇。如果有过装机经验,那么整个过程即为简单。组装完成后,我通过一根 HDMI 转 VGA 线,将树莓派连接至一个古董19寸显示器。
我(也是大多数树莓派素人)选择的是官方推荐的 Raspbian 系统,是 Debian 的树莓派分支。其实树莓派有大量的系统版本可以选择,例如 CentOS 的 ARM 版、Ubuntu Mate等等,可按需选择。Raspbian 的 GUI 没有 Ubuntu 那么炫酷,但是能在这么小的板子上运行如此完整而流畅的桌面版 Linux,也让人很欣喜。
目前我已经把若干连接线(视频线、鼠标、键盘)从树莓派上移除,仅剩供电线路并连上 WiFi,通过 Mac 远程登录进行管理。本来想设置一下 DNS 实现通过 hostname 直接访问主机,结果家里没有多余的机器做 DNS Server,华硕路由器的官方系统又不原生支持 DNS、我还懒得再折腾路由器,所以只是通过改本地的 hosts 来实现 hostsname 登录(我给树莓派起的名字叫做 footboy)。以后可能会在树莓派上搭建几个服务,通过 supervisor 管理;或者做几个 Cronjob 的定时任务。
WechatIMG15

Tagged : / / / /

工作三周的碎语

工作满三周,我的第一个任务也交付测试中,如无意外很快就能上线了。三周来,学了很多知识,也逐渐适应了和工程师们一起工作的气氛。刚开始的时候,我一个人憋着不好意思问同事,结果浪费了好几天时间,后来才知道其实工程师之间每天问问题是常态。后来逐渐和大家熟络起来,也就轻松很多了。我项目做得速度挺慢,但是好在同事们都很乐意帮我答疑解惑,倒也不会遇到死胡同。
同事里,有几个南方科技大学的金融、金融数学出身的实习生,水平很不错,读英文文献,写量化策略,甚至还写的一手好 Java/Python,让人刮目相看。南科大这所新学校的教学质量真让人佩服,准毕业生们的素质比当年的我强多了。
三周工作中,每天早晚通勤各一小时,没时间打游戏,也没时间写博客,在任务交付前期压力巨大,总觉得自己拖了团队的后腿。我估计这种感觉随着技术的进步会逐渐消退,但是紧迫感恐怕是所有工程师永远无法摆脱的心头巨石。
所以这周末我不加班了(前两个周末都在加班),好好的打开 steam 玩几盘游戏,看两部电影,陪老婆出去散散步。此时此刻,经常动辄一整年不工作的我才觉得,在打仗般的工程开发以外,温柔日常生活真的是最让人放松和热爱的。
Python 是个好东西,愈发觉得无论毕业于什么专业、目前做什么工作,都要好好学一学编程,编程会给自己提供极大的选择余地,有太多工作可以用代码来完成。今天代码在日程生活中的应用依然太少,如果做到每个人都能拿起编程这个武器来武装自己,那世界或许能美好很多。

Tagged : / /

我的求职经历

2015年下半年,我在一家外贸软件企业任运营总监,某天无意间看了一眼当时公司产品的前端代码,竟在已发布的产品中发现各种注释,而且注释都是51cto之类网站的教学文章链接。那时候想,如果让我来做的话,应该比他们做的更专业一些。在思考了几个月后,2015年11月,我申请离职,开始脱产学习 Python。
『他们不行,我上!』这个理由,其实是我学很多东西的动力。例如两年多前学爵士鼓,就是看侨城堂教会的鼓手实在太水、于是买了 Roland TP4K 开始练习的。后来没有坚持练下去,水平也就一般般,但临时顶场什么的已经无压力了。
断断续续学了大半年 Python,在闭门造车的做了几个小项目后,我从2016年9月开始投简历。最开始在拉勾上被拒了大概二十几遍,只拿到一个面试,是给一家网站做分布式爬虫,面试结果不好,而我对这种纯应用型的部门也不太感冒(虽然自己技术不好,但一直有个目标,就是要去技术型的公司)。
后来觉得这种海投策略不行,郭老师给我提意见,说写个 cover letter 吧。我乖乖的听话,而当时自己完全没想到这个举动会带来后面的巨大收获。

某日在 v2ex 上闲逛,发现 Ricequant 在招聘 Python 工程师,于是研究了一下这家创业公司,发现居然还开源了一个量化策略研究框架,创始人技术也很好,就写了一封长长的 cover letter 过去,居然也混到了一个面试(收到 Ricequant 面试通知电话的时候,我正在上文提到的那家公司面试中)。9月27日来到 Ricequant ,CTO 正和另一个求职者谈话,于是安排了一位工程师来面我,很快工程师觉得我基础太差无法胜任。CTO 此时也闲下来了,简单聊了一下后,留了学习排序算法的作业。后来我整个十一假期都在做这个作业。
十一结束后发邮件交付了作业,以为可以轻松一下了,但1个小时后就收到回信,要求用代码实现所有排序并提了一堆需求。二话不说,接下来一个星期就继续埋头苦干,把之前没搞懂的面向对象、递归、单元测试等等搞定。第2次作业交付后,长舒一口气,但是还是在2天后收到催命邮件,要求我继续优化代码。这一次把算法部分和界面部分分开,同时做多线程优化等等。就这样又忙了5天,交付了第三次作业,同时也第二次去 Ricequant 面试,并现场拿到 offer。我问了 CTO 为什么会这样反复测验和面试我这样的初学者而不是直接筛掉,他说你 cover letter 太有激情了。此处为郭老师鼓掌三分钟。
(在二面 Ricequant 之前,我还收到了腾讯云的电话面试,依旧因技术太差而被直接告知不行,但建议我转投运营开发岗位。面试我的工程师人也很好,但我没有再投腾讯。)
从开始学习 Python,到找到工作,刚好一年。一年间,我的学习速度很慢,又是零基础,对自己的要求也不严格,经常连续半个月没写几行代码。好在朱老师一直鼓励我,说小步快跑是坠吼的,不用强求速度。事实也证明我的确更适合这种轻松的学习状态,而不是苦大仇深的埋头苦学。
我在刚开始入门时报过开智的 Python 入门班,相信我,很垃圾,不要浪费钱。Python 的入门资料很丰富,看书、在 Stackoverflow 和 Google 上查资料、在 Github 上给牛人提 issue,就已经完爆你能找到的所有国内培训课程了,而这一切都是免费的。
学写代码是我这个习惯性半途而废者第一个坚持下来并让我进入职业圈子的事。我依旧是小白一个,要学的东西太多了,对未来很期待也很紧张。但一年的学习让我找到了一种自信,就是无论在哪里都要坚持下去,为了家人,为了自己,如果需要做律师,我就去读法学院,如果需要牙医,我就去读医学院,如果需要木匠,我就拜师学木艺。1年不够就2年,2年不够就10年,总会有实现目标的一天。
今天是2016年的1024程序员节,在耕耘一年后终于有了收获,我很骄傲。

Tagged : / /

Python 中 list 的传值问题

我在做一个小程序,需要生成一个随机数列表,然后将之赋值给2个 list,并需要这两个列表完全独立(即列表值指向不同的内存地址)。最开始是这样的:

>>> a = [5,4,3,2,1]
>>> b = a
>>> print(a,'-',id(a)) # id是 python 查看对象地址的方法
[5, 4, 3, 2, 1] - 4516275720
>>> print(b,'-',id(b))
[5, 4, 3, 2, 1] - 4516275720 # 显然,此时a和b指向同一个地址
>>> b.sort() # sort()是 python 的内置排序函数
>>> print(b,'-',id(b))
[1, 2, 3, 4, 5] - 4516275720
>>> print(a,'-',id(a))
[1, 2, 3, 4, 5] - 4516275720 # 我去,怎么回事???a 怎么也变了?

Python 的变量赋值机制并不是真的给变量赋值(实际上从头到尾都不存在 list 的容器),只是把变量名当做一个标签,贴在内存地址上,当值发生变化的时候,并不是改变值本身,而是将内存地址对应的标签『唰』的一下撕下来,然后贴到另一个地址上——此所谓『铁打的内存,流水的变量名』。
对于复制 list,按照官方文档的说法,应该这样操作:

b = a[:]
# https://docs.python.org/3/faq/programming.html#how-do-i-copy-an-object-in-python

此时是这样的:

>>> a = [5,4,3,2,1]
>>> b = a[:]
>>> print(a,'-',id(a))
[5, 4, 3, 2, 1] - 4516276488
>>> print(b,'-',id(b))
[5, 4, 3, 2, 1] - 4516276232

可见在 b = a[:] 这一过程中,Python 在内存中创建了一个新值,并将 b 的标签贴到了上面,迥异于我们最开始的过程。
其实上述过程并非发生在所有数据类型中。

>>> A = 5
>>> B = A
>>> id(A)
4540535120
>>> id(B)
4540535120
>>> B = 3
>>> A
5
>>> id(A)
4540535120
>>> id(B)
4540535056

关于这个问题,我还没有研究明白,还没搞懂到底哪些变量是这样传值的,算是一个小小的坑吧。
参考资料:

  1. http://stackoverflow.com/questions/8744113/python-list-by-value-not-by-reference
  2. https://docs.python.org/3/faq/programming.html#how-do-i-copy-an-object-in-python
Tagged : /

几种排序算法的比较

整个十一假期就在折腾这几个算法,这篇总结性文章就是简要的介绍了几个基础算法的特性,并附带了 Python 的实现。
不同算法适合不同情况的数组,但在不知道输入规律的时候,使用时间复杂度低算法的比较保险。
Big O:上界
Big Ω:下界
Big Θ:确界

Big O 比较

big_o_complexity
O(n²):冒泡排序(稳定)/选择排序(不稳定)/插入排序(稳定)
O(nlgn)~O(n²):希尔排序(不稳定)
O(nlgn):堆排序(不稳定)/归并排序(稳定)/快速排序(不稳定)

Bubble Sort 冒泡排序

def bubble_sort(arry):
    n = len(arry)                   #获得数组的长度
    for i in range(n):
        for j in range(1,n-i):
            if  arry[j-1] > arry[j] :       #如果前者比后者大
                arry[j-1],arry[j] = arry[j],arry[j-1]      #则交换两者
    return arry

时间复杂度、稳定性

平均情况:O(n²)
最坏情况:O(n²)
最好情况:O(n)
稳定
辅助空间O(1)

特点

最优情况为全部正序时经过 n-1 次比较即可完成排序,最差情况是倒序。因此冒泡算法对数组的有序性很敏感,适合对规模较小、且比较有序的数据进行排序。[1]

优化方案

  1. 如果某一次遍历没有发生数据交换,则代表已完成排序,可停止迭代。
  2. 记录遍历时最后一次数据交换的位置,后面的数据已经有序,因此可以缩小下次循环的范围。

Selection Sort 选择排序

def select_sort(ary):
    n = len(ary)
    for i in range(0,n):
        min = i                             #最小元素下标标记
        for j in range(i+1,n):
            if ary[j] < ary[min] :
                min = j                     #找到最小值的下标
        ary[min],ary[i] = ary[i],ary[min]   #交换两者
    return ary

时间复杂度、稳定性

平均情况:O(n²)
最坏情况:O(n²)
最好情况:O(n²)
不稳定
辅助空间O(1)

特点

运行时间与输入状态无关(随机排列与正序排列消耗相同的时间)。同时移动次数最少(与数组大小呈线性关系)。[1]

Insertion Sort 插入排序

def insert_sort(ary):
    n = len(ary)
    for i in range(1,n):
        if ary[i] < ary[i-1]:
            temp = ary[i]
            index = i           #待插入的下标
            for j in range(i-1,-1,-1):  #从i-1 循环到 0 (包括0)
                if ary[j] > temp :
                    ary[j+1] = ary[j]
                    index = j   #记录待插入下标
                else :
                    break
            ary[index] = temp
    return ary

时间复杂度、稳定性

平均情况:O(n²)
最坏情况:O(n²)
最好情况:O(n)
稳定
辅助空间:O(1)

特点

输入状态会影响运行效率,对有序数组排序要比对随机排列、逆序排列的数组快,因此适用于部分有序的非随机数组。当『数组中每个元素距离它的最终位置都不愿』『一个有序的大数组接一个小数组』『数组中只有几个元素的位置不正确』时,插入算法的速度很可能比其他算法都快。[2]

Shell Sort 希尔排序

def shell_sort(ary):
    n = len(ary)
    gap = round(n/2)       #初始步长 , 用round四舍五入取整
    while gap > 0 :
        for i in range(gap,n):        #每一列进行插入排序 , 从gap 到 n-1
            temp = ary[i]
            j = i
            while ( j >= gap and ary[j-gap] > temp ):    #插入排序
                ary[j] = ary[j-gap]
                j = j - gap
            ary[j] = temp
        gap = round(gap/2)                     #重新设置步长
    return ary

时间复杂度、稳定性

平均情况:O(nlgn)~O(n²)
最坏情况:O(n²)
最好情况:O(n1.3)
不稳定
辅助空间:O(1)

特点

希尔排序将数组分成较短的子数组、并使之部分有序,很适合插入排序。希尔排序对中等大小数组的排序时间可以接受,代码量小,且不需要额外内存空间。当没有系统排序函数可用时,可以考虑先用希尔排序,再考虑是否值得替换为更复杂的排序算法。[3]

Merge Sort 归并排序

def merge_sort(ary):
    if len(ary) <= 1 : return ary
    num = int(len(ary)/2)       #二分分解
    left = merge_sort(ary[:num])
    right = merge_sort(ary[num:])
    return merge(left,right)    #合并数组
def merge(left,right):
    '''合并操作,
    将两个有序数组left[]和right[]合并成一个大的有序数组'''
    l,r = 0,0           #left与right数组的下标指针
    result = []
    while l<len(left) and r<len(right) :
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

时间复杂度、稳定性

平均情况:O(nlgn)
最坏情况:O(nlgn)
最好情况:O(nlgn)
稳定
辅助空间:O(n)

特点

归并排序在最坏的情况下复杂度为O(nlgn),和其他基于比较的排序算法所需的最小比较次数相同。

Quick Sort 快速排序

用递归在 Python 中实现快速排序会遇到 RuntimeError: maximum recursion depth exceeded 的错误提示,原因是 Python 的递归深度默认为1000(可以用 sys.getrecursionlimit() 来查看),有两种方式解决为题。一种是用循环重写算法,另一种比较简单粗暴,直接用 sys.setrecursionlimit(99999) 把递归深度设置为 99999 这种大数字,更详细可参见这里

def quick_sort(ary):
    return qsort(ary,0,len(ary)-1)
def qsort(ary,left,right):
    #快排函数,ary为待排序数组,left为待排序的左边界,right为右边界
    if left >= right : return ary
    key = ary[left]     #取最左边的为基准数
    lp = left           #左指针
    rp = right          #右指针
    while lp < rp :
        while ary[rp] >= key and lp < rp :
            rp -= 1
        while ary[lp] <= key and lp < rp :
            lp += 1
        ary[lp],ary[rp] = ary[rp],ary[lp]
    ary[left],ary[lp] = ary[lp],ary[left]
    qsort(ary,left,lp-1)
    qsort(ary,rp+1,right)
    return ary

时间复杂度、稳定性

平均情况:O(nlgn)
最坏情况:O(n²)
最好情况:O(nlgn)
不稳定
辅助空间:O(nlgn)~O(n)

特点

在实际应用中,一般比其他算法快很多,内循环很小,原地排序(仅需要很小的辅助栈),且将长度为 N 的数组排序的时间与 NlgN 成正比。但很脆弱,实际性能会因某些错误变成平方级。[4]
快速排序和归并排序使用分治法和递归进行排序,但快排在合并子数组后是自然有序的大数组;归并在合并阶段则繁琐一些,还要再次进行比较。
在对数组进行切分不平衡时,会导致性能低效(例如第一次从最小元素切分、第二次从第二小的元素切分……)。解决该问题,可以对数组进行随机排序,避免性能下降到极低。

优化

  1. 快排在小数组中比插入排序慢,因此在排序小数组时使用插入排序。
  2. 三取样切分。
  3. 熵最优排序[5]

以上三种优化是《Algorithms 4th》中对于快排性能的优化,都是对算法本身做了一些改进。而最著名的优化则是《算法导论》中提到的『随机化快速排序』,与上述三种性能优化有很大不同。
随机化快速排序,一般来说都是将取主元的过程随机化。随机化快速排序的『优化』,并没有提高快排的性能,而是避免了某些序列使快排性能大幅降低到O(n²)的可能性、防止他人设计一个序列对服务器发起DoS攻击,使排序更加稳定和安全(我发现还有很多人有类似的误解)。事实上随机化快速排序和普通快速排序在时间复杂度上同为O(nlgn),实际实验中也没有显著差异。

知乎上一个用户对快排和随机快排的性能做了测试,但我猜他可能也理解错了,他所做的只是在优化随机快排的代码,但并没有显著提高算法性能或降低复杂度(知乎链接)。Thomas Cormen 在 Quora 中也回答了关于随机化快排和普通快排性能差异的问题(Quora链接),但是他本人在《算法导论》(中文版100页,英文版179页)中并没有把这个问题讲的很透彻,也许算是一个微小的失误。

Heap Sort 堆排序

def heap_sort(ary) :
    n = len(ary)
    first = int(n/2-1)       #最后一个非叶子节点
    for start in range(first,-1,-1) :     #构造大根堆
        max_heapify(ary,start,n-1)
    for end in range(n-1,0,-1):           #堆排,将大根堆转换成有序数组
        ary[end],ary[0] = ary[0],ary[end]
        max_heapify(ary,0,end-1)
    return ary
#最大堆调整:将堆的末端子节点作调整,使得子节点永远小于父节点
#start为当前需要调整最大堆的位置,end为调整边界
def max_heapify(ary,start,end):
    root = start
    while True :
        child = root*2 +1               #调整节点的子节点
        if child > end : break
        if child+1 <= end and ary[child] < ary[child+1] :
            child = child+1             #取较大的子节点
        if ary[root] < ary[child] :     #较大的子节点成为父节点
            ary[root],ary[child] = ary[child],ary[root]     #交换
            root = child
        else :
            break

时间复杂度、稳定性

平均情况:O(nlgn)
最坏情况:O(nlgn)
最好情况:O(nlgn)
不稳定
辅助空间:O(1)
2. 特点
目前唯一的能最优利用时间与空间的算法,最坏情况下也能保证 2NlgN 次比较和恒定的辅助空间。当空间紧张时(例如嵌入式),堆排序用几行代码就能实现实现较好性能。
缺点是无法利用缓存,缓存未命中的次数远高于大多数在相邻元素间比较的算法。
sort

通过倍率实验预测程序的增长数量级

可以使用倍率实验来预测任意程序的增长数量级:
每次实验时使输入翻倍,计算时间,并求两次运行时间的比值。反复运行直到比值趋近于2的b次方。[6]

算法的『稳定性』是什么

稳定性指,当排序的元素中有相同的值时,这些具有相同值的元素在排序后的前后位置是否发生变化的性质。如果变化,则不稳定;如果不变化,则稳定。在 Bubble Sort 中,相邻元素互相交换,如果两个相邻元素相等则不需交换;如果两个相等的元素彼此之间有间隔,那么即便它们和相邻元素交换后,其相对的前后位置也不会发生变化,所以是稳定的。而在 Selection Sort 中,第一个元素与最小的元素交换、第二个元素与第二小元素交换等等,间隔有可能很大从而在交换时跳过了相同值的元素,进而造成相同值元素前后位置改变,因此是不稳定的。
排序的键值有可能只是元素的一个属性,如果元素本身还具有其他属性,那么键值相同的元素排序后的相对顺序还与其他属性有关。例如用稳定的算法对员工按工资排序,假如原数组是按年龄排序的,那么月薪同为7000元的3个人在按工资排序后仍然可以保持年龄正序,即最初的相对位置不变。

参考资料:

[1]《Algorithms 4th》 P248
[2]《Algorithms 4th》 P252
[3]《Algorithms 4th》 P262
[4]《Algorithms 4th》 P288
[5]《Algorithms 4th》 P296
[6]《Algorithms 4th》 P121

Tagged : / / / /

完成《Flask Web Development》纪念

DSC_0129-01_meitu_1
(上图为计划中的下一本书《Web Scraping with Python》)
这本 Flask 教材抱着啃了一个月,终于搞定了。标题里之所以说是『完成』而不是『学完』,是因为实际上我确实只是完成——所有的代码都手打了一遍。但是到底学没学会,对自己持悲观态度。这本书内容比较集中,但是细节很多,我又是第一次接触 web 框架甚至是第一次接触 web 开发,读完全书、打完全部代码,实际上也只是盲人摸象的对 web 开发有了大致印象,远远不能算『学会』。(Ps.本书中有若干小错,例如代码文件的路径等等,但是辨识后不影响学习。官方提供的代码有一些教材内的功能没有完成。)
不过我对这种感觉也并不陌生。在完成《笨方法学 Python》的时候,也有类似的体验,书中内容都学了,但合上书后并不知道自己能实现什么,深深的『啥都不会做』感,只是后面接触了更多的 Python 知识后,这种不安才慢慢消散。有了那一次的经验以后,我就不再担心这种『无力感』。相信这种感觉在短时间内可能还会重现多次,但并不代表我真的『啥都不会做』。
回顾一下从去年11月开始至今的学习,自己的速度并不快。学习过的书有:

除了笨方法以外,其余都是英文。所以读这些技术书,对自己的英文阅读也有一些帮助。从《Automate》一书开始,我习惯将原书 PDF 下载后通过淘宝打印。并且多亏了朱老师的全程指导,才能在转行程序员的道路上坚持走下去。
目前写过的一些小工具:

  • 桌游《阿瓦隆》——基本使用 python 语法把规则写了一遍,当时完全不知道数据库,也不懂部署。
  • 基金净值统计——用爬虫抓取自己的基金现价,然后计算目前自己的持仓市值
  • 给基友用 pandas 做的数据处理脚本——这个代码最少,但是我最喜欢,因为解决了原本很麻烦的实际问题。
  • 其他的都是一些跟着教程做出来的东西。

在 Python 的各个用途中,最让我感到神奇的是爬虫和数据处理,也是我曾经实现过的两个脚本的功能。爬虫可以自己阅读、解析、抓取、统计网络上的各种数据、甚至可以跨过 JS 像真实用户一样去操作页面;而 pandas/numpy 这些工具居然可以以远超过我想象的速度处理惊人的数据。我希望自己能够在这两方面加深一下学习。
后面我为自己规划的学习路径是这样的:
1、完成实验楼的 Flask 轻博客项目(已完成)
2、开发一个自己的网站(还没想好需求)
3、完成《Web Scraping with Python》
将这三个任务完成,目测应该已经起码到达八月中旬了。届时找一份 junior developer 的工作应该问题不大。如果在工作之余仍有时间学习,会继续在爬虫和数据处理方面钻研,然后看看自己更喜欢哪方面。

Tagged : / / /

用 python + pandas 帮朋友处理数据

郭老师发小的老公,在一家 Apple 手机电池供应商工作。这天在朋友圈抱怨,用 Excel 处理几十万条数据,i7 处理器 5 分钟进度 1% 。我一下反应过来,这玩意用 Python 处理起来应该很快啊!
于是留言给他说,用excel跑最起码几个小时,让他把文件和处理要求发给我。
过了一会,邮箱收到。其实比较简单,文件 A 有40万条电池数据,文件 B 有30万条良品电池数据,要用 A 减掉 B,剩下来的就是不良电池的数据。数据处理的目标即得到汇总了不良电池数据的文件 C 。
这里有个小插曲:文件 A 有40多万行数据,我用 Mac 的 Number 打开,仅能显示 65535 条。看来 Numbers 处理稍大一点的数据就完全不行了。为了能顺利检视数据结果,又下载了 OpenOffice。
虽然之前没接触过 Python 的数据处理,但是学习过用 Python 的 openpyxl 处理 Excel 表格,所以我的第一反应就是用 xlrd 这种第三方库来处理 Excel 无法快速处理的文件。但是在学习 xlrd 的过程中,发现 xlrd 可以比较好的读取文件,却不能很好的写入文件,于是 又下载了对 Excel 写入支持较好的 xlwt 。
折腾了半天,虽然实现读写,但是对表格的处理还是不满意。随便搜一搜,发现 pandas 也可以做这个工作。于是转向 pandas 。
pandas 支持读取/写入 XLSX 和 CSV 格式,由于我用的是 Mac ,因此将文件先统一转换成了 CSV 。
首先用 pandas 读取 CSV 文件并转化为 DataFrame:

df = pd.read_csv(workbook, low_memory = False)

然后将文件 B 复制到文件 A 需要去重的列下方(这里可以用代码操作,但是我没有查操作函数,因为感觉手动复制粘贴也很方便)。再用 drop_duplicates 函数去掉重复的项(这里需要注意,drop_duplicates 有好几个参数,可以选择留下重复项中的第一项、最后一项、或者全删掉,视需求而定)。

new_df = df.drop_duplicates(subset = '要去重的列名称,必须英文', keep = False)

最后用 to_csv 函数保存成新的 CSV 文件即可。脚本一共 5 行代码,运算处理时间只有几秒钟。
为了减少朋友以后的工作量,我把脚本写好发给他,并将『文件名』等可自定义的部分留空了。有兴趣请点 这里 看我写的脚本。
这个 5 行代码脚本我大约写了三个小时,主要时间都在学习。在帮了朋友的忙时,也实现了我 Python 学习史的好几个第一次:
第一次现学现卖,当天下午就用陌生的知识完成任务。
第一次帮朋友解决了实际问题。
第一次完成了一件数据处理工作。
非常开心,非常值得纪念!

Tagged : / /

解决设置环境变量时的错误 ZSH: BAD ASSIGNMENT

在学些《 Flask Web Development 》Chapter 6 时,因为不可将敏感信息(用户名/密码) 写入代码,因此需要在开发环境中手动设置环境变量,让程序能够从中读取敏感信息。
通用的方法是使用 export ,例如:

$ export MAIL_PASSWORD = XXXXXXXX

然而在命令行中执行这条命令时,会出现错误提示:

zsh: bad assignment

研究了半天没搞明白是哪里出错,Google 了一下才明白,原来是代码编写习惯惹的祸——而我习惯性的在等号前后加入便于阅读的空格,这在 export 语句看来是一个语法错误。删掉空格,问题解决。
所以你看,好的代码习惯偶尔也会带来麻烦!

Tagged :

配置 Hexo + Github 博客的若干恶心处

首先严厉批评一下 Hexo 官方,文档过于落后,导致官方提供的安装配置方法竟有很多错误,给大量用户造成极高的配置成本,而这些本来是不需要用户来承担——软件更新了文档却不改,你是要上天?
声明一下我的环境版本,如果你在网络搜索配制方法,请一定关注一下作者使用的版本,否则可能会有坑。

hexo 3.2
node.js 5.10.1
hexo-cli 1.0.1

一些常见问题的处理方案:

问题一:Mac 用户配置 Hexo 前安装 Command Line Tools

官方文档说,Mac 用户在配置 Hexo 时可能会出现一些错误,因此需要在配置前安装 Xcode,并通过 Xcode 安装 Command Line Tools。
大写的坑爹!
Xcode 自版本 5 之后,就将下载 Command Line Tools 的功能移除,而目前 Xcode 最新版本是 7.3 ,可见 Hexo 官方有多久没有更新文档了!大多数对 Xcode 没有任何需求的人,把将近 5G 的 Xcode 下载安装后发现对自己毫无帮助,该是怎样一种草泥马的心情?
苹果已向开发者单独提供 Command Line Tools,一共约 150M 大小,安装后约 450M 。

下载链接:
https://developer.apple.com/downloads/

当然咯 Command Line Tools 也可以通过 命令行 来安装:

$ xcode-select --install

问题二:npm install hexo-cli -g 后出现无写入权限问题

由于 npm install 会对 /usr/local/bin 文件夹进行修改,需要 root 权限,因此只需在命令前加 sudo 即可:

$ sudo npm install hexo-cli -g

问题三:文档中用命令行安装nvm的代码错误

由于 Github 上代码地址发生了更改,而 Hexo 官方文档提供的依旧是旧地址,因此用户如果按照官方教程进行配置就会安装失败。
官方的失效代码:

$ curl https://raw.github.com/creationix/nvm/master/install.sh | sh (本行有错,仅供鞭尸,请勿使用)

正确代码如下:

$ curl https://raw.githubusercontent.com/creationix/nvm/master/install.sh | sh

问题四:执行 hexo 命令时的 MODULE_NOT_FOUND 问题

在按照官方说明执行 hexo init blog (或者任意 hexo 命令)时,出现三个 Error: Cannot find module的问题。

{ [Error: Cannot find module './build/Release/DTraceProviderBindings'] code: 'MODULE\_NOT\_FOUND' }
{ [Error: Cannot find module './build/default/DTraceProviderBindings'] code: 'MODULE\_NOT\_FOUND' }
{ [Error: Cannot find module './build/Debug/DTraceProviderBindings'] code: 'MODULE\_NOT\_FOUND' }

我在 hexo 的 issue 中发现大家有几种解决方法:

  1. 先卸载 Hexo ,然后仅安装 Hexo 的核心部分,放弃可选项,代码如下:
$ npm uninstall hexo
$ npm install hexo --no-optional

同时有群众表示,新版本中需要添加 –save 参数,代码如下:

$ npm uninstall hexo
$npm install hexo --no-optional --save

两种方法我都试过,对我无效。但对你可能有用,不妨一试。

  1. 在 Github Issue 下面,有人提醒也许问题并不出在 Hexo 或者 Node.js 身上,而是错误信息中那个 DtraceProviderBindings 模块的问题。相关链接在此

问题五:部署到Github上的若干小坑

  • 要在blog目录下安装hexo-deployer-git
    这里我一直犯错,在用户根目录下安装,然后显示找不到目录云云。实际应该先进入blog目录,然后执行以下命令:
$ npm install hexo-deployer-git --save
  • 如前文所述,执行 hexo 系列命令时,module_not_found 问题始终没有解决,但是目前看来,似乎并不影响程序的执行。所以这个错误应该是 OSX 中的某个细节问题,而非 Hexo 的问题。但每次都有这么个尾巴毕竟不爽,后面我会继续跟踪学习,尽量找到解决方案。

  • 详细的安装步骤、以及写博客编辑页面等命令,都在官方文档中,不再赘述。

Tagged : /