笔记本

排序算法笔记

2016-01-23

最近在上MIT的6.006算法课,重新温习了下排序算法,发现很多知识点以前并没有吃透,也没有记下来,所以这次还是写在这里了。知之为知之,不知为不知嘛。

Insertion sort

核心

取出元素比较并插入到之前已经排好序的数组中。

例子

  1. [3 5 2 1]  # 取第二位5,比较第一3
  2. [3 5 2 1]  # 5 比 3 大, 略过
  3. [3 5 2 1]  # 取第三位2, 和第二位比较,2 比 5 小,2向前
  4. [3 2 5 1]  # 继续比较2 和 3, 2 比 3小,2向前
  5. [2 3 5 1]  # 1就重复上述步骤

代码

def insert_sort(a):
    for i in xrange(1, len(a)):
        v = a.pop(i)
        p = bisect.bisect(a[:i], v)
        a.insert(p, v)
    return a

Merge sort

核心

合并已经排好序的两个数组,哪个符合条件就添加到结果里。

合并时,对两个数组头元素作出对比,又称“两指合并”

例子

  1. [3 5] [2 1]  # 拆成两个数组,并给他们排序
  2. [3 5] [1 2]  
  3. R:[1]  Stack:[3 5] [2]  #两个数组里1 最小,添加到结果里
  4. R:[1 2]  Stack:[3 5]  # 继续比较2 和 3, 2 比 3小,2添加到结果里
  5. #就重复上述步骤

代码

def merge_sort(a):

    la = len(a)
    if la == 1:
        return a
    elif la == 2 and a[0] > a[1]:
        a[0], a[1] = a[1], a[0]
        return a
    else:
        left, right = merge_sort(a[:la/2]), merge_sort(a[la/2:])
        result = []

        while left and right:
            if left[0] < right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))

        if left:
            result += left
        if right:
            result += right

    return result

Quick sort

个人最喜欢的一个算法,简单,快速!但是对栈的调用较多~

核心

和MergeSort 很像,也是合并已经排好序的两个数组,但是是哪个符合条件就放入递归的qsort里。

可以说两个是一前一后。

代码

def qsort(a):

    la = len(a)
    if la <= 1:
        return a
    elif la == 2 and a[0] > a[1]:
        a[0], a[1] = a[1], a[0]
        return a
    else:
        lt, gt = [], []
        for x in a[1:]:
            if x > a[0]:
                gt.append(x)
            else:
                lt.append(x)
        return qsort(lt) + [a[0]] + qsort(gt)

Heap sort

核心

借助Heap(堆)的特性:最大/小的元素会在数组的头部,进行排序。

知识点

heap是一种由数组构成的特殊二叉树结构,具体在下面的思维导图里。

代码

def heap_sort(a):
    la = len(a)

    def heapify(start, end):
        father = start

        while True:
            child = father * 2 + 1
            if child > end:
                break
            if child + 1 <= end and a[child] < a[child+1]:
                child += 1
            if a[father] < a[child]:
                # swap
                a[father], a[child] = a[child], a[father]
                father = child
            else:
                break

    # la/2 -> 0
    for i in xrange((la-2)//2, -1, -1):
        heapify(i, la-1)

    # la -> 0
    for end in range(la-1, 0, -1):
        a[0], a[end] = a[end], a[0]
        heapify(0, end-1)
    return a

随机输入比较图

#数据结构与算法

2015年终总结

2015-12-28

终于又到了年末自我审查的时间了……今年就不填表了,我觉得我已经不需要这种东西来督促我学习了,毕竟目标很明确了。

今年在游戏公司算是扎下了根,带了一小段时间的后端团队(虽然只有一个成员),学到了怎么给他人做职业规划,教学,发展;也学到了不少职场上的事情。Golang也算是能信手拈来的程度了,但是对于高性能系统还是有些不知所措,比如内存池规划,TCP连接优化。架构上至少接触了点分布式的东西,但是还没有上手的感觉,毕竟需求并不是那么强烈,对于CAP、Paxos都只是停留在大致知道上,明年务必要实现过一次Paxos和raft才行。算法/数据结构上,今年简直就是LRU年,之前在Game Server里有用到,写了一个,然后跑到新团队发现,又缺一个,想着LRU反正不复杂,又写了一个……LeetCode重新捡了起来,刷了40多道而已,简单地学了些图论的东西,但是边上班边生活(其实都是些琐事,比如小区换出入证什么的)真的业余时间几乎就没有了,加上还要学车,简直快要把我给累垮了。幸好女友经常安慰,疏导我,其实对我来说,能有个人说说今天的烦恼,舒缓一下压力就已经足够,然而她给予我的更多,真的要感谢她。

今年只看了一本书--《网络游戏核心技术与实战》,讲得真得很细,对于架构上也是面面俱到,可惜,大裁员时顺手把书送给了同事,要不然,还得继续精读。

东西还是造了不少,可惜没有时间整理、总结:

参加了不少分享会,不过学到的并不多,以后看来得参加更加高端点的分享会。或者报个算法班来系统补补课?

年终总结

Bla -- another static blog app

2015-11-23

After 2 weeks working on my pet project, I'm glad to say that Bla is ready at the stage of MVP(minimum viable product).

Other highlights: 

Simple Tutorial

go get -u github.com/mengzhuo/bla/cmd/bla

bla new

edit your configure file "bla.config.json" and just run bla

Github repo:

github.com/mengzhuo/bla

某项目上线及事故总结

2015-10-19

EW4终于在中国iOS顺利上线了,虽然我已经被调到其他项目组,但是也经历了上线加班调试到4点的情况。所用的技术栈其实在招聘页面都有,所以不算泄密。

事故总是由看似无关紧要的小错误累积而成的。

整个系统架构上是一般的二代网游架构,大问题没啥,但是登入服务赶新潮地依赖了DynamoDB这个SLA号称在线率三个9的玩意。可是偏偏在正式上线前三天us east1的数据中心写故障!这时IT团队试图从us east1迁到us east2,顺利的迁移完了,结果再次中了彩票,east2也故障了!这简直是可以买彩票的节奏!!反正数据还没迁完,IT团队就再次修改了配置指向east1,由于此前迁移没有进行过演练,所有配置的更改都是手动操作的,所以有台负责处理连接的节点没有更新,埋下了祸根:这个节点不停地对登入节点上报错误的地址,但由于ELB的关系,这个错误在人工测试的阶段都没有察觉到。 这时,悄然开服的消息已经传遍了骨灰玩家圈,玩家纷纷开始登入注册。

大概是下午开始,客服陆续收到玩家投诉说丢档了!但错误收集sentry并没有报告什么异常,顿时我就纳闷了,难道是DynamoDB又出了问题?但,这次,并不是,只好继续排查代码上的问题。一波未平一波又起,之前给各个安卓运营商上线之后一直正常,但是现在某运营商那边的玩家投诉无法登入,美国上线的负责人也表示自己无法登入,这时整个团队都非常沮丧,因为错误收集系统压根就没有错误报告。IT团队开始一遍又一遍地切换DynamoDB的数据库、登入服务的配置来查错,这时已经是凌晨4点了,估计因为在线人数下降了,ELB自动分配到了一台机子上,所有人又能正常登入了。王总提出让一部分人休息,明天好继续排错,所以我回家休息了。 结果第二天来时,美国团队的人通过debug 客户端,发现本来该指向US的节点,竟然给出了中国区的服务器地址!大家顿时恍然大悟,有台机子在上报错误的地址!!于是IT团队用昨晚写好的部署程序,重新部署了所有大区服务,登入问题就都解决了。 接下来就是无法下载的问题,客户端的同事发现是更新用的服务下载到了不同的数据更新包导致的,不过所幸只是一个小国的部分用户…… 这次事故,其实说实话是完全可以避免的。

p.s.通过这次排查代码,我发现系统里还有不少因为加新功能而加的补丁,重构看来也是不可避免了。