我时不时会收到一些小朋友们的私信，问是否招实习生或者「程序员学徒」的，可以不要薪水。我一般回复「没有」，就不再多说什么了。并不是我高冷，而是觉得这样的小朋友恐怕并没有什么潜力值得去挖掘。
这么冷酷的结论，并不是拍脑门想出来的。经历了多次打脸，我最终明白一个道理——如果一个人把「廉价」甚至「不要工资」作为核心竞争力，那么他不仅对自己没有信心，其实也不会有任何主动性去发展自身。他们只期待一个武林高手从一招一式开始教起，像妈妈带娃一样照顾始终，而自己只需负责饭来张口即可，希望在人畜无害的气氛中，无能的成长起来。
显然这是做梦。即便这样一位「程序员学徒」不要工资，其他人为了培养他而投入的巨大精力和时间难道不值钱？武林高手有这个时间干点什么不好，不能去争一争武林至尊吗？为什么要把时间浪费在一个连学习知识技能都需要他人喂食的巨婴身上呢？这些幻想成为「程序员学徒」的小朋友明显算错了数，他们以为「不要工资」是自己的巨大优势，实际上这样的人带来的往往是负价值，对团队和项目都有巨大损害。
举一个我自己的例子。我曾经在一个水平相当低的工程师身上耗费了近半年时间，从 Google 搜索引擎和 stackoverflow 的用法，到代码规范，到 Python 各个标准库的用法，再到各类 Pythonic 代码的写法。之所以耗费这么大精力，是因为我是一个不错的老师，能把很多道理讲的深入浅出（例如我可以在 1 分钟时间里让任意一个无技术背景的人理解金融量化交易引擎的技术原理），经过我的细致培训，他一定有机会成为一个代码细腻而简洁的工程师。
直到被我劝退前，他都一直在用百度搜中文关键词并跳转到 CSDN 上看技术文。
这是什么概念呢？就是一个数学老师教了你半年的二项式展开，最终面对最简单的二项式题，你依然在掰手指数数。
这样的程序员带给同事的往往是噩梦。在他离职之后，我们依然时不时的从他代码中发现骇人的 bug，然而数据已经被污染，重新修正几乎不可能。由他引入的问题，很有可能直到公司破产都不会有人愿意去解决。这样巨大的负担，当年的我如果更成熟一点，是万万不会惹祸上身的。所以现在收到各类的「不要工资」的申请，心里都会默默的想，「你当我是傻子么」。
每个人都渴望成长，但成长不是商品，不是你用「不要工资」就能够换回来的。成长源于你一步一个脚印的学习，在学习过程中，你又创造出了价值。本质上，只有当你持续创造价值的时候，你才会成长；而不是反过来。
如果你技术不好、没公司要你，能否在力所能及的范围内，对开源社区做一点贡献？
如果你技术不好，能否仔细研究业务代码，试着花一个月甚至两个月的时间写一个简单但核心的模块？
如果你技术不好、又想找个老师，能否先帮这个老师做一点事情、哪怕只是帮他写单元测试？
……
可做的事情太多了，简直数都数不过来，而它们的共同点就是——持续创造价值，而不是持续索取关照。
所以，当我们对一件事情有了强烈的渴求时，最好先问问自己，能不能用已有的技能先创造一些价值出来。如果不能，说明你其实并没有那么渴求。那么，请不要再去骚扰那些工作量已经很饱和的工程师了，码农滞销，可怜可怜老乡们吧。
分类： 技术
给马蜂窝支招
互联网运营中，存在一种非常隐晦却不可不谈的手段，谓之「虚假运营」。虚假运营指用假数据，给用户或者竞品造成某种错觉，从而达到运营目标。从马化腾在 OICQ 上装女生陪用户聊天，到 Airbnb 将 Craiglist 的数据塞到自家网站上，再到新手玩吃鸡手游会匹配到人机、更容易获得胜利，都体现了这是一种隐匿而重要的互联网运营手法。
然而运营者必须对数据负责，对结果负责，对用户和产品负责。这次马蜂窝被爆 UGC 数据造假，其曝光方式异常简单，甚至无需专业人士出马，普通用户稍加观察，都能轻易发现端倪，体现出其运营团队低下的运营能力。
换句话说，造假都造不好，还能指望它「造真」么？
针对马蜂窝拙劣的运营手法，我提供一些技术方案，用开发手段解决运营问题，估算一下工程量：一个后端开发工程师 + 2 个运营专员，可以在一个月时间内搞定开发、测试、上线。如实在无能为力，也可请我作咨询，连开发带运营，我一个人就够了，给你们省点钱。
长话短说，解决马蜂窝的虚假数据问题，可分五步走：
- 对马甲和内容数据分类、打标签
- 对「有毒内容」进行过滤
- 调研真实用户行为特征
- 开发自动化内容发布系统
- 优化运营人力
一、对马甲和内容数据分类、打标签
在今天曝光的蚂蜂窝数据造假证据中，马甲人设来回变换、点评内容忽男忽女，即便是普通用户，只要稍微细心，都可以发现其造假实锤（例如刚和老婆在上海喝完咖啡，就带老公去深圳吃面）。
首先，批量生成小号，并对其打标签（如 25 岁白领单身女性，32 岁企业管理层已婚男性，19 岁广东省大学女生等等），其属性划分应该符合网站真实用户的正态分布（例如 80 岁老爷爷应该不太会是蚂蜂窝的主力用户吧）。
其次，对爬来的点评数据进行类似处理，按作者性别、年龄、婚姻状态等进行标签归类，便于未来发布内容时，「女性大学生」人设的账号不至于发布出「携老婆和丈母娘旅行」的内容。其中，最重要的属性是性别，在爬取数据应顺便解决性别数据，搞定性别，大约 90% 的点评数据不会出现严重错位。
这个步骤的意义在于，将马甲账号与点评内容关联起来，营造出真实用户的氛围。当马甲账号发布消息时，可通过相应的匹配规则获取符合其人物设定的内容，被现场抓包的问题基本可以解决。
二、对「有毒内容」进行过滤
把爬取到的评论中附带的竞品名字（大众点评/美团/携程等），按照渠道来源，直接替换成自己的产品名，（例如从大众点评爬来的数据，统一把「大众」「大众点评」「点评网」等关键词替换为「马蜂窝」），虽然有可能产生内容不精确问题，但是远好于被读者及同行抓现行。
同理，爬虫在爬取数据时被对方以「插入推广链接」等方式「反爬」、导致存在部分脏数据，应及时清理。
运营人员还需要定期抽样检查数据，对存在的问题进行跟踪，发现问题后可以制定数据修改规则，使用脚本对数据进行批量修改，定期对规则进行迭代。
三、调研真实用户行为特征
暂停所有马甲账号发布，对真实用户进行为期一个月的行为观测，统计网站用户的真实活跃时间、频率和点评数量。
四、开发自动化内容发布系统
按照已被揭露的马蜂窝虚假内容发布时间来看，大概率是运营团队花费了大量人力在其工作时间段内发布，而这毫无必要。后端提供写入接口，并使用脚本或服务定期定量的写入数据，可以将大量人力工作直接转化为自动化任务。
后端开发工程师应该为运营部门提供两个组件：按标签获取点评内容的消息队列，以及写入内容的接口。然后设置定时任务进行批量写入操作，时间规则参考上一条用户真实行为特征，且写入时间可随机做小幅波动，尽量贴近真实用户行为。
五、优化运营人力
通过上述方法解放出来的运营人力，应该全力负责下述方面：
1. 如何用更好的方法将马甲账号与爬取到的内容匹配起来？
2. 怎样持续优化点评内容质量、以及迭代检验内容合格与否的标准？
3. 持续观察真实用户行为，要对自己的产品和用户有更更更更深入的理解。
4. 与工程团队对接，寻找优化这套「自动化发布系统」的方法，应有运营专员负责该系统的需求与迭代。
做到以上几个方面，我相信很少有用户用户或机构可以再通过运营数据观测到虚假运营。因为虚假运营的本质就是模拟用户真实行为，面面俱到，则可最大限度减少破绽。当然虚假运营的手段多处于灰色地带，而一家正经企业也不能一辈子鸡鸣狗盗，其最终目标依然是获取更多「真实用户」并提高其活跃度和消费额，将「假数据」转变为「真数据」。广大互联网运营人士，应以蚂蜂窝为鉴，时刻提醒自己，在实战中要更专业、更专注。
程序员年龄增大后的职业出路是什么？
这篇文章是我在知乎上的的一个回答，讲的略微有点深。另外感觉自己这两年越来越左翼，越来越觉得马克思不愧是20世纪最伟大的思想家之一。
今年 30 了，也开始考虑年龄问题了。
不过虽然 30 岁，但我实际作为程序员、以编程为业，也只是最近两年的事情（关于我的编程职业经历，在这个回答里写的比较详细：知乎用户：自学编程的人，都是怎么找到第一份软件开发工作的？）。因此对编程这个职业的理解，可能还不如一些 90 后小朋友深，写的不对的地方贻笑大方，请见谅了。
注：以下叙述，不局限于程序员，实际上包含所有职业。
中国的程序员在市场中的地位，不客气的说，随便翻开《1844经济学哲学手稿》里描写产业工人的段落，把这些一百年前的论断放到程序员身上，都言之凿凿：
例如：关于程序员的先进生产力与其对应的可怜回报
「的确，今天由于有了新的动力和完善的机器，棉纺织场的一个工人往往可以完成早先 100 甚至 250-350 个工人的工作。在一切生产部门中都有类似的结果，因为外部自然力日益被用来加入〔Ｘ〕人类劳动。如果说为了满足一定量的物质需要必须耗费的时间和人力比现在比过去减少了一半，那末，与此同时，在不损害物质福利的情况下，给精神创造和精神享受提供的余暇也就增加一臂。但是，在我们甚至从老克伦纳士自己领域中夺得的虏获物的分配方面，仍然取决于像掷骰子那样盲目的、不公正的偶然性。法国人有计算过，在目前生产状况下，每个有劳动能力的人平均每日劳动五小时，就足以满足社会的一切物质利益……尽管因机器改进而节省了时间，工厂中奴隶劳动的时间对多数居民说来却有增无已。」
例如：关于「越工作越贫穷」这一现象的分析
「工人生产的财富越多，他的产品力量和数量越大，他就越贫穷。工人创造的产品越多，他就变成廉价的商品。物的世界的增值同人的世界的贬值成正比．劳动不仅生产商品，它还生产作为商品的劳动自身和工人，而且是按它一般生产商品的比例生产的。」
例如：关于程序员异化为程序的奴隶
「因此，工人在这两方面成为自己的对象的奴隶：首先，他得到劳动的对象，也就是得到工作：其此，他得到生存资料。因而，他首先是作为工人，其次作为肉体的主体，才能够生存。这种奴隶状态的顶点就是：他只有作为工人才能维持作为肉体的主体的生存，并且只有作为肉体的主体才能是工人。」
以上，并不是呼吁大家都去读马克思，我也无意挑起关于马克思的政治经济学的争论（也希望大家尊重题主和读者们，不要做跑题辩论），只是希望各位静下心来想一想，我们和百多年前的纺织工人的区别，到底是什么？
伴随一个产业工人或程序员的老去，不可避免的是工作时长与强度的降低、工资的刚性提升（正常来说只能升不能降）、对家庭福利需求的增高（例如需要公司为家人购买保险）等等。而普通工人（程序员）的工作效率增长速度一旦无法达到其福利需求的增长速度，在公司里即成为累赘。换句话说，辞退你、换新人，对公司有很大好处，而这对资方来说是一个巨大的诱惑。
多亏劳动法和近二十年来的互联网产业红利，程序员的处境已经远远优于当年的工人，不用时刻担心被辞退，但是当到达了一定年龄后，大多数程序员的个人价值已到峰值，收入封顶，但生活压力却越来越重。这是「年龄-收入」的悲剧冲突核心，也是大量程序员夙夜忧叹的唯一原因。
而这种悲剧，集中式的出现在中国，其直接表现就是程序员的薪酬过低（例如在美国，普通工程师拿个十几万刀的 package 并不算天方夜谭，这种问题也就并不严重。）。
所以程序员老了怎么办？唯一靠谱的解答，就是脱离自己的产业工人身份，直面残酷的市场食物链，尽一切可能向上爬，脱离这个「产业工人诅咒」。
那么程序员以上的食物链有哪些？最直接的就是技术管理层、公司中高层，再次是资本方，最后是权力方。故而其方法也分外直接：要么争做管理层并获取股份、股权激励等非劳动收入，要么以资本进行投资、让别人为你打工，要么当个省委副书记、起码乡镇干部之类（这一条过于奇幻，当做笑话吧）。
但凡符合上述逻辑的职业规划，都是靠谱的，区别仅在于风险大小。
至于计算机领域的、乃至其他各行各业的技术专家，这是一类我非常崇敬和羡慕的人群，他们往往已经获得了超额收益，故而不在我上述论证范围内。我所说的一切，仅仅针对你我这样的普通职员。
所以，程序员们，不要为自己掌握先进的知识而沾沾自喜，这个世界并不属于知识劳动者，所有利润最终将归属资本和权力……
……和猫。
树莓派3初体验之一：搭建 Python 开发环境
最近新买了一个树莓派3（购买前还考虑了 Orange Pi 等 Linux 开发板，但最终仍然选择了树莓派），主要目标是想通过折腾这个信用卡大小的 Linux 电脑，学习一下 Linux 系统知识，熟悉服务器的各项操作，顺便给自己搭建个 Web Server。
安装步骤很顺利，通过官网下载了 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 时候就遇到的问题，现在居然都想不起来了……
此时又遇到了第二个坑——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 的定时任务。
关于开发流程的一些体会
工作近5周，共完成了2个项目（第二个项目已经基本完成测试，准备收尾中）。第一个项目，是用爬虫抓取数据，然后做好 API 供用户使用。第二个项目，是扫描僵尸用户，发邮件唤醒，如未唤醒则关停僵尸用户的进程。
做这两个项目的过程中各有各的体会。
首先，是关于解决问题的方式。做第一个项目时，刚刚进入公司，很难适应工程师文化，加上和同事不熟悉，脸皮薄，不愿意问问题，甚至没有仔细确认需求和工程方式就动手开搞，最终耽误了不少时间。在工程上，沟通极为重要，工程师不是低着头闭门造车的，恰恰相反，工程师们是用集体合作的方式共同搭建一个或繁或简的系统，最终完成个体无法完成的大规模工程。这应该是工程师们在一起工作的最重要意义之一吧。
工程被分割成一张张工单，并不意味着其整体被切割成无关联的个体。在完成工作的时候需要尽可能多的理解工程的有机性。例如我将爬下来的时间序列存入数据库时，每条数据的时间都被我存成了str，于是在后期制作 API 的时候就遇到了一些问题，最后需要通过将其转成datetime来解决。类似的问题说明我在完成某件工作时，并不知道这件工作在工程中的位置与意义，这就需要多问和多做了，在对整体熟悉了以后，自然会逐渐清晰。
其次，是关于单元测试的重要性。其实『单元测试』这四个字，有弱化其意义的副作用。我在做第二个项目的时候，由于内部处理数据的逻辑比较复杂，导致大大小小的 Bug 一大堆，每次提交都认为自己已经做得差不多了，但还是在 code review 时被打脸，来来回回提交了若干次，花费大量时间，甚至同事成了我的人肉 Debug 处理器。最后同事说，你还是写一些测试用例吧，覆盖的情况越多越好。
果然，写了一百多行的测试用例后，将单元测试完成，自然发现了一些之前很难发现的 Bug，无论对我还是其他工程师来说，都节省了大量调试改错的时间，多灾多难的第二个任务也随之迎刃而解。经此一役，我对单元测试的意义恍然大悟，其实单元测试并不仅仅是『测试』这么简单。在『测试』的背后，其实是将代码化整为零、各个击破的写作过程，因此单元测试的写作时间，应当与程序本体同步，也即『写一个函数，就写一个测试』，二者几乎是同步完成的。这样看上去花了很多时间在设计测试用例上，其实是规范了自己的思路和代码，同时大大提高了后期的可维护性。
在明白了第二点（也就是单元测试的真正意义后），觉得自己仿佛突破了一个模糊边界——一个软件工程师和业余代码爱好者的界限。虽然现在代码依然很烂，但是本着对代码负责的态度和对自己职业的尊重，我会把以后写下来的所有代码都同步加上单元测试，配得上一个专业人士应有的严谨。
以上就是我在完成了两个项目后的些微体会。工程师的快乐，是由一个个微小的痛苦组成的。此生竟有幸成为工程师，真是一件幸福的事情。
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
关于这个问题，我还没有研究明白，还没搞懂到底哪些变量是这样传值的，算是一个小小的坑吧。
参考资料：
- http://stackoverflow.com/questions/8744113/python-list-by-value-not-by-reference
- https://docs.python.org/3/faq/programming.html#how-do-i-copy-an-object-in-python
几种排序算法的比较
整个十一假期就在折腾这几个算法，这篇总结性文章就是简要的介绍了几个基础算法的特性，并附带了 Python 的实现。
不同算法适合不同情况的数组，但在不知道输入规律的时候，使用时间复杂度低算法的比较保险。
Big O：上界
Big Ω：下界
Big Θ：确界
Big O 比较
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]
优化方案
- 如果某一次遍历没有发生数据交换，则代表已完成排序，可停止迭代。
- 记录遍历时最后一次数据交换的位置，后面的数据已经有序，因此可以缩小下次循环的范围。
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]
快速排序和归并排序使用分治法和递归进行排序，但快排在合并子数组后是自然有序的大数组；归并在合并阶段则繁琐一些，还要再次进行比较。
在对数组进行切分不平衡时，会导致性能低效（例如第一次从最小元素切分、第二次从第二小的元素切分……）。解决该问题，可以对数组进行随机排序，避免性能下降到极低。
优化
- 快排在小数组中比插入排序慢，因此在排序小数组时使用插入排序。
- 三取样切分。
- 熵最优排序[5]
以上三种优化是《Algorithms 4th》中对于快排性能的优化，都是对算法本身做了一些改进。而最著名的优化则是《算法导论》中提到的『随机化快速排序』，与上述三种性能优化有很大不同。
随机化快速排序，一般来说都是将取主元的过程随机化。随机化快速排序的『
知乎上一个用户对快排和随机快排的性能做了测试，
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 次比较和恒定的辅助空间。当空间紧张时（例如嵌入式），堆排序用几行代码就能实现实现较好性能。
缺点是无法利用缓存，缓存未命中的次数远高于大多数在相邻元素间比较的算法。
通过倍率实验预测程序的增长数量级
可以使用倍率实验来预测任意程序的增长数量级：
每次实验时使输入翻倍，计算时间，并求两次运行时间的比值。反复运行直到比值趋近于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
万用骰子脚本（跑团专用）
几个月前，我写过一个专门用来玩卡坦岛的命令行骰子工具，里面的骰子函数都是写死的，只能选2d6/2d10/3d4这几个，够用，但是不方便，适用性太差。最近入了《Pathfinder基础包》，准备重新开始跑团，看几个跑团QQ群里都有骰子机器人（方便大家开网团的时候投骰子），他们输入『.r 3d6』『.r 4d10』甚至『.r 1d97』这种实际中并不存在的骰子都可以得到值，自由度非常高。
于是我计划用Python来实现这种高自由度的骰子。首先遇到的问题就是如何让程序识别『3d6』『1d4』『1d8』这种跑团黑话。先普及一下，d4/d6/d8/d10/d20等都指骰子的面数，例如d4指的是四面骰，d20则指二十面骰，1d4指扔1个四面骰，2d6则指扔两个六面骰。普通游戏一般用不到这么多种类的骰子，而在以大量数值检定为核心的TRPG（桌面角色扮演游戏）中，这些骰子就不可或缺了。
首先想到的方法是用正则表达式来解析命令。以最常用的『1d6』为例，『1』指骰子个数，『6』是骰子类型（面数），『d』则是分割二者的分隔符。用正则表达式来写的话，应该是这样：
roll = input('> ')
match = re.search(r'(\d+)([Dd])(\d+)', roll)
先让用户输入命令，然后开始解析命令。命令的结构是『数字』+『D或d』+『数字』，正则表达式如上图。最早的版本里，是 r'(\d)([Dd])(\d)’ ，两个数字位都没『+』，后来发现第二个数字位必须带『+』（因为骰子类型有可能是两位数甚至三位数，例如1d20,1d100），于是我干脆把两个数字位都变成可以无限位取值的。
到此，解析命令完成。下一个问题发生在定义函数时的全局变量上。早期版本如下：
result = 0
def d(n):
result = randint(1, n)
函数外部出现了变量 result，函数内部又给 result 赋值，电脑就懵圈了。在这里，我一直没搞懂的问题是，定义函数时的返回值，并不是返回给某个变量，而是对应了这个函数本身。result = 0 这个变量的初始化也可以删掉。在朱老师的指导下，终于搞明白这个问题，于是代码顺利改成这样：
def d(n):
return randint(1, n)
最后，做好一个 for 循环来实现反复扔骰子的动作即可：
for i in range(m):
result = d(n)
dice.append(result)
print(result)
print('和为: ', sum(dice))
至此，其实还没有写完，脚本还有很多地方需要完善，但是已经不再是当初那个被朱老师批评的『到处给全局变量赋值的超级烂代码』了。日拱一卒，余欣慰也。
Github地址
欢迎各位去围观我写的其他小脚本，帮我改改这些超级烂代码！
完成《Flask Web Development》纪念
（上图为计划中的下一本书《Web Scraping with Python》）
这本 Flask 教材抱着啃了一个月，终于搞定了。标题里之所以说是『完成』而不是『学完』，是因为实际上我确实只是完成——所有的代码都手打了一遍。但是到底学没学会，对自己持悲观态度。这本书内容比较集中，但是细节很多，我又是第一次接触 web 框架甚至是第一次接触 web 开发，读完全书、打完全部代码，实际上也只是盲人摸象的对 web 开发有了大致印象，远远不能算『学会』。（Ps.本书中有若干小错，例如代码文件的路径等等，但是辨识后不影响学习。官方提供的代码有一些教材内的功能没有完成。）
不过我对这种感觉也并不陌生。在完成《笨方法学 Python》的时候，也有类似的体验，书中内容都学了，但合上书后并不知道自己能实现什么，深深的『啥都不会做』感，只是后面接触了更多的 Python 知识后，这种不安才慢慢消散。有了那一次的经验以后，我就不再担心这种『无力感』。相信这种感觉在短时间内可能还会重现多次，但并不代表我真的『啥都不会做』。
回顾一下从去年11月开始至今的学习，自己的速度并不快。学习过的书有：
- 《笨方法学 Python》
- 《Automate the boring stuff》
- 《Introducrion to HTTP》
- 《Flask Web Development》
除了笨方法以外，其余都是英文。所以读这些技术书，对自己的英文阅读也有一些帮助。从《Automate》一书开始，我习惯将原书 PDF 下载后通过淘宝打印。并且多亏了朱老师的全程指导，才能在转行程序员的道路上坚持走下去。
目前写过的一些小工具：
- 桌游《阿瓦隆》——基本使用 python 语法把规则写了一遍，当时完全不知道数据库，也不懂部署。
- 基金净值统计——用爬虫抓取自己的基金现价，然后计算目前自己的持仓市值
- 给基友用 pandas 做的数据处理脚本——这个代码最少，但是我最喜欢，因为解决了原本很麻烦的实际问题。
- 其他的都是一些跟着教程做出来的东西。
在 Python 的各个用途中，最让我感到神奇的是爬虫和数据处理，也是我曾经实现过的两个脚本的功能。爬虫可以自己阅读、解析、抓取、统计网络上的各种数据、甚至可以跨过 JS 像真实用户一样去操作页面；而 pandas/numpy 这些工具居然可以以远超过我想象的速度处理惊人的数据。我希望自己能够在这两方面加深一下学习。
后面我为自己规划的学习路径是这样的：
1、完成实验楼的 Flask 轻博客项目（已完成）
2、开发一个自己的网站（还没想好需求）
3、完成《Web Scraping with Python》
将这三个任务完成，目测应该已经起码到达八月中旬了。届时找一份 junior developer 的工作应该问题不大。如果在工作之余仍有时间学习，会继续在爬虫和数据处理方面钻研，然后看看自己更喜欢哪方面。
用 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 学习史的好几个第一次：
第一次现学现卖，当天下午就用陌生的知识完成任务。
第一次帮朋友解决了实际问题。
第一次完成了一件数据处理工作。
非常开心，非常值得纪念！