Oct 15
1、插入排序

描述

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

代码实现

Python

def insert_sort(lists):

    # 插入排序

    count = len(lists)

    for i in range(1, count):

        key = lists[i]

        j = i - 1

        while j >= 0:

            if lists[j] > key:

                lists[j + 1] = lists[j]

                lists[j] = key

            j -= 1

    return lists


2、希尔排序

描述

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

代码实现

Python

def shell_sort(lists):

    # 希尔排序

    count = len(lists)

    step = 2

    group = count / step

    while group > 0:

        for i in range(0, group):

            j = i + group

            while j < count:

                k = j - group

                key = lists[j]

                while k >= 0:

                    if lists[k] > key:

                        lists[k + group] = lists[k]

                        lists[k] = key

                    k -= group

                j += group

        group /= step

    return lists


3、冒泡排序

描述

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

代码实现

Python

def bubble_sort(lists):

    # 冒泡排序

    count = len(lists)

    for i in range(0, count):

        for j in range(i + 1, count):

            if lists[i] > lists[j]:

                lists[i], lists[j] = lists[j], lists[i]

    return lists

4、快速排序

描述

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

代码实现

Python

def quick_sort(lists, left, right):

    # 快速排序

    if left >= right:

        return lists

    key = lists[left]

    low = left

    high = right

    while left < right:

        while left < right and lists[right] >= key:

            right -= 1

        lists[left] = lists[right]

        while left < right and lists[left] <= key:

            left += 1

        lists[right] = lists[left]

    lists[right] = key

    quick_sort(lists, low, left - 1)

    quick_sort(lists, left + 1, high)

    return lists

5、直接选择排序

描述

基本思想:第1趟,在待排序记录r1 ~ r[n]中选出最小的记录,将它与r1交换;第2趟,在待排序记录r2 ~ r[n]中选出最小的记录,将它与r2交换;以此类推,第i趟在待排序记录r[i] ~ r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

代码实现

Python

def select_sort(lists):

    # 选择排序

    count = len(lists)

    for i in range(0, count):

        min = i

        for j in range(i + 1, count):

            if lists[min] > lists[j]:

                min = j

        lists[min], lists[i] = lists[i], lists[min]

    return lists

6、堆排序

描述

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

代码实现

Python

def adjust_heap(lists, i, size):

    lchild = 2 * i + 1

    rchild = 2 * i + 2

    max = i

    if i < size / 2:

        if lchild < size and lists[lchild] > lists[max]:

            max = lchild

        if rchild < size and lists[rchild] > lists[max]:

            max = rchild

        if max != i:

            lists[max], lists[i] = lists[i], lists[max]

            adjust_heap(lists, max, size)



def build_heap(lists, size):

    for i in range(0, (size/2))[::-1]:

        adjust_heap(lists, i, size)



def heap_sort(lists):

    size = len(lists)

    build_heap(lists, size)

    for i in range(0, size)[::-1]:

        lists[0], lists[i] = lists[i], lists[0]

        adjust_heap(lists, 0, i)

7、归并排序

描述

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

代码实现

Python


def merge(left, right):

    i, j = 0, 0

    result = []

    while i < len(left) and j < len(right):

        if left[i] <= right[j]:

            result.append(left[i])

            i += 1

        else:

            result.append(right[j])

            j += 1

    result += left[i:]

    result += right[j:]

    return result



def merge_sort(lists):

    # 归并排序

    if len(lists) <= 1:

        return lists

    num = len(lists) / 2

    left = merge_sort(lists[:num])

    right = merge_sort(lists[num:])

    return merge(left, right)

8、基数排序

描述

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

代码实现

Python


import math

def radix_sort(lists, radix=10):

    k = int(math.ceil(math.log(max(lists), radix)))

    bucket = [[] for i in range(radix)]

    for i in range(1, k+1):

        for j in lists:

            bucket[j/(radix**(i-1)) % (radix**i)].append(j)

        del lists[:]

        for z in bucket:

            lists += z

            del z[:]

    return lists

Oct 15

读而思

天道酬勤是很多人知道的道理,“勤”的重点在哪里?农民很勤,工人很勤劳,但他们仍然是社会的底层。一些创业者每日披星戴月,依然没有摆脱失败的命运。在这里我们必须反思,一个成功的创业者或者公司员工,辛苦的体力只能带给你基本的温饱,如何获得更大的社会认可和上级认可是你必须要面对的问题。

天道不一定酬勤,深度思考比勤奋工作更重要。

我要讲一个故事。我在2003年就认识了雷军。在2010年投资小米之前,我们两个有大约六七年作为朋友的交往经历。这个故事我忘记是发生在哪一年,也许是在2007年,也许是在2006年,也许是在2008年。

有一次,我忘记是什么原因,雷军给我打了一个电话他说:“我一直认为你做投资是有自己的独到之处,你能告诉我,到底怎么样才能做一个成功的投资者?你为什么投资能做得非常不错呢?”

我当时给了他一个答案,“我相信我极其的勤奋。我相信天道一定能酬勤!我相信如果勤奋的话,你一定能做一个非常好的投资者。”我本来以为这个答案至少能得到雷军的部分认同,结果我没想到,他给了我一个让人惊讶的反馈。这个答案就是天道并非一定酬勤。

这个观点当时给了我非常大的刺激。我后来慢慢明白了,可能勤奋是必要的,但是勤奋是远远不够的。

这件体悟,也许我可以和大家分享另外一个有趣故事,是一本书。这本书豆瓣上可以找得到,叫《异类》。在豆瓣的书评里,有这样一段介绍:在《异类》一书中,作家格拉德威尔对社会中那些成功人士进行的分析,让读者看到了一连串颇感意外的统计结果:英超联赛大部分球员都在9月至11月出生;比尔·盖茨和史蒂夫·乔布斯都出生在1955年;纽约很多着名律师事务所的开创者竟然都是犹太人后裔,并且他们的祖辈大多是在纽约的服装行业谋生。

blob.png


为什么会有这些奇怪的统计结果?

我可以给大家再提供几个例子。我昨天上网又查了几个:富豪榜里有几个成功的创业者,我给大家报一报年龄啊。李彦宏1968年11月出生,雷军1969年12月出生,周鸿祎1970年10月份出生,丁磊1971年10月出生,马化腾1971年10月出生的。稍微不一样点,马云1964年10月出生。

我再给大家一个例子,我是中欧98级的。98级中欧的毕业生很有意思。我回中欧的时候,听到这样一个笑话。很多同学和老师说,你们98级的毕业生,是不是有什么特殊的基因。你看,你们班上做风险投资的特别多,比如刘芹,比如石建明,比如红杉资本的计越,CDH的陈文江,还在中国文化创业基金的陈杭。比我们再高一级是97级的也有几位。


为什么都是97或者98级的呢?是我们的基因有什么特殊之处吗?我想和大家分享的最重要的一点是,其实有时候光有勤奋是不靠谱的。机遇很重要。但是作为创业者,机遇是很难捕捉的,重要的是你要去发现这个机遇。


其实乔布斯和比尔盖茨都是1955年出生的原因,在他们大学毕业和辍业的时候,PC行业刚刚开始。为什么PC互联网的创业者1969年,1970年,1971年这个年龄群最多,是因为刚好互联网热潮,是他们刚好那一年参加工作两年到三年。你太早毕业了,像雷军是软件的这一代,他已经被他的“金山软件”给缠住了。你太晚出生,你还在大学里面,你根本没有机会去思考创业的机遇。


我1998年从中欧毕业,紧接着1999年刚好互联网浪潮爆出。不是因为我多么聪明,不是因为我多勤奋,因此机遇更重要。但是机遇不是运气,机遇是你对创业环境趋势的深度思考。深度思考要比你的勤奋更重要!只是绝大部分的机遇只是被动的被利用起来。只有少部分创业者是主动的去判断和捕捉机会。这是我和大家分享的另外一个观点“天道不一定酬勤!深度思考比勤奋工作更重要!”


孤独,是每一个创业者与生俱来的。


做公司早期创始人是非常困难的。因为你面对员工的时候,很难向他去解释,公司可能只有三个月发工资的钱,甚至三个月之后发工资的钱从哪里来,我都不知道。你无法和他们去分享这个事实。你同时还得和他们讲,你在干一件非常伟大的事情。而事实上,你连明天干什么都不知道。


第二,你也无法和你的投资人去分享这件事。因为并不是所有的投资人,都有勇气去听到真实的现状。你也无法站在聚光灯下,向媒体去分享你的创业故事。你讲的都是你的光鲜亮丽,而事实上,你的压力无法得到分担。


这种孤独是一个创业者与生俱来的。而且越是成功的创业者,在工作上孤独感更大。为什么?如果你不成功,你可能失败了以后换一个办公室,两年时间干一番新的事业。如果你成功了,你被成功所累,你有了光环。人人都认为你应该继续更成功。这种光环使得你的孤独感更强。


所以投资人的认同,以及让创业者放下这种所谓的包袱,是创业者本质上最需要的。其实投资者给你投一档钱,这不重要。投一档钱真的是因为跟你投缘,是对你的认同。


只是投资者把这种认同,用一个实实在在的,三个月之后要发的工资这笔账送给他们。因此,你看那些真的很优秀的投资者,他们内心深处是极其尊重创业者的。


他们从内心深处明白,他们之间的位置,不是一个居高临下的俯视态度,他们是平等的,甚至是创业者拥有更高的位置。因此,你作为一个创业者,真正需要找到的是能够认同你的投资人,而不应该是一张支票。我是一个什么都不是的人,但是我热爱创业。我知道怎么能够帮助中国的创业者获得成功,这是真正的财富。这是主流社会真正价值的所在。所以,认同是极其重要的一点。创业需要有价值的东西。


伟大创业者的灵感来自于一些你所忽略的细节。


在座的各位,可能听过我在其他地方的演讲。我曾经提到,创业最重要的愿景,要回答三个关键性的很“虚”的问题。“我是谁?我从哪里来?我向哪里去?”


但是我想今天我不展开讲其他问题。今天我想专攻一点,这三个问题其实一点都不虚一点都不空一点都不大。因为我们最关键的问题都是从蛛丝马迹的核心细节所捕捉出来的。所以要小中见大。


我给大家分享一两个例子。在2007决定投资UCweb,很多人不理解你为什么要投资UCweb这个手机浏览器。因为它有价值。它在浏览器上面放了一个所谓的分类导航目录,就是所谓的网站导航。


我想不出来,为什么在美国,是雅虎首先出现——这是一个人工分类的导航列表——而后谷歌出现,把整个的雅虎价值给打没了。但在中国,却是先有了百度,但是很多年以后,才出现了一个叫hao123的导航页,为什么?


我觉得这是一个很有意思的现象。雅虎一个最原始的人工分类列表,曾经极大规模地推动美国互联网发展。而被谷歌这样一个搜索引擎公司轻而易举地取代了。而在中国,我们一直强调中国有叫“后发优势”,我们却是在百度搜索引擎出现后,为什么又会出现一个人工分类的hao123?


这就存在一个非常非常有意思的核心细节。这说明在中国我们有大量的网民,是不知道怎么用拼音的,不知道怎么用键盘的,甚至是不知道怎么用搜索引擎的。拉丁字母打一个字做搜索非常简单,而中国用拼音写汉字输入到搜索框是很困难的。


这说明,第一,流量在互联网里是很核心;第二,流量的实现不一定纯粹是中国照搬美国。


2007年,没有安卓,没有iPhone。2007年,是塞班的时代。塞班的特点,是用手机键盘输入汉字,更加痛苦。用手机键盘,要去按住搜索框更加痛苦。所以我们发现我们的答案很简单,UCweb在2007年塞班的无线互联网时代是流量聚合核心。


这就是我们2007年投资UCweb最核心的一个观点。这个决策的核心点,来自于我们对hao123一个不起眼的现象的思考。所以我想在这里讲到,作为一个创业者,当你在规划你的创业愿景的时候,不要去捕捉一些概念,要去理解你的核心市场的那些核心细节。小中见大。很多伟大的创业者的灵感是来自于一些你所忽略的细节,一些蛛丝马迹的细节隐藏了大量的有益的洞察力。


洞见力是你有一个愿景的源发点。我看到了很多优秀的创业者,无论是周鸿祎,雷军,马化腾,他们所有都有着极强的洞察力。这些洞察力全是来源于被常人所忽略的蛛丝马迹中所捕捉到。


blob.png


三人行,必有我师,更重要的是与谁行?

“三人行,必有我师。”其实我想大家都懂的。但是实际上“三人行,必有我师”里面最关键的是:你跟谁在一起往前走。


我为什么想提这一点?因为在早期的时候,我们一般谈创业都说,我们多看看你的团队,你的团队执行力,团队的重要。


到底怎么来判断一个团队?有很多人都在问我,我曾经和有的朋友谈过。我说:“我看你娶什么样的老婆,我看你找什么样的女朋友。”其实这里面有一个很重要的一点在于你跟什么人交往,决定了你的优秀程度。


什么样的人是你的创业的合作伙伴,决定了你的创业团队的quality。 “三人行,必有我师。”我们要学会跟身边的人去学习他们身上的闪光点。


我在自己创业的过程中,和我那些投资了很多年的创始人,我从他们身上学到了很多东西。那么在今天如果我不考虑创业,你在组队的时候,你是愿意组一群你很容易说服和崇拜你的人做你的创业团队,还是尽可能找甚至比你还要优秀的能够扶持你创业的?


其实我们判断一个创业者是否有优秀的团队能力,其实就是看你和什么样的人在一起交往。


所以三人行,必有我师。更重要的是与谁行!小米创始人雷军在业内赫赫有名。他在2010年和我谈时说,他想建立一个不一样的创业公司,“我想把我的股权大量分散出去,因为我需要足够多的,尽可能的多的,足够优秀的人。我们小米前十个月没干事,只干一件事:找人。”


其实很多人觉得找人很难,其实首先要问问你,你是不是深刻地认识到,“三人行,必有我师。”谁做你的老师。人人都做你的老师,你跟谁行?所以在这件事情上,第一点,你要尽可能的找到你能够得到最优秀的,而且优秀程度决定了你团队有多优秀。而不是你如果足够优秀,你要找比你差的,这是很多创业者愿意去找一些容易被说服的比较普通的人的误区。


很多人说,我搞不定那些优秀的人。我同意,搞定优秀的人很难。但是这是我送给大家的另外一句话,“领导力来源于不偏不倚的自我认知、空杯心态和知行合一。”在这一点上,其实很多人认为领导的魅力,来自于你的成就,你的名气。我认为都不是。


真正的领导力,首先你要领导一个团队,你要领导自己。你要做一个公正与公平的领袖和领导者,你首先要对自己公平公正。不偏不倚的自我认知,是一个极难的事情。


所以到今天,我从不认为我是一个成功的投资者。我只愿意说,我是一个很热爱投资和创业的投资者。好的不偏不倚的自我认知,不但看清自己,也不看高自己。当你对自己不偏不倚非常诚实的时候,你会发现你身边的人都聚到你身边。因为他们认识到你是一个值得信赖的领袖。


第二,空杯心态。对于很多优秀的成功商人,特别有想法的创业者不是靠你声音大,是要学会能够放下能够倾听,聆听是比什么都重要的素质和能力。要学会坦荡,简单。所以对于一些优秀的团队,最好的管理是不管理!不管理的意思是说让他们变成自驱动的团队,每个人都能很好的管理自己。高效的团队来自于自驱动,而不是来自于KPI指标。


第三,怎么做到“守正出奇”?做减法是一个创业公司最重要的素质。很多时候,特别在互联网行业,追求极致。互联网是一个以点概面的行业。互联网是一个口碑点可以改变整个行业格局的地方。把公司所有的资源,赌在最核心的点上,是极其难的一件事。这是我讲的最后一点。


其实互联网是一个每天都会出现颠覆与创新的地方。每天都有很多创新的想法,但是我也想讲,现在互联网行业里面我看到很多优秀的人没有办法做成大事。原因是因为他们奇兵不断,怎么能够做到守正出奇是一件极难的事。


怎么能够做到守正出奇,这是我与周鸿祎交往时,所观察到的。周鸿祎是个有争议的人,但他在互联网流量这个理解上,是极其深刻的,他以前也是做流氓软件的。他反思了什么才能回到一个守正出奇的状况。


我想我今天不展开,只希望大家思考比较一下,在奇虎之前的周鸿祎,和奇虎之后的周鸿祎是不一样的。我觉得什么叫守正出奇,是互联网行业里面很重要的一个因素。


在座有很多年轻的创业者,你们都非常有创造力,但是怎么能够把你们的创造力放在一个更抢眼的位置。


首先最重要的一点做产品,而不要做生意。不要只做流量的转换收入,而不做核心用户价值。好的公司都是能够创造真正的长期价值。很多人说,小米手机就是一个会炒作的公司,会做营销的公司。有几个人真正理解,小米是这么具有极客精神的公司?


他把市场上所有资源,想办法提供给用户,最好的价值,最好的性价比,最好的体验。他创造的粉丝,和他的产品分不开。所以守正出奇,是互联网行业创业里面很重要的一个点。


创业的三个关键问题


我们在选择投资机会的时候,更看重优秀的创业者,除此之外还会考虑三个关键问题:这事儿是不是足够大;是不是抓住了一个正确时机,切入到一个趋势性的机会;这个公司长期来说能不能形成护城河效应。


第一个关键问题,这事儿是不是足够大,如果今天创业,你选择这个方向,应该问问自己,有没有发展空间,同时你有没有野心。


无论你是做1千万人民币的退出,还是做100亿美元的退出,基本要花6-8年(我们基本上平均投一家企业要经历6-8年时间)。而创始人把一个公司做起来,所投入的时间精力也是一样的,面临的问题和痛苦也相同。既然同样的时间退出,为什么不去选择一些足够大的机会?


第二个问题,是不是抓住了一个正确时机,切入到一个趋势性的机会?时机比选择方向更难,踩对点非常重要。


时机太早,这个市场机会没到,你会发现你很痛苦。90%的失败公司都不是方向、体量的问题,可能绝大部分都是时机太早的问题。领先市场3步、5步,市场还没起来,你就撑不下去了。不能领先太早,最好领先0.5步。太晚当然也不行,市场如果很热,通常意味着红海了,时机已经晚了。


最后一个关键问题,是否能够可持续发展,长期下来能形成竞争壁垒。好的商业模式、好的公司,时间是朋友,意思是说随着时间的推移,你的竞争壁垒越来越高,护城河越来越强,这就是可此续发展。


创业者应该有杀手气质、传教士能力


创业者要具备两个核心能力:一个叫以身作则的犀利杀手气质;另一个是你有传教士能力,能聚一帮牛人。

blob.png



杀手的气质。解决公司业务发展中的短板,就跟打仗一样,你要拿下这个山头,就要有在百万军中取上将首级的能力。公司的发展是长板和短板理论,什么短补什么,所以创业者最重要的能力是杀手气质,还有补短板的能力。你得不停的变,缺什么都能自己顶上,也许不一定能做的最好,但是你要有从0到1解决短板的能力,虽然你不专业,但你永远是那个冲在第一线的。


传教士是什么?就是深入思考和能影响到什么样优秀的人跟你一起的能力。传教士传教一定是你不信我的时候我来传。所以你身边聚一群什么样的人,基本就能衡量你的理念。如果你下面的人,每个都是很有想法的人,那一定是你的想法比他们都大,能把他们震住,你就能取得1+1大于2极强的成功。 雷军就是其中的佼佼者。


总而言之,创业者要有这两个能力:一是在0到1的时候,一定要有以身作则的,把公司的短板补掉,迅速把业务往前推进极强的执行能力。二是有传教士能力和魅力。你的魅力源头是来自于你的理念。两者缺一不可,特立独行的孤胆英雄,在今天很难成功。

May 23
转自:http://blog.jobbole.com/93905/[img]
"hello world"它是最著名的程序。对于每个程序员来说,它几乎被认为是每种程序设计语言的第一个例子,那么这条消息是从哪里来的呢?
作为一个功能,计算机程序简单地告诉计算机显示“Hello, World!”。传统上,它是开发者用来测试系统的第一个程序。对于程序员来说,在屏幕上看到这两个单词意味着他们的代码可以编译、加载和运行,并且他们可以看到输出。
它是一个测试,象征着一个程序的开始。在过去的几十年,它已经成为了一个历史悠久的传统。在某个时候,所有在你之前的程序员在意识到他们成功与电脑进行通讯之后,都会肾上腺素急剧上升。下面将会介绍程序历史上最著名的两个单词开始是怎样出现的:
点击在新窗口中浏览此图片
Brian Kernighan(上面照片中的帅哥)创造了“Hello, World”,他是一本被广泛阅读的书籍(1978 年的《C 程序设计语言》)的作者。他在《C 程序设计语言》的前身(1973 年出版的《B 程序设计语言的入门教程》)中首次引用‘Hello World’。

main( ) {
extrn a, b, c;
putchar(a); putchar(b); putchar(c); putchar(’!*n’);
} 1 ’hell’;
b ’o, w’;
c ’orld’;


不幸的是,这位传奇人物自己也没办法明确地指出何时或者为什么他选择了“Hello, World”这两个单词。当在接受 Forbes India 的访谈中被问到是什么激发了他使用“Hello, World”这个名字的灵感时,他说他的记忆很模糊。“我记得的是我看到了一个卡通片,里面有一个鸡蛋和一只母鸡,并且母鸡说:‘Hello, World’”。
考虑到“Hello, World”代表着计算机编程对于大众是一种普遍现象的诞生,这组单词是很适合的。
当时,Kernighan 和他的同事 Dennis Ritchie(已故的 C 语言之父),都没想到这个语言和教程对今天的编程领域如此重要。因为这些想法只不过是 Bell 实验室(AT&T 的一个研究和开发分部)里面的一个研究项目。
虽然没人可以科学地解释为什么“Hello, World”会变得如此受欢迎,但是“Hello, World”程序标志着编程的历史论调上一个重大改变。下面让我们看下它的历史背景。
萌芽时期
虽然在今天很难想象,但是在 Kernighan 的书中出现“Hello World”之前,即二十世纪七十年代之前,计算机在大众心中是伴随着贬义的。它们是巨大的机器、非常慢、占据了整个房间并且需要科学家或者研究者全职进行维护保养。事实上,在七十年代末以前,计算机科学家编程都是用一叠叠打孔卡。

点击在新窗口中浏览此图片
人们普遍将计算机视为遥不可及的、复杂的和贵得离谱的设备,它们只预留给学术界的精英、国防或者政府。实际上,献身于计算机世界的行业巨头已努力地洗掉这个污名。想想我们已经走了这么远,以至于没有了我们的个人设备之后,切实感受到的焦虑感,这是多么令人惊讶。

第一次使用计算机的著名事迹之一发生在 1890 年的美国,当时自动电子制表机为超过 6 千万美国人计算数据。在二十世纪四十年代,Bombes 和 Colossus 计算机在第二次世界大战期间对德国人的电报密码进行解密。

二十世纪五十年代迎来第一台针对算术运算的商用计算机,像 Zuse 3 和 UNIVAC,但你需要上百万的美元才能买到一台。

从教育的角度来看,很多关于早期程序设计语言(像 FORTRAN 或者 BASIC)的书籍,都会提供这样一个观点作为书本的开始:计算机其实很有用的。这是根据算法学家和研究者 John Mount 的文章得到的。Mount 说“Hello, World”爆炸性受追捧表明一个时代的到来,那个时代里,计算机科学家不再觉得他们需要说服社会,去相信计算机的实用程序是有形的。

例如,在 1964 年的《My Computer Likes Me When I Speak Basic》一书中,介绍部分大体上谈及程序设计语言的意图。此外,第一个例子输出:“MY HUMAN UNDERSTANDS ME”。使用这个例子是为了加深一个不太流行的想法:人类事实上是可以与计算机对话的。1956 年的动态编程开始使用一些可以应用到普通计算的例子。

直到《C 程序设计语言》出现时,“Hello World”才真正地流行起来。
点击在新窗口中浏览此图片
Hello World’ 编程来了

触发“Hello World”传播的一个主要催化剂是 PDP-11(最早成功商用的微型计算机之一)的并行介绍。数字设备公司(DEC)一共卖出超过 600,000 台单价为 $10,000 的 PDP-11,这个价格远远低于通常需要花费数百万美元的计算机的价格。此外,PDP-11 的 16 位系列不需要穿孔卡片。这是首次你可以使用程序设计语言直接与一台电脑对话。

但是为了提高大众的接受程度,DEC 不能提及它是一台计算机。DEC 把它作为“程序控制的数据处理机”来进行推销,以此与过去的大型计算机撇清关系。随着更多的人购买可编程计算机,对《C 程序设计语言》这本书的需求也激增。

C 和 Unix 操作系统在 PDP-11 上首次流行起来。所以,紧接着出现支持新的 C 程序设计语言的商用计算机的热潮,驱使成千上万的人去阅读 200 页的《C 程序设计语言》。这也重新介绍了‘Hello World’。

在八九十年代以后,几乎每个用桌面软件工作的程序员都会拥有那本书的一份拷贝或者参考文献。至今已经卖出数百万份拷贝了。

开始学习编程可能会有很多不同的基础程序可用,但是到目前为止,‘Hello World’是最著名的。每个程序员会记住他们的第一个‘Hello World’,并以此作为他们开始编程的一个仪式。很多人可能没有意识到,但是每次一个程序员通过‘Hello World’这两个单词清除程序设计的第一个障碍后,他们所感受到的甜蜜和胜利的感觉,是经历过的超越历史的时刻。
May 9
开篇
     “古巴比伦王颁布了汉摩拉比法典,刻在黑色的玄武岩,距今已经三千七百多年,你在橱窗前,凝视碑文的字眼,我却在旁静静欣赏你那张我深爱的脸……”,想必大家都听过这首周杰伦演唱的《爱在西元前》,由方文山填词,歌词生动美妙不落俗套。作为周杰伦的御用作词人,方文山其实只有高中学历,但他才华横溢,创作了不少经典之作,有些作品甚至被收录进了学校的课本中。那么他是如何写出这么美妙的歌词呢?直到看了他的访谈笔者才了解到其实他的歌词大多来源于生活中的灵感,这首《爱在西元前》就是他在某日逛完博物馆后有感而发,他从现实的场景获得灵感再进行文字加工,从而文思泉涌,妙笔生花。其实运维工作也亦然,需要我们时时从工作中寻找灵感。笔者从事运维工作接近8年,多年的工作经验总结出一个道理:我们要善于从运维工作中发现问题,并根据问题及过往经验发明创造改进工具,接着再从发明创造中提炼技术,最后根据技术提炼原理。近来以Docker为代表的容器很火,很多互联网公司都在使用。那么Docker是如何获得互联网公司的青睐的,我们又应该如何来应用Docker,本章将从以下几个方面逐一介绍:
 我们为什么使用Docker
 离线系统业务架构
 Clip名字服务
 Clip名字服务与Docker应用场景



我们为什么使用Docker
     首先来看一下我们在运维中发现了哪些问题。以笔者就职的腾讯公司案例为例,腾讯产品战线很长,笔者所在的团队负责运维腾讯的QQ、Qzone等核心产品,而这些产品也算是中国互联网骨灰级的业务了,整体架构都有着复杂的历史背景。不仅团队的老员工发现架构逐渐产生的问题,团队新入职的同事也会指出与原任职公司比较架构存在的一些问题等等。如何将很多好的技术融入到我们的业务架构中,以解决产品的问题是摆在每一个运维架构师面前的难题。架构的复杂性与历史沉重的包袱决定着牵一发而动全身,并且架构支持的业务为近半数的中国互联网网民所使用,还有着不少的优点,在对其进行改进优化之前,我们主要先分析了它的优缺点:
  优点:目前还是单机或单集群对应一个业务模块的形式,彼此间没有交集与复用(见图1),其架构优势应对爆发式增长扩容方便,成本结算简单,架构形成的历史原因更多的是前者流量的爆发增长。
点击在新窗口中浏览此图片
图1
  缺点:随着网民的饱和,相同业务模块下移动流量上涨,PC流量直线下降,很多业务出现了低负载情况。海量服务器的运维场景中即使只有1%的低负载规模也是惊人的,在实际运营中低负载+长尾业务下的机器数量可能达到了25%-30%甚至更高。当然这里不排除业务对流量做了冗余与灾备,但是多个业务模块的灾备就会出现浪费资源的情况。除低负载与长尾业务外,为了应对业务的流量徒增团队为产品留出了足够富裕的Buffer资源以应对某业务徒增,而导致这些资源的实际利用率不高。

分析了优缺点后以及运营中发现的这问题后,从2014年中我们就开始着手离线业务混合部署项目。项目的思路是通过高负载业务譬如音频转码、视频转码、图片人脸计算和图片特征提取业务(注:后统称“离线业务”)与低负载、长尾业务和部门buffer业务进行混合部署,来提升机器利用率并同时为部门节约机器成本。不过经过半年多的运营,我们也发现了很多问题:
  在低负载与长尾业务上部署离线业务,如果离线业务抖动出现大的CPU毛刺(特别在晚高峰时段)就会影响用户的使用体验,从而导致部分投诉产生的情况。
  部署在buffer池上的离线业务,由于在线业务申请机器导致机器上的离线环境没有及时清理,继续运营影响在线业务的正常使用。
这两个问题比较有代表性的问题也是我们最不希望看到的,所以总结经验教训后在2015年上半年我们又重新打磨项目开发了新版离线系统,新项目与老项目相比通过Docker技术将离线业务与在线业务的低负载、长尾业务和Buffer池进行了部署,从而顺利解决了上述的问题。这里主要利用了Docker的三个优势:
  Cgroup对资源的隔离让离线与在线业务彼此间对资源使用有了保障;
  命名空间,让相同框架多业务跑在相同物理机上成为可能;
  容器的快速回收上线下线,使用Buffer资源时不再为回收离线资源而头痛。



离线系统业务架构
上文中笔者提到QQ、Qzone的整体架构着很复杂的历史背景,而希望仅仅通过Docker或一两种工具来解决现实存在的所有问题是不现实的,所以我们在保持现有架构与内部用户习惯的基础上另辟蹊径逐渐解决我们产品运营上的一些问题,具体部署见图2。
点击在新窗口中浏览此图片
离线系统业务架构(图2)

从图2中可以看到在部门Cmdb基础之上,我们建立了数据分析系统,通过它可以分析出哪些是低负载业务,哪些是时段低负载业务。在此基础之上我们使用Clip名字服务系统在Cmdb基础之上重新建立了业务之前的IP关系,并根据重新划定关系的IP进行了业务流量与资源快速的调度。其中Etcd为服务发现工具,根据Clip名字服务系统传入的信息通过Confd重新生成HAproxy的配置文件并热重启它,离线业务流量通过HAproxy的虚拟IP屏蔽底层资源信息,建立离线与资源的生态供应链,同时上层监控与调度均为Clip名字服务系统。这里读者有可能会有疑问,尽管HAproxy的虚拟IP屏蔽底层资源信息(其为动态的),但如果程序有问题,如果能快速到机器上去debug自己的程序呢? 这里我们使用的是Clip名字服务。




Clip名字服务
Clip(http://blog.puppeter.com/read.php?7)是一个名字服务C/S架构,它将传统的IP管理维度替换为名字服务即有意义可记忆的String。Clip将IP对应的String关系保存在Server端。Client端可以下载SDK,通过SDK遍历Server端的String对应IP的关系,并在本地对获取的IP模块关系进行重新的组织与编排。传统服务器IP方式与String方式相比,String方式有3点优势:
  传统IP管理方式,IP由4组无意义的数字组成,比较难记忆。String更方便记忆;
  管理海量服务时,IP相似经常会导致运营故障,譬如A模块(10.131.24.37 )和B模块(10.117.24.37),后两组数字一致,系统惯性的认为B模块就是A模块,发送配置导致线上故障。通过string管理方式可以规避此问题;
  String 可以解析1个IP,也可以解析一组IP ,根据IP也可以反解析String对应关系,使得管理一组服务更加方便。
    Clip中的String由四段(字段含义idc-product-modules-group)组成,读者会发现String与Cmdb的结构很像:四级模块定位一个服务。但是为了充分利用资源我们的业务要求一个IP可能要对应多个服务,不同的服务有自己的波峰与波谷,在相同的IP上只要保证各业务的波峰不重叠就满足了业务的需求,也充分了利用资源。而在一台服务器上混合部署不同的业务模块,四级模块就只能定位到服务的IP级别,而无法精确定位到真正的服务,所以Clip名字服务在Cmdb的基础上增加了port端口,即五段(字段含义idc-product-modules-group-port)定位一个服务。我们可以将动态的IP通过Clip接口注册到指定含义的String上,通过Clip自带工具来解析实时的String对应IP关系,譬如:

# clip cstring -q idc-product-modules-group-port
192.168.0.1
192.168.0.2
192.168.0.3
192.168.0.4
192.168.0.5

Clip数据存储结构分为两层:
关系层保存了String对应IP或内部系统Cmdb的模块关系(见图3)。
点击在新窗口中浏览此图片
Clip名字服务关系表(图3)
关系层数据含义见表1
点击在新窗口中浏览此图片
关系层数据含义表1
数据层保存了String与IP的具体关系(见图4)。
点击在新窗口中浏览此图片
Clip名字服务数据表(图4)
点击在新窗口中浏览此图片
Clip名字服务在存储String对应IP关系基础上,在SDK上还提供了远程端口扫描、远程ssh、远程文件拷贝和查找String关系结构的工具子命令等,更多可以见http://blog.puppeter.com/read.php?7。




Clip名字服务与Docker应用
如笔者上文所提,离线系统的建设思路就是将离线业务通过Docker快速的部署在资源空闲的机器上,而空闲的机器是通过数据分析系统长期分析沉淀的结果,Clip名字服务就是这两种资源建立联系的桥梁,但只有Clip绑定关系还是不够的,还需要建立绑定关系String对应Docker环境的关系,所以在Clip名字服务的基础上我们又扩充了Docker的资源关系表。
点击在新窗口中浏览此图片
Docker资源关系表图5
其中Docker资源使用的关系表的字段含义见表3:
点击在新窗口中浏览此图片
我们来看一个需求案例:某视频转码业务在上海需要使用资源约1000核心,对应的关系表为表4
点击在新窗口中浏览此图片
由于buffer资源不时在变动,我们需监控String (sh-buffer-qq-video-2877)整体核数是否低于mcount值,如果低于则出发自动扩容策略。同时也需针对Docker资源使用关系中的app_port字段来监控整体String (sh-buffer-qq-video-2877)业务是否处于健康状态。在这里我们沉淀了String (sh-buffer-qq-video-2877)的一些基础数据如负载、内存、网络和磁盘IO等为资源的调度奠定的基石(见图6)。
点击在新窗口中浏览此图片
离线运营系统图6
Dec 15
通过Puppet管理大量机器的过程中会经常遇到连接超时的情况,所以通过Shell脚本包装Puppet Agent随机连接也是一种很好的方法,以下为连接过程脚本。



Puppet连接过程架构
点击在新窗口中浏览此图片



Agent连接Master脚本(注:部分内部为了安全被替换为中文注释)


#!/bin/bash
# author: wds
# time : 20151212

## init
PATH="/sbin:/usr/sbin:/bin:/usr/bin:/usr/local/bin/"
export PATH
export LC_ALL=POSIX
export LANG=en
_PWD="/etc/puppet"
_PUPPET="/usr/local/services/puppet/bin/puppet agent"
_HOST="puppet.example.com"
_LOG_TIME=`date +%Y%m%d%H%M`

[ ! -e ${_PWD}/lock ] && mkdir ${_PWD}/lock
[ ! -e ${_PWD}/log ] && mkdir ${_PWD}/log
[ -e /etc/puppet/log/ ] && find /etc/puppet/log/ -name "*.log" -mtime +3 -exec rm -rf {} \;
[ -e /etc/puppet/lock/ ] && find /etc/puppet/lock/ -name "*.lock" -mmin +17 -exec rm -rf {} \;

## function
getip()
{
    IPADDR=`ifconfig eth1 | awk '/inet addr/ {print $2}' | cut -f2 -d ":"`
    if [ "x${IPADDR}" == "x" ];then
        IPADDR=`ifconfig eth1 | awk '/inet addr/ {print $2}' | cut -f2 -d ":"`
    fi
    echo $IPADDR
}

netlog()
{
    #打网络日志
}

#content title
sendalarm()
{
    #发送告警
}

rand(){
    min=$1
    max=$(($2-$min+1))
    num=$(date +%s%N)
    echo $(($num%$max+$min))
}

clip_ini(){

if [ ! -e /usr/local/services/clip/clip ];then
    netlog "clip not exists fail"
    exit
fi
# clip 相关介绍http://blog.puppeter.com/read.php?7

if [ ! -e /etc/facter/facts.d/clip ];then
    ipaddress=`getip`

    clip=`/usr/local/services/clip/clip cstring -i $ipaddress`
    if [ ! -e /etc/facter/facts.d/ ];then
      mkdir -p /etc/facter/facts.d/
    fi

    echo -n "#!/bin/bash
    echo \"clip=$clip\"
    " > /etc/facter/facts.d/clip
    chmod -R 777 /etc/facter/facts.d/clip
fi

return 0
}

hostname=`getip | sed 's/\./_/g'`
if [ "x${hostname}" != "x" ];then
        hostname $hostname
fi

##############################################################################################
#/usr/local/services/puppet/bin/puppet agent --server puppet.example.com --test

## first  首次连接
if [ ! -e ${_PWD}/lock/first.lock ];then
    sed -i '/puppet/d' /etc/hosts
    echo "IP $_HOST # puppet" >> /etc/hosts
    res=`$_PUPPET --server $_HOST  --test | tee -a ${_PWD}/log/puppet.log | grep "Finished catalog run" | wc -l`
    if [ $res -eq 0 ];then
    netlog "puppet first fail"
    else
        touch ${_PWD}/lock/first.lock
    fi
fi

## second 二次连接

if [ ! -e ${_PWD}/lock/second.lock ];then
ipaddress=`getip`
clip=`/usr/local/services/clip/clip cstring -i $ipaddress`
if [ "x$clip" != "x" ];then
  touch ${_PWD}/lock/second.lock
fi

idc=`echo $clip | awk -F '-' '{print $1}'`
if [ "$idc" == "tj" ];then
    _host='IP'
elif [ "$idc" == "sz" ];then
    _host='IP'
elif [ "$idc" == "sh" ];then
    _host='IP'
else
    _host='IP'
fi

sed -i '/puppet/d' /etc/hosts
echo "$_host $_HOST # puppet" >> /etc/hosts
fi

## app
##########################################################################################
if [ -e ${_PWD}/lock/puppet.lock ];then
exit;
fi

clip_ini
wait
touch ${_PWD}/lock/puppet.lock
rnd=$(rand 1 5)
sleep $rnd
res=`$_PUPPET --server $_HOST  --test | tee -a ${_PWD}/log/puppet.log | grep "Finished catalog run" | wc -l`
if [ $res -eq 0 ];then
  rnd=$(rand 1 20)
  sleep $rnd
  res=`$_PUPPET --server $_HOST  --environment=${_ENVIROMENT} --test | grep "Finished catalog run" | wc -l`
  if [ $res -eq 0 ];then
    netlog "puppet cluster fail"
  fi
fi

netlog "puppet succ"
rm -rf ${_PWD}/lock/puppet.lock
exit 0;
Tags: ,
分页: 5/10 第一页 上页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]