算法学习笔记(2):快排

前言:最近两天又改变了下学习方法。直接看《算法导论》,然后看完立刻实现感觉太直接,自己不需要动脑子,引导性也不是很强。于是去hackerrank上一点点学。昨天把warmup和implement完成了,熟悉了下大概环境。今天把插排和快排看完了。

网上之前一直流传的一个图书馆大妈给书排序的段子形象的解释了快排的思路。

图书馆看见两个志愿者需要把还回来的一堆书按顺序入架, 管理员大妈给他们教的时候说:『你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一边,然后剩下两堆继续这样整,这样排的快!』

从分治法的思维来看,快排和堆排的路数差不多。堆排中是假设左子树和右子树是已经排好了的树,而快排中则是假设左侧的序列和右侧的序列分别是排好了的序列。其实就是每次排序之前都能保证小的在左面,大的在右面。思路很简朴。

对比之下,由于堆排中使用了二叉树的结构,所以在排序这个事情上徒增了复杂度,所以导致了其比快排效率低。

过来人也都对这种『凡事不能搞得太复杂』的思想也有过阐述。

Everything should be made as simple as possible, but no simpler.

——爱因斯坦

万物之始,大道至简,衍化至繁。

——老子《道德经》

说回图书馆大妈的段子。毕竟图书馆大妈不是程序员,只能想到最简朴的快排的方法。事实上,在把书分成三摞(即『比Pivot小的一摞』、『Pivot一摞』、『比Pivot大的一摞』)的不停迭代的过程中,实际上是个把最初的一整摞书摊开的过程。形象的说就是原来一摞书撑死只占A4纸那么大的面积,然而摊开之后会占许多倍原来的面积。即段子中的排序实际上是会多占空间的。

对应的也有一种『原地快排』的算法,并不需要把书按着大小摊开,只需要把书从那一摞里『抽出来』再『塞回去』(对应着其实就是数组元素之间的互相调换)即可以完成排序。《算法导论》上杭也介绍的是这种快排方法。

这种原地快排的代码也不是很复杂,书上写的也很清晰。我觉得一个挺巧妙的地方是《算法导论》中使用两个下标来圈定了『大于Pivot的右侧子数组』。这样处理的时候很直观。

别的关于快排也并没有什么了,毕竟学的时候感觉一切都是那么顺理成章。又想起来小波课上老师说的,『一看都不对的结论肯定有问题』。

算法学习笔记(1)——堆排序

前记:最近回家除了干干所里剩下的活,手头剩了不少时间。于是趁着这个寒假比较长,准备把算法导论看完了。不过隔了很久突然看起,有些生疏,于是准备再实现一遍。选择语言秉承了「人生苦短,我用python」的原则,果断的选择了python。

虽然把代码提交到了github上,不过感觉不能看着书把伪代码翻译一遍就算完了,写完了之后好好感悟一下,记录一下自己的感想也是很重要的,于是准备在博客上大概记录下自己的学习笔记和感想。

所以重点不在于名词定义和原理解释,毕竟wiki上也好,书上也好,都是一翻到处都有。我想记下来的更多的还是自己个人在学习过程中觉得这些算法构思巧妙的地方。

第一天的复习内容是堆排序,我认为巧妙的地方有以下几点。

1.首先这里的堆使用的数据结构是二叉树,在顺序存储二叉树的时候,父节点、左子节点和右子节点的下标之间具有天然的简单倍数、邻近关系。这直接决定了在访问数据时,不需要很大的代价,客观上显著降低了复杂度。

访问各个节点的代码如下所示,为了简便并没有考虑下标越界的异常处理,这也是为了突出原理。用书上的话说就是:

数据抽象、模块化和错误处理等问题往往都被忽略掉了,以便更简练的表达算法的核心内容。

def get_parent(self, index):
	return self.heaplist[index/2+1]

def get_leftchild(self, index):
	return self.heaplist[2*index+1]

def get_rightchild(self, index):
	return self.heaplist[2*index+2]

2.其次,堆排序将一个复杂的工作分成了许多层次,即所谓的分治法(divide-and-conquer)。

逆向思考的话,就是将一个排序问题分解成了「提取最大元素」、「构建最大堆」、「使用两个最大堆一个节点组成一个最大堆」三个层次。

而如果正向思考的话,由于最大堆的最大的节点就是根节点,所以实际问题就变成了「如何将最小的元素都放在叶节点上」、「如何将根节点和某个叶节点交换之后,再次构建最大堆」两步。

虽然实际上使用的方法都是相同的,即从叶节点开始(由于是顺序存储结构,只需要从数组的中间开始倒序进行)构建最大堆,最后自然整个树会变成最大堆;而后将根节点拿出来(《算法导论》中是将根节点放到了数组末尾,由于放到数组末尾之后并不是二叉树的组成部分,其下标与其他节点的下标没有关系,实际就是放到了另一个数组里)。最后自然形成了一定的大小顺序。

从这种角度来看,其实这种排序方法与插排的思想差不多。就是依次为各个元素找到合适的位置,而由于在元素比较多的时候,第一次构建最大堆的时候,所有的元素形成了一定的有序性。所以一般堆排序比插排的效率要高,不过也不是很高,因为受到了算法设计思维(单个、依次操作)的限制。

实现的代码如下所示。

def max_heapify(self, i=0):
	l = 2*i+1
	r = 2*i+2
	if l <= self.length-1 and self.nodelist[l] > self.nodelist[i]:
		largest = l
	else:
		largest = i
	if r <= self.length-1 and self.nodelist[r] > self.nodelist[largest]:
		largest = r
	if largest != i:
		self.nodelist[i], self.nodelist[largest] = self.nodelist[largest], self.nodelist[i]
		self.max_heapify(largest)

def build_max_heap(self):
	for i in reversed(range(0, self.length-2-1)):
		self.max_heapify(i)

def heapsort(self):
	self.build_max_heap()
	for index in reversed(range(1, self.length)):
		self.sortlist.append(self.nodelist[0])
		self.nodelist[index], self.nodelist[0] = self.nodelist[0], self.nodelist[index]
		del self.nodelist[index]
		self.length = len(self.nodelist)
		self.max_heapify()
	self.nodelist = self.heaplist
	self.length = len(self.nodelist)

最终所有的代码在heapsort.py

夜色

最近宿舍里刮起了一阵摇滚风。

过去只听过唐朝的《梦回唐朝》和《国际歌》。在龙哥的推荐下,听了唐朝的《送别》。即使是送别作为主题,还是一如既往的大唐气象。歌词也超脱于《送别》许多,有《春江花月夜》的既视感,颇有些跳出时间、以词入哲的感觉。

于是挨个听唐朝的受欢迎的歌,找到了这首《夜色》。

这首歌被收录在一张合作专辑《告别的摇滚》里。这张专辑为了纪念去世的邓丽君,收录的歌曲也都是邓丽君的歌曲。不过专辑曲目的演唱者是一众玩摇滚的,其中就有唐朝。

《告别的摇滚》专辑封面

《告别的摇滚》专辑封面

虽然是一群玩摇滚的翻唱,不过这歌并不像上文提到的《送别》那样被打上了鲜明的摇滚印记,翻唱者们——除了臧天朔——将这首歌演绎的充满了硬汉柔情的感觉,无比浪漫。

前几天的时候去北京城里,晚上十点多回学校的时候从怀柔北火车站到学校还有一段夜路。这条夜路会路过学校旁边的不知名小村子,冬天的夜晚天寒地冻,村子里的路上并没有几个人,周围亦无灯光。

下车的时候余光就发现天空异常的干净,银河依稀可见。于是哼着《夜色》,心情愉悦的走完了那20分钟的夜路。

想起来初中的时候家里给买的天文望远镜,记得第一次看到满天银河的时候先是心生敬畏,而后便是强烈的快乐,无缘由的快乐。

也许我已经在城市里呆的太久,城市的夜灯红酒绿、五光十色,已经不能再称作夜了,只能当作另一种白天。在城市里的所谓「娱乐」更多的是一种机械的、物化的享受。或许第一次、第二次会感觉快乐,时间长了,就会心生厌倦;然而却像吸毒一样,抛弃这种「娱乐」之后,因为没有更好的替代品,会再度沉溺于城市。

离开人群,到更接近自然的地方,去看看真正的「夜」,换一种心境,也许能获得更自然、更长久的快乐。

Linux中读写i2c

最近因为种种原因,要在跑Linux Embedded的上位机中写一个程序,要有界面还要控制i2c和下位机通信。

于是回想起了本科的时候各种搓板子的「悲惨经历」,以及微机原理老师留的在嵌入式OS上随便跑点什么的课后大作业。预估了一下,估计这活挺难的。

不过好在最近一段时间一直在用Linux,或多或少的也了解了一些关于Linux的知识。发现在应用层写个控制i2c的程序实在是太简单啦!

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <linux/i2c-dev.h>
#include <linux/i2c.h>
#include "i2c.h"

int slave_read_byte(int fd, unsigned char addr, char* readByte)
{
    fd = ::open(I2CDEV, O_RDWR); //这里需要添加::,在global namespace中找到open函数,close同理。
    if(fd<0)
    {
        return 1;
    }
    if(ioctl(fd, I2C_SLAVE, addr) < 0)
    {
        return 1;
    }
    read(fd, readByte, 1);
    ::close(fd);
    return 0;
}

int slave_write_byte(int fd, unsigned char addr, char* value)
{
    fd = ::open(I2CDEV, O_RDWR);
    if(fd<0)
    {
        return 1;
    }
    if(ioctl(fd, I2C_SLAVE, addr) < 0)
    {
        return 1;
    }
    write(fd, value, 1);
    ::close(fd);
    return 0;
}

然后就ok了,剩下的就可以在pushbutton的slot里读写下位机之类的了。