Fork me on GitHub
Google

更好地 partition array

很多算法或者题目里面都有 partition array 这步。所谓 partition array,指的就是把元素按某种条件分开,一部分放前面,另一部分放后面。

比如快速排序,这个条件就是“元素是否小于 pivot”,小于放前面,大于放后面。

大部分人写快排,其中 partition 的一步都喜欢这么写:

def partition(alist, first, last):
    pivot = alist[first]

    left = first + 1
    right = last

    while left <= right:
        while left <= right and alist[left] <= pivote:
            left += 1

        while left <= right and alist[right] >= pivot:
            right += 1

        if left <= right:
            alist[left], alist[right] = alist[right], alist[left]
            left += 1
            right -= 1

    alist[first], alist[right] = alist[right], alist[first]
    return right

弄两根指针 left, right 分别放在 array 的左端和右端,然后 left 右移,right 左移,如果能交换就交换元素,直到 left > right

上面是一个比较标准的 partition 实现,也有一些变体,不过凡是使用 left/right 指针的都是一类。这类实现当然没有问题,但是不优雅,而且难记。

哪里不优雅?仔细看就会发现,代码里有 4 次 left <= right 的判断!而且这 4 次都是必要的。

为什么难记?因为代码多,所以难记!而且稍不注意,最后一步就会写成 alist[first], alist[left] = alist[left], alist[first]

优雅的写法是什么呢?

def partition(alist, first, last):
    pivot = alist[first]        
    i = first

    for j in range(first + 1, last):
        if alist[j] <= pivot:
            i += 1
            alist[i], alist[j] = alist[j], alist[i]

    alist[first], alist[i] = alist[i], alist[first]
    return i

短了这么多,更重要的是再也没有重复的 left <= right 判断了!这段代码也很好理解,j 指针把 array 扫一遍,把 <= pivot 的放到前面,i 用来记录放的地方。停止的时候,i 的位置是 <= pivot 部分的最后一个元素的 index。当然,不要忘记把 pivot 和这个元素交换。

需要注意的地方有两个,首先是初始化:i = first, j = first + 1。还有,每次是先 i += 1,然后再交换i, j元素。

其实这种区别不仅仅在于快排,所有 partition array 都是一样。比如这题:

给出一个整数数组nums和一个整数k。划分数组(即移动数组nums中的元素),使得:

所有小于k的元素移到左边
所有大于等于k的元素移到右边

不优雅的写法这么写:

int partitionArray(vector<int> &nums, int k) {
    int i = 0, j = nums.size() - 1;
    while (i <= j) {
        while (i <= j && nums[i] < k) i++;
        while (i <= j && nums[j] >= k) j--;
        if (i <= j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

还是 4 次比较╮(╯▽╰)╭

优雅的写法:

def partitionArray(nums):        
    i = -1

    for j in range(len(nums)):
        if nums[j] < k:
            i = i + 1
            nums[i], nums[j] = nums[j], nums[i]

当然拿Py和C++比是不合适的,但关键是少了 4 次比较,代码就好看多了。
这一题不存在真实的 pivot,所以我们对快排做了改进,初始化时 i 不再是 0,而是 -1。快排的时候,因为第一次交换时 i = first + 1,所以初始化 i=first 实际上跳过了 pivot 也就是 array[first]。这里因为没有需要跳过的元素,所以 i=-1,然后 j 还是等于 i + 1 也就是 0。其它的没有区别。

熟悉没有真实 pivot 的写法之后,不论按何种规则划分,都只改一行就可以。
比如按照奇偶划分:

def partitionArray(self, nums):
    n = len(nums)
    i = -1

    for j in range(n):
        if nums[j] % 2 == 1:  # changed this line
            i = i + 1
            nums[i], nums[j] = nums[j], nums[i]

其实到这里本来是写完了,但是那天和同学吃饭的时候聊天,又让我意识到优雅写法不光只是优雅而已,有时候只能用它。同学出这题考我:

单链表排序能不能用快排?

我想了想,没有不能用的理由吧,就说能用。他说,不行,因为是单链表,所以不能用快排。我没反应过来,就问为什么单链表不能用快排?他很不解我居然提出这个问题,说你要移动左右两个指针啊,但是单链表你没法把右边的指针往左移动,所以没法用快排。

于是我瞬间懂了,他只知道快排可以用左右指针来写,却不知道另一种写法。原本我只是觉得第二种写法更优雅,没想到在不知道的情况下,居然会误认为单链表没法用快排。

不只是更优雅,而是更好。

Google

PyCon2015 笔记

原本是知乎上的一个答案,现在挪到博客里来。

1. Type Hints - Guido van Rossum

视频:https://www.youtube.com/watch?v=2wDvzy6Hgxg
主要就是讲 PEP 484 - Type Hints,通过 typing 这个模块,从 3.5 版本开始,Python 也可以做静态检查了!

2. Raymond Hettinger - Beyond PEP 8 -- Best practices for beautiful intelligible code

视频:https://www.youtube.com/watch?v=wf-BqAjZb8M
强烈推荐!Raymond Hettinger 的演讲适合所有层次的程序员看。这个演讲说的是,我们都知道 PEP8 来规划 Python 代码,但是这样是否就够了呢?我们可能忽视了一件更重要的事:Pythonic!这个演讲举了几个例子,怎么 make code more pythonic,比如使用 context manager,使用 @property,使用 Adapter 包装已有代码让 import 更简洁。不过其中最神的我觉得还是通过定义 __len____getitem__ 来构造一个 sequence,然后这个 sequence 自动就是 iterable 的,之前我一直以为必须通过定义 __iter____next__ 方法构造 iterator 才能达到让类支持 for in 的效果。
这个演讲没有 slide,不过代码不多。

3. David Beazley - Modules and Packages: Live and Let Die!

视频:https://www.youtube.com/watch?v=0oTh1CXRaQ0
Slide: http://www.dabeaz.com/modulepackage/ModulePackage.pdf
代码:dabeaz/modulepackage · GitHub
David Beazley 以前的视频我也看过几个,他的演讲最大特点就是 mind-blowing,会在短时间内让你意识到你根本就不会 Python! 如果有人能在不查资料的情况下理解他的演讲的50%内容,那这个人绝对是 Python 高手。这次的视频也是一如既往的烧脑,讲的是和 import 相关的各种知识,因为之前写 ezcf 的缘故这次终于能看懂稍微多一点。。。实在不想介绍了,各位可以自己去看。
之前有人问 Python 里有哪些黑魔法。那个问题我没有答,我只想说 David Beazley 的每一个演讲都充斥着黑魔法。。。

4. Dan Crosta - Good Test, Bad Test

视频:https://www.youtube.com/watch?v=RfR_QRoNZxo
Slide:https://speakerdeck.com/dcrosta/good-test-bad-test
文章:http://late.am/post/2015/04/20/good-test-bad-test.html
关于测试质量的演讲,重点讲述了三个测试的误区:
(1) 过分追求 100% 覆盖率。他认为有些代码反而应该尽量避免去测试,比如依赖于网络上某个服务的代码。
(2) 使用过多 assert。他的建议是一个 test function 里面最好只有一个 assert。
(3) Mock 一定会让测试更好。在测试中用到了数据库,与其直接 mock 一个返回值,不如用简单的代码模拟数据库的工作流程。
第二条我觉得像只用一个 assert 在很多情况下并不方便,但是把 dict 的 assert 拆分成多个键值 assert 还是可以借鉴的。关于数据库的 mock,其实有很多工具可以使用,比如见过一个专门用来为单元测试生成假数据的第三方库,还有 Django 的测试自带测试数据库。

Google

你将度过怎样的大学四年?

今天这篇文章我很久之前就想写了,但是不太敢写。时至今日毕业已将近两年,下定决心还是写出来,不然时间久了难免淡忘。虽然题目是个问句,但其实个人早就有结论了。更准确的题目应该是:哪些因素决定了一个人的大学四年会怎样度过。我的结论是这样的:

30%自身 + 30%专业 + 10%室友 + 10%偶然因素

这里的百分数其实不用深究,它只是大概反映了每一个因素在我看来有多大影响。没有列上去的,也未必就没有影响。分条来说一说。

自身

进了大学靠自己,这是大家都知道的道理,但这里说的“自身”其实并不单单指“个人努力的意愿”。这里的自身实际上说的是一个人的属性,就是你是什么样的人。个人感觉,进入高中,人的各种特点变得逐渐稳定,进入大学则基本固定。回想起来,周边熟悉的同学基本也是如此,大一什么样,大四什么样。那么人有哪些特质呢?太多了,但对大学生活来说,影响最大的还是两个东西:兴趣、智商。大学无疑是一生中最自由的阶段,摆脱了高中成天刷题的日子,又还没有进入必须要为生活挣钱乃至养家糊口的阶段,有大把时间可以做自己想做的事。除了上课和完成作业,你做什么完全看自己的兴趣。至于智商,它会影响你做的每一件事,并且不光是做这件事本身,还包括对事情的计划。想把课程学好,智商也是必不可少的。我就属于智商捉急的那一类,基本从来没有在课堂上完全弄懂老师讲的内容,考试又想不出题目的做法,非常悲惨。当然还有很多别的因素,比如是否愿意和人接触决定了你的交际面,是否够帅/漂亮/有钱影响你是否能找到男/女朋友,总之自身属性是大学四年真正的决定性因素。

专业

专业太重要了。如果你有转专业的想法,那就果断转。在不适合自己的专业里呆着,会让人痛不欲生。这方面我依然是反面教材。高考选专业,谁 TM 知道哪个专业干嘛啊,所以就听父母的了。我从来不责怪他们,正是因为我自己没有在高中找到方向,才把选择权丢给了他们。大学里的大部分时间我都过得不爽,因为学的东西不感兴趣,也学不懂。直到大二下学期,一个很偶然的机会,我才意识到自己更喜欢计算机,从此就踏上了成为码农这条路。我无数次地想,如果一开始我就去了计算机系,现在到底过着怎样的生活。

前面说到兴趣是很重要的自身属性,如果专业能符合兴趣,那是最好不过的事了。我认识的转专业的人,有从电子去生物的,有从计算机去学医的,有从精密仪器去自动化的,之后全都过得很开心,因为他们终于可以享受学习了。但中国的大学有一个矛盾,除了浙大,别的学校都不可能让你先呆一年再选专业,但是不了解一个专业,又怎么知道自己感不感兴趣呢?所以要么在高中就明确方向,要么去浙大,要么出国,否则在专业选择上后悔的可能性极大。

室友

这是一个让我不知道该从何说起的话题。什么才是好的室友,个人有个人的标准,所以这个问题并不好讨论。不过我相信所有上过大学的人都会认同室友对自己的影响有多大。如果你拥有了你心目中的“好室友”,请感谢上天。

偶然因素

我曾经是学校推理协会的会长。我们这个协会是怎么成立的呢?某一天,同学 A 和同学 B 在学校书店相遇了。当时,那个书店有专门的一个书架放推理小说,而他们发现对方也在看推理小说,就聊了起来。这两人的相遇是学校推理协会成立的契机,之后他们找到了一些志同道合的人,成立了协会,而我则是第一时间加入的会员。之后我逐渐做到了会长,把学习之外的大部分时间都奉献给了协会。So,如果他们当时擦肩而过了,会怎么样呢?也许,我们学校到今天都没有推理协会,也许有,但是我肯定不会是其中一员,更不会成为会长。如果我没有加入协会,那么我又会去做些什么呢?谁都不知道。蝴蝶效应是真实存在的,这也是生活有意思的地方。


top