青羽的博客

广义相对论告诉我们，时间并不是以恒定速度流逝的，更不是独立存在的一个标尺。

那么“时间”是从哪来的？是从我们体验“熵增”这个过程中来的。究其原因，是因为人类并不能感知到每个粒子的状态而只能感知到一个宏观现象。详见关于时间存在的几个质疑

双缝干涉实验告诉我们，粒子拥有叠加态，测量会导致叠加态的坍缩。通常这会扯到“意识”，但目前还没有这方面公开的权威研究结果，就不说了。

作者：赵泠
链接：https://www.zhihu.com/question/410716897/answer/1371899384

你可以看一点20世纪的物理，以便理解“熵增原理”对宇宙压根没用。要是你谈的“世界”不是宇宙而是地球表面，那就更和熵没什么关系了，19世纪的物理也不会在一个有外部热源不断输入能量、自身还不断向外辐射能量的非封闭系统里讨论什么熵增。
对宇宙谈“熵增”是毫无意义的。宇宙不适用热力学第二定律。宇宙在膨胀且是个自引力系统，是具有负热容的不稳定系统，没有平衡态，永远不会热寂。

根据位力定理，对于自引力系统，在一个周期内动能的时间平均值等于总能量的负值，即Ek=-E。也就是说，自引力系统> 得到能量时动能减小，失去能量时动能增大。
热学中比热容的定义是物体温度每升高1开尔文所需要的热量。
而对于自引力系统来说，释放能量才能提高温度，这就是负的热容量。
负热容系统没有稳定的平衡态。
宇宙是自引力系统，它根本不可能达到平衡态。
其实，在1872年，全人类都不知道什么量子力学的时候，玻尔兹曼就用涨落捅穿了热寂说的屁股。他就是凶手。现在都2020年了，还有人对着这盒骨灰“变得悲观”，几悲观的。
将一切现象都推给熵增等于说熵增不起任何作用，“宇宙的熵增”是无意义概念。
而且，除了在理想气体之类极少数系统里有用之外，在绝大多数系统里，熵都是无意义概念。

宇宙也不适用能量守恒定律。

膨胀的时空没有时间平移不变性。能量守恒定律由类时killing场生成，宇宙中没有这种场。宇宙非渐近平直，不能对全时空定义守恒的ADM能量[1]。简单粗暴地对宇宙套用能量守恒定律是不可行的。
按照目前的观测事实，宇宙中存在辐射和暗能量。从早期宇宙形成以来，暗能量在增长，从早期宇宙里几乎不含暗能量的状态发展至现在暗能量占据宇宙总能量的68.3%。
弗里德曼-勒梅特-罗伯逊-沃尔克度规[2]描述了符合观测事实（均匀、各向同性）的四维时空的大尺度结构，度规中随时间变化的尺度因子对应着宇宙空间尺寸的变化。重子物质的能量密度正比于尺度因子的负三次方，辐射的能量密度正比于尺度因子的负四次方，暗能量的能量密度不随尺度因子变化，因此宇宙不适用能量守恒定律。

1. ^无限远处重力场强度的计量
2. ^（riedmann-Lemaître-Robertson-Walker metric，FLRW度规）

上面这个关于热寂的回答告诉我们，宇宙并不适用热力学第二定律，也不适用能量守恒定律。当然也就没有热寂一说了。

倘若只是“知识”变了，看似知道的更多了，其实并没有改变什么。

无论是绝对时空观，还是相对时空观，还是玄学时空观，都是别人告诉你的死知识，知道这些和知道“显示屏上的图像是由像素构成的”没什么两样。

核心在于，能否用心去感受这些知识背后所隐藏的广阔天地带给自己内心的震撼以及察觉这些知识对自己潜移默化的改变。

“显示屏上的图像是由像素构成的”

第一层：哦，原来如此。

第二层：看似模拟的图像其实源头是离散的，有趣……

第三层：模拟信号也可表示图像比如老式电影胶卷，为什么要用数字信号？哦，因为数字信号方便处理。

第四层：这背后可是一整个数字世界啊！

还有受限于作者有限的思考能力而无法知道的第五层、第六层……

我们需要从一个全新的角度来看待这个世界，这些离我们并不遥远，相反，没有比这些更能影响我们日常生活的事物了。广义相对论的时空观，双缝干涉实验里的观察者，这些已经被实验证实的——哪怕并不是最终的真理，哪怕几百年后也都会被推翻——也足够揭示：现代人的世界观只是一个阶段性认识的产物、或者说直白点，一个幻象。我们生活在其中的这个世界，值得我们好好去体悟。

框架

用四种方法算算一个整数中位1的个数，关键词：位运算、效率。

首先把整个框架给出来，用上次我写的那个比较算法时间复杂度的模板和例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/*
比较不同的计算位1的个数的算法的时间复杂度
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <limits.h>

#define INT_BIT (CHAR_BIT * sizeof(int))

typedef int (*pfun_t)(int x);

void time_test(pfun_t method);

int main(void)
{
    return 0;
}

void time_test(pfun_t method)
{
    clock_t start, end;
    static int i = 0;
    i++;

    int loop = 1e6; // 多次运行取平均值
    int result;     // 计算结果

    start = clock();
    for (int i = 0; i < loop; i++)
    {
        result = method(9); // 计算9中位1的个数 => 2
    }
    end = clock();

    printf("method %d result: %d\n", i, result);
    printf("method %d duration: %.2e s\n\n", i, (double)(end - start) / CLOCKS_PER_SEC / loop);
}

循环右移

要计算一个整数中位1的个数，最简单的就是循环右移然后取最低位就好啦~

代码：

1
2
3
4
5
6
7
8
9
10
11
12

// 平均循环（INT_BIT）次
int method_1(int x)
{
    int cnt = 0;

    for (int i = 0; i < INT_BIT; i++)
    {
        cnt += (x >> i) & 1;
    }

    return cnt;
}

这个就不多说了，学过C语言的应该都能想到。平均循环（INT_BIT）次。

优化的循环右移

事实上，如果一个数只是低位有几个1，高位都是0，那么每次都循环INT_BIT次显然太浪费了，可以优化一下。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 平均循环（INT_BIT - N）次，N=前导零个数分布均值
int method_2(int x)
{
    int cnt = 0;

    if (x < 0)
    {
        // 去掉最高位方便逻辑右移，可移植
        x &= ~(1 << (INT_BIT - 1));
        cnt++;
    }

    while (x != 0)
    {
        cnt += x & 1;
        x >>= 1;
    }

    return cnt;
}

核心就是一个while循环，前面的if主要是处理负数的。因为C语言没有逻辑右移（不管是不是负数都补零）只有算术右移（如果是负数就补一），我试了一下确实没找到逻辑右移，所以只好在前面处理一下负数了，x &= ~(1 << (INT_BIT - 1))在我的电脑上其实就等价于x &= 0x7fffffff，这样做可移植性比较好（看起来比较高级而已，估计也没其他人运行这个程序）。

平均循环（INT_BIT - N）次，N=前导零个数分布均值。想不到在这里居然会碰上前导零……话说我还是在STM32的uC/OS-III内核里第一次看到前导零这个东东。理论上来说，N应该可以算出一个确定的数值，具体涉及到有符号整数的二进制补码形式的前导零的概率分布，听起来似乎有点复杂，懒得算了……

x &= x - 1消去最右边的1

原谅我实在是不知道这个方法该取什么名字，索性就这样叫吧……顾名思义，核心就是这个位运算：x &= x - 1，它可以消去x最右边的一，举个栗子：

1
2
3
4
5
6
7
8
9

  1010 (x=10)
& 1001 (10-1=9)
-------
  1000

  0111 (x=7)
& 0110 (7-1=6)
-------
  0110

我觉得这个栗子很清楚明白了，所以直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

// 平均循环（INT_BIT/2 - N）次
int method_3(int x)
{
    int cnt = 0;

    while (x != 0)
    {
        x &= x - 1;
        cnt++;
    }

    return cnt;
}

平均循环（INT_BIT/2 - N）次，这里假设整数是均匀分布的，这样每一位是0、1的概率各为50%，如果是其他分布的话就不是/2了。到底要不要减去前导零个数分布均值我没有想明白，应该是要吧，大概，因为循环次数也和前导零有关系……

查表

最后出场的方法通常是最厉害的，这次……也不例外。
顾名思义，查表嘛，你要问我怎么查？请看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 平均循环（INT_BIT/M - N）次，M=log2(sizeof(table))，N=前导零个数分布均值
int method_4(int x)
{
    // 0-15 位1的个数(M=4)
    static int table[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};

    int cnt = 0;

    if (x < 0)
    {
        // 去掉最高位方便逻辑右移，可移植
        x &= ~(1 << (INT_BIT - 1));
        cnt++;
    }

    while (x != 0)
    {
        cnt += table[x & 0xf];
        x >>= 4;
    }

    return cnt;
}

因为涉及右移，所以还是需要处理一下负数，然后查表。

平均循环（INT_BIT/M - N）次，M=log2(sizeof(table))，N=前导零个数分布均值。

总结

结果：

在算法的精简程度和时间复杂度之间需要有一个平衡，我觉得第三种方法取得了一个不错的平衡，核心代码就一个5行的while循环，因为是直接位运算也不需要考虑负数的情况。

如果需要更高的速度那么整一个M=5甚至M=6的查表法，如果还觉得想要更刺激一些，其实还有一些很变态的位运算方法，我从网上看到的，至今不太明白。那种方法不需要循环也不需要判断，直接几行位运算就得到结果了，估计怕是只有游戏核心引擎里才需要那么快的速度吧。

那一天，他45岁，面对心底再一次被激起的怨愤，而无处发泄；

那一天，他31岁，看着满街打砸抢烧的人群，空有满腔怒火却深感无力；

那一天，他16岁，听着面前这位大哥的怒吼亦或是恳求，眼神逐渐坚定了起来；

那一天，苍山如海，残阳如血，当他第一次看见这本红色封面的书本之时，他还不知道这代表了什么。

虽然有些词语他还不太懂，比如“communism”这个词语，他脑海里浮现的是在电视和网络上接收到的与之相关的红色暴政，暴力侵略，独裁统治……但他觉得，事情不该是这样，绝不该是这样。

他的脑海里一直有个声音在喃喃低语——“你们得想出一个更好的办法”

了解黑豹党的历史。

于中东与某黑豹党幸存党员亲属会晤。

回到美国，在细致而深入的调查之后写了一篇《明州黑人运动考察报告》，报告中明确指出“种族歧视是阶级矛盾的外在表现之一”。

组织群众，联合受压迫的白人，宣传共产主义思想，暂时不碰武器，不组建军队，以免重蹈黑豹党的覆辙。建党，前期闷声发展地下党员，注意低调行事。时机成熟后，建军，成立地下革命根据地，低调训练军队，同时注意统一战线。

联合一切可以联合的进步力量，如被发现，必要时战略转移到亚洲，不和美国军队硬刚。

在非洲、南美洲、东南亚和中东建立革命根据地，使美国依赖的一些低端产业链掌握在党的手中。
……
……
……

许多年之后，美共中央党校。

这里是一个暂时用来作仓库的房间，当他处理完一天的政务之后，他常常喜欢来这里坐坐。

这里的东西不久之后都要放到革命历史博物馆里去展览了，虽然是他下令这样做的，但他还是有些不舍——想要在最后再单独陪陪它们。

他眼前放着那杆他第一次使用的武器，一支半自动步枪，虽然现在只剩下因高温而变形的枪管了；

旁边柜子上的盒子里，放着一个缺了一角的徽章，看起来十分破旧，但其上承载着他最好的朋友、同时也是他最怀念的战友的不屈的意志；

在一堆像是老旧书店买回来的二手书籍中，还有一本残破的红色书籍，他轻轻拿起来，拂了拂上面的灰尘，打开了它，又看到了那个改变了他一生，也改变了整个世界的单词——“communism”。

他看着这个单词，想起了许多往事，他还记得，记得第一次看见这本书的那一天，苍山如海，残阳如血。

《后浪》一出，阶级矛盾被进一步放大。B站上《韭浪》、《非浪》等讽刺作品层出不穷，且有向娱乐化发展的趋势。许多人讨论这件事，或激进，或戏谑，或讽刺，或感叹。这不妨看作是一种“发泄”，而“发泄”是暂时的，影响也有限。再之后就是沉闷，因为心理能量都“发泄”完了。

“翼装飞行女大学生不幸身亡”的新闻一出，知乎上有部分答案阴阳怪气地说这个女大学生家里有钱如何如何，抛开仇富心理不说，这位女大学生并没有做错任何事，无非就是安全措施没做到位导致了这个事件的发生。此事件为何会引发这么多的讨论？一说是死者亲属花钱买的热搜，目的是给景区压力以此加大赔偿/报复心理。我看还有另一部分原因，这个原因和《后浪》事件一样：阶级矛盾。若要仇富，那么真正该把矛头对准的，应该是“财产可以继承”这件事以及背后的法律条文。这个才是核心。

“权力不得继承”已是共识，那么下一步就是实现“财产不得继承”，这是阶级差异的源头之一。

“疫情使俄罗斯倒退了四十年”的笑话，让我想到了那个曾经的苏联。

奴隶主与奴隶、地主与农民、资本家与工人，阶级矛盾从未消失，以至于人们似乎已经默认这一切是正确的。直到十月革命一声炮响，一个本着为所有劳苦大众而创立的、没有剥削没有压迫的乌托邦，从文字描绘中，来到了现实。

然而，这个理想的实践最终失败了。

但这并不能否认那理想的崇高，更不能熄灭埋藏在每一个人心底最深处的那一颗火苗。

星星之火，可以燎原。

《国际歌》，全世界无产阶级最嘹亮的战歌，曾经响彻在巴黎、在冬宫、在柏林、在首尔、在东京、在井冈山，在延安……

从西伯利亚穿过伏尔加河向西

从高加索的雪山渡过里海往南

从烟囱森立的城市到一望无际的田地

整个欧亚大陆都沸腾起来了

如今，还有工人会唱这首歌吗。

看了《共产党宣言》之后，除了“全世界无产者，联合起来！”这句口号外，印象最深的还有这句话：

“代替那存在着阶级和阶级对立的资产阶级旧社会的，将是这样一个联合体，在那里，每个人的自由发展是一切人自由发展的条件。”

是的，“每个人的自由发展是一切人自由发展的条件”，这就是人类命运共同体。那时候，工作将不再是为了生存，而是为了体现自身价值。

要是学校里的《马克思主义基本原理》课程教材直接用《资本论》就好了，《马克思恩格斯文集》也行啊。《毛泽东思想和中国特色社会主义理论体系概论》课程教材直接用《毛泽东选集》和历届党和国家最高领导人的文集就好了啊。

我曾经是憧憬小资生活的，至少是精神上的小资。一杯咖啡，岁月静好，但那只是一厢情愿。有一面墙上用白底红漆写了八个字：“放弃幻想，准备战斗”，我觉得很合适。

我也曾经是社会达尔文主义的崇拜者，认为人分三六九等，认可优胜劣汰。但内心总有一种感觉，感觉这是不对的，感觉本末倒置了。

我能扯这些有的没的，想来也是因为还能吃饱穿暖，以及一点想要改变什么的愿望。若是出生在穷苦人家，不辛勤劳作就吃不饱饭的话，我还有时间想这些吗？

狼在吃羊时，羊群不是一起愤怒地拿角去攻击狼，而是麻木甚至内讧。

若是每一只羊都能明白自己的处境并且团结起来，有组织有纲领有行动，那将是一股巨大的力量。

“我相信这不是我一个人的经历：傍晚时分，你坐在屋檐下，看着天慢慢地黑下去，心里寂寞而凄凉，感到自己的生命被剥夺了。当时我是个年轻人，但我害怕这样生活下去，衰老下去。在我看来，这是比死亡更可怕的事。”——《沉默的大多数》

若是在革命年代，能为了理想而抛头颅洒热血，那样的话，没有衰老，没有疾病，没有贫困，有的只是坚定的信仰和一颗赤子之心，也是一种幸福吧。

在日复一日的生存压力下，在现代都市的欲望中，十年后，可还记得这些中二的理想？

好久没写文章了，因为我逐渐从细枝末节的技术细节中抽离出来了，想从一个更全面，更本质的层面去看待这世界，而那些东西很难写成文章。

不过今天看到一个有意思的东西，试着写写，写的不好请见谅，因为我是在失眠的状态下写的。

其实开始写的时候我想删了，感觉没什么好写的，因为这篇文章——《自指机器的奥秘》已经写得够详细了。

但是基于以下两点：

1. 想让更多人了解到这些有趣的知识
2. 我想用较为感性的方式而非理性的论述来表达

这么想着，我还是水一篇文章吧，哈哈哈哈。

我们知道，$y=x$ 能在平面上表示为一条直线，而 $y<x$ 则表示这条直线的右下侧区域，对吧。

那么，猜猜这个函数画出来是什么样子呢？

……

……

……

……

……

事实上，这个函数画出来是这样的：

就是它自身，神奇吗？我也觉得神奇。关于这个函数的细节，我就懒得写了，互联网嘛，能引用链接就引用链接：Tupper自我指涉公式：图象里竟然包含式子本身

这种自我复制的函数还不太好构造，不过我们可以用编程来搞搞~

自我复制嘛，用编程来搞就是写一段能输出自身源代码的代码。

首先，最简单的，比如要输出一句“hello world”用Python是这样写：

1

print("hello world")

运行结果就是：

1

hello world

那么，要输出源代码，就得这样写：

1

print("print(\"hello world\")")

运行结果就是：

1

print("hello world")

而要输出这句的源代码，就得再嵌套一层：

1

print("print(\"print(\\\"hello world\\\")\")")

如此循环下去，无穷无尽……

(禁止套娃)

那么，就没有办法了吗？

办法肯定是有的，不然我也不会写这篇文章。

实际上，办法就在《自指机器的奥秘》这篇文章的后半段里，我懒得写就直接引用链接了（事实上我也不太懂）。

不过运用自己对编程语言的知识，网上查一下，照葫芦画瓢还是能搞出来的（还搞了两个）：

Python语言版本：

1

I='I=%r;print(I%%I)';print(I%I)

C语言版本：

1
2
3

#include <stdio.h>
char *I="#include <stdio.h>%cchar *I=%c%s%c;%cint main(){printf(I,10,34,I,34,10);}";
int main(){printf(I,10,34,I,34,10);}

运行之后得到的输出结果就是源代码本身，一模一样的。

代码的具体分析不难，写出来也枯燥，我就不写了（才不是因为懒）。

我本来是想着沿着 自我复制->自我描述->自指->递归、分形、无穷->自我意识 这条逻辑链写下去的，但是《自指机器的奥秘》这篇文章其实已经写得很详细了，我再写就画蛇添足了。

最后，说说我自己的一些想法吧。

关于意识，关于宇宙，关于爱，关于永恒的真理，我以前觉得理性至上、科学至上，只想寻找真理，喜欢严谨的公式，对“不懂科学技术”的人不屑一顾，比较高傲……但我现在觉得理智的思考是一方面，感情的体验也是不可或缺的。与其说对真理不再追逐了，倒不如说我相信“真理就在心中”，语言无法描述，只可意会不可言传，毕竟道可道，非常道。

耳得之而为声，目遇之而成色。外在的物质/能量/信息也都是真理的一部分/一方面的某种形式化/扭曲化的体现/显现。

仰望过星空吗？当看见那些穿越广袤浩瀚的宇宙的星光时，内心是否会有某种触动？

那不过是一些特定频率的电磁波进入眼睛经过大脑视觉神经元转译形成的图像而已，这样想着，是不是感觉缺了什么呢？

听音乐时，当那些旋律挑动你的心弦时，是否仿佛闻到了冬天校园里的味道？亦或夏天燥热的街道的味道？

那不过是一些特定频率的声波振动鼓膜经过大脑听觉神经元转译后激活相关记忆神经元的联想而已，是这样吗？

走在夜晚回家的路上时，栀子花或夜来香的味道沁入心脾时，会想起以前做过的那个朦胧的奇妙的梦吗？

那不过是一些特定结构的分子接触鼻腔黏膜经过大脑嗅觉神经元转译后激活相关记忆神经元的联想而已，仅此而已？

当我看到密密麻麻的代码的时候，我感到了厌倦，我感到这一切没有意义，于是我问了自己一个问题，我真的喜欢编程吗？我这是叶公好龙吗？

我觉得不是这样的。表面的推理看起来是这样，但好像忽略了什么。

忽略了两点。

第一点，那密密麻麻的代码很多都是可以重构的，可以更加精简的。比如（以下举例都是没有严格的时间复杂度和空间复杂度的要求）可以用switch/case就不要if/else各种嵌套、可以用一种更加高效的数据结构就不要自己设置奇奇怪怪的数据结构、可以模块化就不要全塞在一个函数里、重复的地方尽量抽象成一个单独的函数等等。许多看起来密密麻麻的代码逻辑不一定很复杂，反而往往是简单的逻辑。而看起来简简单单的代码，往往真正具有内涵。一个真正好的项目，其代码的组织是可以让人一目了然的。

更别说变量命名和缩进了，我就是再怎么热爱编程，看到一堆意大利面式的代码我也很头疼。

想起当初上C语言课的时候，黄院长告诉我们数组下标不一定非得从0开始，可以从1开始，这样可读性高。我当时还不以为然，觉得专业的程序员都应该是数组下标从0开始，现在想想，黄院长其实说得有道理的。如果可读性能有明显的提升，浪费几字节的空间也无所谓（有严格空间要求的除外，比如嵌入式编程）。

第二点，我总觉得人啊，生下来应该是享受生活、享受生命的。人应该是目的，而不是手段。正如康德所说：

“人是生活在目的的王国中。人是自身目的，不是工具。人是自己立法自己遵守的自由人。人也是自然的立法者。”

如果为了生产出什么产品而刻意的压抑人的本性，那是适得其反，丢了西瓜捡芝麻的行为。人类生产这些东西应该是服务于人类自身的，我们不应该是螺丝钉——至少我不应该是，而应该是创造者，通常创造本身就是一种奉献，但这种奉献不是刻意的，而是一种副产品。

Linus真的是为了奉献什么才搞出来的Linux吗？或者是为了挣钱才弄的吗？不是的，他只是在好奇心的引导下，想玩一玩，于是自己动手实践，在原Unix基础上进行创造，然后放在网上，让大家都可以参与进来。

我只是举个例子，其实创造的门槛一点也不高，你唱一首歌、写一篇文章、做一个甜品、甚至拍张照片发一段话，只要是基于自己的意志去做的事情，那都可以是一种创造，而这种创造本身就是一种享受的过程，无意间也会给社会作出贡献。

知乎上有个“这个世界有哪些不合理的地方？”的回答里有这么一段话：

全球总生产力已经翻了不知道多少倍了，人均下来也早就能满足一个人的基本需求，然而我们还是处在剥削的状态下每天不得不让工作占据绝大多数时间，另外还有一大批人因为没有争取到被剥削的机会而食不果腹。

某些地方未利用的土地明明还有很多，房价高绝不是因为土地不够人用，然而就是有既得利益者控制着不去开荒，使得普通都市白领终身房奴。

任何生产出来的产品都应被消费，总生产力比古代提高100倍即意味着我们比古代人多消费了100倍的商品，然而一个人的刚需是有限的，生产力的极大提高无疑意味着对人类种种欲望的挖掘和无限放大，我们不经要问：人类真的需要消费这么多东西吗？

深以为然。

说到底，其实我并不想讨论什么高深的东西，随笔罢了。人始终是变化着的，也许过段时间我又觉得人生应该奋斗，应该苦尽甘来了，又或者是其他什么，一切皆有可能。

前言

说是初探，其实我并不是想写一个入门的教程，因为网上关于排序算法的学习资料已经足够多了，我不想再增加无谓的冗余。

这篇文章主要是简单的梳理和总结，并对各个排序算法的时间复杂度做一个直观的认识，但不分析时间复杂度。

但是如果直接起名为“总结八大排序算法”的话未免看起来有点“排序算法学完了”的意思。之所以叫“初探”，是因为把这些排序算法梳理总结之后才算是刚刚入门吧。

排序算法

为了对各个排序算法的时间复杂度有一个直观的认识，这里我借助了PTA上的OJ来测试。

测试题目如下：

测试程序框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <stdio.h>
#include <stdlib.h>

typedef long item_t;

void XXX_Sort(item_t arr[], int n)
{
    // Code...
}

int main(void)
{
    int n;
    scanf("%d", &n);
    item_t arr[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%ld", &arr[i]);
    }

    XXX_Sort(arr, n);

    for (int i = 0; i < n; i++)
    {
        if (i != 0)
        {
            printf(" ");
        }
        printf("%ld", arr[i]);
    }

    return 0;
}

冒泡排序

冒泡排序，一般学的第一个排序算法就是这个吧，不多说。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void Bubble_Sort(item_t arr[], int n)
{
    int flag;
    item_t tmp;
    for (int i = 1; i < n; i++)
    {
        flag = 0;
        for (int j = 0; j < n - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                flag = 1; // Identity swapped
            }
        }
        if (flag == 0)
        {
            break;
        }
    }
}

效率：

可以看到，测试点4和8直接运行超时了，测试点6用了八秒多，我们来看下一个。

插入排序

插入排序，也叫直接插入排序，以区别于改进的插入排序（希尔排序）。想象你打扑克牌，每次从乱牌中摸一张出来插入到手中的有序序列中，这就是插入排序了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void Insertion_Sort(item_t arr[], int n)
{
    int i, j;
    item_t tmp;
    for (i = 1; i < n; i++)
    {
        tmp = arr[i];
        for (j = i; j > 0 && arr[j - 1] > tmp; j--)
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = tmp;
    }
}

效率：

可以看到，所有测试点都通过了，最慢的测试点6用了三秒多，看起来比冒泡快了不少。

希尔排序

希尔排序就是改进的插入排序，插入排序是每次两两相邻的比较，希尔排序是每次隔一段距离比较，这个距离取决于增量序列，不同的增量序列有不同的排序效率。这里我采用的是实际效果比较好的Sedgewick增量序列。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

int *Sedgewick(int n)
{
    static int sedgewick[Sedgewick_SIZE] = {0};
    for (int i = 0; i < Sedgewick_SIZE; i += 2)
    {
        sedgewick[i] = 9 * pow(4, i) - 9 * pow(2, i) + 1;
        sedgewick[i + 1] = pow(4, i + 2) - 3 * pow(2, i + 2) + 1;
    }
    return sedgewick; // {s[0]=1, s[1]=5, s[2]=19, s[3]=41, ..., s[Sedgewick_SIZE-1]}
}

void Shell_Sort(item_t arr[], int n)
{
    int *sedgewick = Sedgewick(n);

    int i, j, si;
    item_t tmp;

    for (si = Sedgewick_SIZE - 1; sedgewick[si] >= n; si--)
        ;

    for (int step = sedgewick[si]; si != -1; step = sedgewick[--si])
    {
        for (i = step; i < n; i++)
        {
            tmp = arr[i];
            for (j = i; j >= step && arr[j - step] > tmp; j -= step)
            {
                arr[j] = arr[j - step];
            }
            arr[j] = tmp;
        }
    }
}

效率：

没有比较就没有伤害呀，可以看到，采用Sedgewick增量序列的Shell排序在所有的测试点表现都非常出色，最慢也不过是10ms这个数量级。

选择排序

选择排序，顾名思义，就是每次都扫描一遍待排序序列然后选择最小/最大的一个元素移动到已排序序列的末端。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void Selection_Sort(item_t arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int minPosition = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minPosition])
            {
                minPosition = j;
            }
        }
        if (minPosition != i)
        {
            item_t tmp = arr[i];
            arr[i] = arr[minPosition];
            arr[minPosition] = tmp;
        }
    }
}

效率：

囧……比冒泡还慢……不过，幸好它还有一个改进版，请看下面。

堆排序

既然选择排序是选择最小/最大的元素然后移动，主要耗费的时间其实在选择元素那里，因为每次都要扫描一遍，那么这时候堆(Heap)就派上用场啦。因为最小堆/最大堆的堆顶元素始终是最小/最大的那一个，而关于堆的构造是有一个线性时间复杂度的算法，因此使用堆可以大大提高选择排序的效率，这种排序就叫堆排序。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

void PercDown(item_t arr[], int r, int n)
{
    /* 将n个元素的数组中以arr[r]为根的子堆调整为最大堆 */
    int parent, child;
    item_t tmp;

    tmp = arr[r];
    for (parent = r; (parent * 2 + 1) < n; parent = child)
    {
        child = parent * 2 + 1;
        if ((child != n - 1) && (arr[child] < arr[child + 1]))
        {
            child++;
        }
        if (tmp >= arr[child])
        {
            break;
        }
        else
        {
            arr[parent] = arr[child];
        }
    }
    arr[parent] = tmp;
}

void Heap_Sort(item_t arr[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        PercDown(arr, i, n);
    }

    for (int i = n - 1; i > 0; i--)
    {
        item_t tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;

        PercDown(arr, 0, i);
    }
}

效率：

表现非常出色！所有测试点都在10ms这个数量级。而且理论上，堆排序确实是很优秀的一种算法。

归并排序

归并排序，其实核心思想就是把两个已排序的序列归并成一个已排序的序列，然后递归罢了。说起来简单，实现起来并不简单……

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

void Merge(item_t arr[], item_t tmpArr[], int left, int mid, int right)
{
    int tmp = left;
    int start = left, end = right;
    int leftEnd = mid - 1;

    while (left <= leftEnd && mid <= right)
    {
        if (arr[left] <= arr[mid])
        {
            tmpArr[tmp++] = arr[left++];
        }
        else
        {
            tmpArr[tmp++] = arr[mid++];
        }
    }

    while (left <= leftEnd)
    {
        tmpArr[tmp++] = arr[left++];
    }
    while (mid <= right)
    {
        tmpArr[tmp++] = arr[mid++];
    }

    for (int i = start; i <= end; i++)
    {
        arr[i] = tmpArr[i];
    }
}

void Merge_Pass(item_t arr[], item_t tmpArr[], int n, int length)
{
    int i;

    for (i = 0; i <= n - 2 * length; i += 2 * length)
    {
        Merge(arr, tmpArr, i, i + length, i + 2 * length - 1);
    }

    if (i + length < n)
    {
        Merge(arr, tmpArr, i, i + length, n - 1);
    }
    else
    {
        for (int j = i; j < n; j++)
        {
            tmpArr[j] = arr[j];
        }
    }
}

void Merge_Sort(item_t arr[], int n)
{
    int length = 1;
    item_t *tmpArr = malloc(n * sizeof(item_t));
    if (tmpArr != NULL)
    {
        while (length < n)
        {
            Merge_Pass(arr, tmpArr, n, length);
            length *= 2;
            Merge_Pass(tmpArr, arr, n, length);
            length *= 2;
        }
        free(tmpArr);
    }
    else
    {
        fprintf(stderr, "ERROR: There was not enough memory.\n");
        exit(-2);
    }
}

效率：

可以看到，归并排序也非常优秀。

（喂喂喂，就这么简短吗！）

快速排序

接下来，终于到了传说中的，实际应用中最快的一种算法——快速排序算法！听名字就知道，快速排序非常快，嗯，让我们来看看到底有多快。

首先关于这个快速排序算法的几点，我需要说明一下：

1. 我这里参考了中国大学MOOC浙大的陈越老师的课程设置了一个快排阈值 CUTOFF ，当待排序的元素数量大于这个阈值时才进入快排，否则调用简单排序（这里我用的选择排序，冒泡排序也可以）。因为快速排序会频繁递归，当待排序的元素数量充分小时，快速排序可能还不如简单排序快。
2. 一般来说，快排的参数都有三个：待排序的元素首地址、左边起始下标、右边结束下标，网上的快排程序大多都是这样的。这里我把它简化到了两个参数：待排序的元素首地址、待排序的元素个数。因为快排会频繁地递归，所以原始版本会push push push…… pop pop pop……，这个版本就是push push…… pop pop……，总的来说，就是减少了大概三分之一的函数调用开销。我一开始以为会增加程序的复杂度，降低可读性，但是写完之后发现似乎并没有降低可读性，如果懂了快排的话那么这个程序应该还是很容易看懂的。并且这样刚好符合 void XXX_Sort(item_t arr[], int n) 这样的函数接口，就不用再重新写一个符合接口的函数然后再调用递归了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

void swap(item_t *a, item_t *b)
{
    item_t tmp = *a;
    *a = *b;
    *b = tmp;
}

item_t median(item_t arr[], int n)
{
    int left = 0, right = n - 1;
    int center = (left + right) / 2;

    if (arr[left] > arr[center])
    {
        swap(&arr[left], &arr[center]);
    }
    if (arr[left] > arr[right])
    {
        swap(&arr[left], &arr[right]);
    }
    if (arr[center] > arr[right])
    {
        swap(&arr[center], &arr[right]);
    }

    swap(&arr[center], &arr[right - 1]);

    return arr[right - 1];
}

void Quick_Sort(item_t arr[], int n)
{
    if (n > CUTOFF)
    {
        int pivot, low, high;

        pivot = median(arr, n);
        low = 0;
        high = n - 2;

        while (1)
        {
            while (arr[++low] < pivot)
                ;
            while (arr[--high] > pivot)
                ;
            if (low < high)
            {
                swap(&arr[low], &arr[high]);
            }
            else
            {
                break;
            }
        }

        swap(&arr[low], &arr[n - 2]);

        Quick_Sort(arr, low);
        Quick_Sort(arr + low + 1, n - low - 1);
    }
    else
    {
        Insertion_Sort(arr, n);
    }
}

效率：

1. CUTOFF = 10 时
   
2. CUTOFF = 100 时
   
3. CUTOFF = 1000 时
   

可以看到，当CUTOFF在10-1000这个范围时，效率几乎没有波动，而当CUTOFF超出这个范围时，效率会慢慢下降。总的来说，快速排序好像和希尔排序堆排序以及归并排序效率差不多。但是一般来说，面对一组充分大的随机数，快排表现通常都比其他排序要好一点。

基数排序

理论上已经证明，基于比较的排序算法最快最快也是 O(NlogN) 这个时间复杂度的，换句话说，一个排序算法，如果想要突破 O(NlogN) 这个魔咒的话，就不能比较两个元素，那么问题来了，不能比较那还怎么排序啊？

我原以为，基于二分思想的快排已经是最快的了。但是，大千世界无奇不有，你想得到的想不到的其实都存在，基数排序就是其中之一。在某种情况下，基数排序算法能够在线性时间复杂度内完成排序。

那么基数排序到底是什么？我不讲，如果你不知道的话请去看《数据结构》这门课（MOOC、B站都有），一般都会讲的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

typedef struct node *node_t;
struct node
{
    item_t key;
    node_t next;
};

struct headNode
{
    node_t head, tail;
};
typedef struct headNode bucket_t[RADIX];

int GetDigit(item_t item, int D)
{
    int digit;

    for (int i = 1; i <= D; i++)
    {
        digit = (int)item % RADIX;
        item /= RADIX;
    }
    return digit;
}

void Radix_Sort(item_t arr[], int n)
{
    int negativeFlag = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < 0)
        {
            negativeFlag = 1;
            break;
        }
    }

    if (negativeFlag)
    {
        Insertion_Sort(arr, n);
    }
    else
    {
        int D, digit;
        bucket_t bucket;
        node_t tmp, p, list = NULL;

        for (int i = 0; i < RADIX; i++)
        {
            bucket[i].head = NULL;
            bucket[i].tail = NULL;
        }
        for (int i = 0; i < n; i++)
        {
            tmp = (node_t)malloc(sizeof(struct node));
            tmp->key = arr[i];
            tmp->next = list;
            list = tmp;
        }

        for (D = 1; D <= MAX_DIGIT; D++)
        {
            p = list;
            while (p)
            {
                digit = GetDigit(p->key, D);

                tmp = p;
                p = p->next;
                tmp->next = NULL;

                if (bucket[digit].head == NULL)
                {
                    bucket[digit].head = tmp;
                    bucket[digit].tail = tmp;
                }
                else
                {
                    bucket[digit].tail->next = tmp;
                    bucket[digit].tail = tmp;
                }
            }

            list = NULL;

            for (digit = RADIX - 1; digit >= 0; digit--)
            {
                if (bucket[digit].head)
                {
                    bucket[digit].tail->next = list;
                    list = bucket[digit].head;
                    bucket[digit].head = bucket[digit].tail = NULL;
                }
            }
        }

        for (int i = 0; i < n; i++)
        {
            tmp = list;
            list = list->next;
            arr[i] = tmp->key;
            free(tmp);
        }
    }
}

效率：

可以看到，似乎和快排他们表现差不多，原因应该是优化得不好，有大量的指针指来指去……

基数排序有一个致命的缺点：不好处理负数，更准确地说，是不好处理符号相反的数。这和它的原理有关，因为它不是比较大小而是把元素拆分成“基数”迭代进行桶排序。不过可以把基数排序改造一下，使它可以处理负数，但好像不怎么常用，也比较麻烦。所以我用了一种简单粗暴的方法：扫描一遍，有负数就用插入排序。哈哈哈……

另外两种排序

其实还有两种排序算法，分别是表排序和桶排序，如果加上这两种算法的话那就是所谓的“十大排序算法”了。这里简单说一下。

• 表排序：表排序适用于待排序元素特别大的情况下，比如每个待排序元素都是一部电影，那么把元素移来移去显然就会耗费很多时间，这个时候就换种思路，不移动元素本身，而移动元素的“索引”，把“索引”排序好后依照“索引”来看元素就是有序的了。
• 桶排序：桶排序其实就是低阶的基数排序。桶排序的原理就是给每个可能的待排序元素设置一个“桶”，然后扫描一遍，遇到的元素符合哪个“桶”就扔进去，最后把“桶”串起来就好了。

总结

最后，关于这八大排序算法的总结，可以用一张图来表示：

这篇文章看起来好长啊，不过如果把代码去掉还是挺短的，哈哈哈……

八大排序算法的全部代码我都上传到了GitHub上，请随意：Sorting Algorithm

以上。

首先搞清楚一个概念，什么是“符号系统”？

我个人理解是 各国的文字、字母、数字、标点符号、表情符号等等进行排列组合生成的所有可能的符号及其相互作用的规则构成的集合。

比如“true”、“false”、“w”、“∫”、“d”、“*”、“/”、“\”等等这些都是符号系统的真子集。

知识的传承，人类的发展，几乎是与符号系统捆绑在一起的。

其实我并不是闲得没事干跑来设计符号系统，我只是察觉到有很多目前人们正在使用的符号的不合理性，不吐不快而已。

语言是符号系统的一个真子集，一门语言的生命力依附于使用这个语言的国家/地区的影响力，并不是很看重这个语言本身是否易于学习和使用。

比如，虽然某些小众语言很难学也很难用（至少我是这么觉得。在外国人眼中，貌似中文也很难学），但因为还有一些国家和地区的人们使用这些语言作为官方语言，所以目前这些语言的生命力还比较旺盛。

比如，虽然“世界语（Esperanto）”的语法严谨、语音优美、逻辑性强、表现力丰富，比英语更易学，但知道世界语的人显然没有知道英语的人多。

所以就算没多少人能看见这篇文章，我还是要吐槽一下目前的符号系统，不吐不快。

那么，正片开始！

首先，我吐槽几点：

• “true”和“false”代表“真”和“假”，在编程中经常使用这两个单词。明明是反义词，但是字母数量却不相等，有没有搞错啊！导致书写的宽度不一样，逼死强迫症。类似的还有“big”和“small”等等等等。你看人家中文，“真”和“假”，“大”和“小”，“美女”和“帅哥”都是一致的宽度。

• “w”，达不溜，26个英语基本字母之一，这个有什么问题呢？问题很大！“w”其实是“double v”（一说是“double u”）的意思，那么问题就来了，你拿一个复合符号当基本字母干啥呀！重新设计一个符号不行吗？“w”是依附于“v”之上的，二者不应该同为基本字母。逼死强迫症+1。

• “∫”和“d”在数学里代表“积分运算符”和“微分运算符”，微积分可以说是数学大厦的基石了，相当重要，现在看似不重要是因为人类平均科学素质不高，几百年后微积分一定会和加减乘除一样被普遍使用（虽然频率可能略低于加减乘除）。可是你看看微积分的符号是啥？“∫”这个还好说，未来的键盘估计会有这个符号，可是“d”怎么解释？为什么拿一个英语基本字母当作微分运算符？“∫ dt”、“∫ dx”之类的，看起来很不和谐啊！“∫”和“d”明明互为逆运算，首先得基本对称吧，其次这么重要的符号，应该要有唯一性吧，这两个条件都不满足，逼死强迫症+2。

• “*”，星号，在计算机领域一般用作乘法运算符，经常用作正则匹配的通配符。乘法就乘法，通配符就通配符，为什么搞在一起？再说乘法这么基本的运算为什么没有一个唯一的符号？就用“×”（不是英语字母x）不好吗？你说因为怕和字母“x”搞混，所以不用。那么请你解释一下“0”和“O”、“1”和“l”？好吧这可能是ASCII码的锅，属于历史遗留问题了。

• “/”，斜杠我觉得我现在很杠，在计算机领域一般用作除法运算符，经常用作路径分隔符。除法就除法，分隔符就分隔符，为什么搞在一起？再说除法这么基本的运算为什么没有一个唯一的符号？就用“÷”不好吗？好吧这应该是ASCII码的锅，属于历史遗留问题了。

• “\”，反斜杠，在计算机领域一般用作路径分隔符或者转义字符。关于斜杠和反斜杠，总结一下是这样的：在Windows系统中，斜杠表示除法运算符；反斜杠表示路径分隔符或转义字符。在Unix系统中，斜杠表示除法运算符或路径分隔符；反斜杠表示转义字符。乱吧？我也觉得乱。

• 字符集，各种字符集，你品，你细品。虽然我知道微软要整一个BOM是有原因的，LE和BE也是有用的，每个国家和地区也都想搞一个自己的字符集，可是看着就是逼死强迫症。

  

那么，一个理想的符号系统应该是怎样的呢？

既然是理想的，那么我就天马行空了，不考虑现实了。换句话说，想象一万年以后，人类已经共产主义了，那时候的符号系统是怎样的呢？

• 不保留任何对现有符号系统的兼容性。
  • 微分运算符、积分运算符等重要数学符号重新定义。
  • 基本符号重新构造。
  • 重新设计一套十六进制的数字符号系统。
• 词汇集符合霍夫曼编码定理。
  • “true”、“false”等重要的词汇设计成单音节的。
• 统一使用改进的世界语或者其他专为全人类设计的语言，但保留各个文化的语言。
• 拼写即音标。读音具有唯一性。
• 明确区分基本符号和复合符号，基本符号具有唯一性。
• 数学、计算机科学和物理学等具有自洽而完备的符号系统。

开个脑洞，到时候中文这种表意文字的影响力不会被削弱，反而更具有生命力。原因如下：

• 中文这种表意文字普遍比英语这种表音文字具有更大的信息密度。想想看，为什么目前只有中国和日本有大型的弹幕网站，并且形成了独有的弹幕文化？就因为中文和日文比英语具有更大的信息密度，换句话说就是更加易读（缺点就是相较于英语不易写）[1]。但是，在高新技术的支持下，还有多少人需要用笔来写？
• 到时候需要用笔的，可能只有一个地方：书法。这是艺术。
• 中文诗词非常优美：
  • “黄河之水天上来，奔流到海不复回”之磅礴；
  • “举杯邀明月，对影成三人”之浪漫；
  • “人生自古谁无死，留取丹心照汗青”之赤诚；
  • “问苍茫大地，谁主沉浮”之大气；
  • “落霞与孤鹜齐飞，秋水共长天一色”之意境；
  • “对酒当歌，人生几何”之感慨；
  • ……

好吧，可能是因为我是中国人，所以对中文情有独钟。总之，在一个理想的符号系统之下，世界人民都使用同一种语言——可能是改进的世界语或者其他专为全人类设计的语言，那时候，中文也还有一席之地。

另外，既然那时候基本不用笔写字了（书法除外），并且文盲应该也没有了，那么简化字就没有必要了，可以适当恢复繁体字。爱无心（愛），亲不见（親），怎么行呢？并且书法也基本都是写繁体字。

以上。

[1]: 为什么全世界只有中日两个国家弹幕视频网站成为流行？ - Sithferia的回答 - 知乎 https://www.zhihu.com/question/65281224/answer/967240703

前言

啊，终于写完了。

我是指，那9个.c文件以及3个.h文件。

其实，前几天就写完了，只是写完后发现似乎可以再优化一下，于是就在重构代码的路上一去不复返了……

简单说一下，我用顺序储存结构（数组）和链式储存结构（链表）分别实现了列表List、队列Queue以及栈Stack的ADT，文件如下（后来又增加了二叉搜索树BinarySearchTree，散列表HashTable，最大堆MaxHeap以及加权图WeightedGraph）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Data Structure
├─List
│    ├─main.c
│    ├─List.h
│    ├─ArrayList.c
│    ├─LinkedList.c
│
├─Queue
│    ├─main.c
│    ├─Queue.h
│    ├─ArrayQueue.c
│    ├─LinkedQueue.c
│
├─Stack
|    ├─main.c
|    ├─Stack.h
|    ├─ArrayStack.c
|    ├─LinkedStack.c
|
├─...

List（列表）目录下共有四个文件，其中main.c是驱动代码，用来测试实现的功能。List.h是ArrayList.c和LinkedList.c共用的头文件，用来定义统一的接口，这种接口无关具体的实现，也就是说无论该接口的具体实现是用的数组（ArrayList.c）还是用的链表（LinkedList.c），都不影响使用该接口的程序（main.c）。

如果是列表或者是栈还好，很容易就统一了，但是队列就很麻烦，因为队列用数组实现的时候并没有指向每一个元素的指针，而用链表实现的时候不仅有链表内部的指针，还有一个包含两个指针的结构体分别指向队头和队尾，而这个指针结构体也是用一个指针来表示的，换句话说就是一个指针指向包含两个指针的结构体，这两个指针又分别指向一个链表的头和尾，而另一边只是一个数组以及两个表示头和尾的整数组成的结构体，所以统一起来很麻烦，也没有专业的老师指导，全靠我自己瞎想，不过好在我花了差不多两天的时间最终还是统一了。

我又有完美强迫症，总想着优化优化再优化，结果就是把一个简单的写来练习的程序硬是重构成了比较标准的ADT接口包……

一开始每种ADT只有两个.c文件（数组实现和链表实现），那两个.c文件重构了好几次然后拆分成四个文件：驱动代码，头文件，数组实现的代码和链表实现的代码，这期间的曲折我就不细说了，总之我一个人坎坎坷坷总算完成了……人生太难了。

这里我就只把列表的头文件和链表实现的代码以及驱动代码贴出来简单说一下，就不全部贴出来了，因为太多了。

头文件

头文件如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

/*
列表(List)
对象集：n(n>=0)个元素构成的有序序列 a1, a2, a3 ... an.
操作集：列表 list 属于 list_t ，整数 i 表示元素下标(从0开始)，元素 data 属于 item_t ，基本操作有：
    1. list_t CreateList(void)
    2. void DestroyList(list_t list)
    3. int GetLength(const list_t list)
    4. bool IsFull(const list_t list)
    5. bool IsEmpty(const list_t list)
    6. item_t Get(const list_t list, int i)
    7. int Find(const list_t list, item_t data)
    8. void Insert(list_t list, int i, item_t data)
    9. void Delete(list_t list, int i)
    10. void Print(const list_t list)
    11. void Reverse(list_t list);
*/

#ifndef LIST_H
#define LIST_H

#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define ERROR (-1)

#define LIST_CAPACITY 128

typedef int item_t;

typedef struct list *list_t;

/*************************************************
  Description:    创建一个空列表
  Parameter:      空
  Return:         一个指向空列表的指针
*************************************************/
list_t CreateList(void);

/*************************************************
  Description:    销毁一个列表 list
  Parameter:      一个指向待销毁列表的指针 list
  Return:         空
*************************************************/
void DestroyList(list_t list);

/*************************************************
  Description:    求列表 list 的长度
  Parameter:      一个指向列表的指针 list
  Return:         列表长度
*************************************************/
int GetLength(const list_t list);

/*************************************************
  Description:    判断列表 list 是否已满
  Parameter:      一个指向列表的指针 list
  Return:         如果列表已满则返回 true ，否则返回 false
*************************************************/
bool IsFull(const list_t list);

/*************************************************
  Description:    判断列表 list 是否已空
  Parameter:      一个指向列表的指针 list
  Return:         如果列表已空则返回 true ，否则返回 false
*************************************************/
bool IsEmpty(const list_t list);

/*************************************************
  Description:    取列表 list 的第 i 个元素
  Parameter:      一个指向列表的指针 list
                  下标 i (0 <= i < GetLength(list))
  Return:         第 i 个元素
*************************************************/
item_t Get(const list_t list, int i);

/*************************************************
  Description:    求元素 data 在列表 list 中的下标
  Parameter:      一个指向列表的指针 list
                  一个待寻找元素 data
  Return:         待寻找元素 data 的下标 i 或者 ERROR
*************************************************/
int Find(const list_t list, item_t data);

/*************************************************
  Description:    在列表 list 的下标为 i 的位置上插入一个元素 data
  Parameter:      一个指向列表的指针 list
                  下标 i (0 <= i <= GetLength(list))
                  待插入元素 data
  Return:         空
*************************************************/
void Insert(list_t list, int i, item_t data);

/*************************************************
  Description:    从列表 list 当中删除下标为 i 的元素
  Parameter:      一个指向列表的指针 list
                  下标 i (0 <= i < GetLength(list))
  Return:         空
*************************************************/
void Delete(list_t list, int i);

/*************************************************
  Description:    输出列表 list 的内容
  Parameter:      一个指向列表的指针 list
  Return:         空
*************************************************/
void Print(const list_t list);

/*************************************************
  Description:    就地逆置列表 list
  Parameter:      一个指向列表的指针 list
  Return:         空
*************************************************/
void Reverse(list_t list);

#endif

其中item_t是抽象的，用户需要不同的数据类型的时候只需要在头文件这里改一下就可以了，数组实现或链表实现都不用改。

链表实现

下面看看链表实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

#include "List.h"

struct list
{
    item_t data;
    list_t next;
};

/*******************************
Helper functions implementation.
*******************************/

/*******************************
Interface functions implementation.
*******************************/

list_t CreateList(void)
{
    list_t list = (list_t)malloc(sizeof(struct list));
    if (list == NULL)
    {
        fprintf(stderr, "ERROR: (file %s, line %d) There was not enough memory.\n", __FILE__, __LINE__);
        exit(-2);
    }

    list->next = NULL;

    return list;
}

void DestroyList(list_t list)
{
    if (list)
    {
        list_t current;

        while (list)
        {
            current = list->next;
            free(list);
            list = current;
        }
    }
}

int GetLength(const list_t list)
{
    list_t current = list->next;
    int length = 0;

    while (current)
    {
        current = current->next;
        length++;
    }

    return length;
}

bool IsFull(const list_t list)
{
    return GetLength(list) >= LIST_CAPACITY;
}

bool IsEmpty(const list_t list)
{
    return list->next == NULL;
}

item_t Get(const list_t list, int i) // list[i]
{
    if (i < 0 || i > (GetLength(list) - 1))
    {
        fprintf(stderr, "Illegal location.\n");
        return ERROR;
    }

    list_t current = list->next;

    for (int j = 0; j < i; ++j)
    {
        current = current->next;
    }

    return current->data;
}

int Find(const list_t list, item_t data)
{
    int index = 0;
    list_t current = list->next;

    while (current != NULL && current->data != data)
    {
        current = current->next;
        index++;
    }

    if (current)
    {
        return index;
    }
    else
    {
        return ERROR;
    }
}

void Insert(list_t list, int i, item_t data)
{
    if (IsFull(list))
    {
        fprintf(stderr, "The list is full.\n");
        return;
    }

    if (i < 0 || i > GetLength(list))
    {
        fprintf(stderr, "Illegal location.\n");
        return;
    }

    list_t new = (list_t)malloc(sizeof(struct list));
    if (new == NULL)
    {
        fprintf(stderr, "ERROR: There was not enough memory.\n");
        exit(-2);
    }
    new->data = data;

    list_t tmp = list;
    for (int j = 0; j < i; j++)
    {
        tmp = tmp->next;
    }
    new->next = tmp->next;
    tmp->next = new;
}

void Delete(list_t list, int i)
{
    if (IsEmpty(list))
    {
        fprintf(stderr, "The list is empty.\n");
        return;
    }

    if (i < 0 || i > (GetLength(list) - 1))
    {
        fprintf(stderr, "Illegal location.\n");
        return;
    }

    list_t tmp = list;
    for (int j = 0; j < i; j++)
    {
        tmp = tmp->next;
    }
    list_t del = tmp->next;
    tmp->next = del->next;
    free(del);
    del = NULL;
}

void Print(const list_t list)
{
    printf("Now print the list elements:\n");
    list_t tmp = list->next;
    int len = GetLength(list);
    for (int i = 0; i < len; i++)
    {
        printf("[%d]: %d\n", i, tmp->data);
        tmp = tmp->next;
    }
    printf("That's all.\n");
}

void Reverse(list_t list)
{
    if (GetLength(list) <= 1)
    {
        return;
    }

    list_t pre = list->next;
    list->next = NULL;
    list_t tmp;

    while (pre)
    {
        tmp = pre;
        pre = pre->next;
        tmp->next = list->next;
        list->next = tmp;
    }
}

简单说几点：

2. 这些是我写来练习的程序，因此并没有实现所有的链表操作，同时在函数内部有充分的提示信息。
3. Print函数可以被抽象成一个Traverse函数，接受一个函数指针，这样更加抽象一点。
4. 变量命名和函数命名很重要。C语言不具有面向对象的特性，因此这里函数采用大驼峰命名法，变量采用小驼峰命名法。
5. 不仅malloc()和free()要成对存在，free()和p = NULL也要成对存在。简单来说就是释放一个指针变量p指向的内存空间后要立刻把它指向NULL。因为释放前后，p所指向的内存空间是一样的。所以释放后p所指向的仍然是那块内存空间。可是释放后的那块内存空间已经不属于p了，该内存空间可能会被分配给其他函数使用。如果其他函数在那块内存空间存放了值，而现在假如不小心再用p往里面写入了数据就会把那个值给覆盖了。所以当内存空间被释放后，要立刻把指针变量指向NULL。
6. 使用malloc()申请了内存空间之后一定要紧接着用if (p == NULL)判断申请成功没。虽然一般不会出错，可是保持良好的编程习惯以后写程序不容易出Bug。
7. 肯定还有不足的地方，但是我不想再花时间改了。

驱动代码

最后是驱动代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include "List.h"

int main(void)
{
    list_t list1 = CreateList(), list2 = CreateList();
    item_t a[] = {1, 2, 3, 4}, b[] = {233, 666, 888, 999};

    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        Insert(list1, i, a[i]);
        printf("Insert an item to list 1 [%d]: %d.\n", i, a[i]);
    }
    printf("\n");

    for (int i = 0; i < sizeof(b) / sizeof(b[0]); i++)
    {
        Insert(list2, i, b[i]);
        printf("Insert an item to list 2 [%d]: %d.\n", i, b[i]);
    }
    printf("\n");

    printf("Reverse list 1.\n");
    Reverse(list1);
    Print(list1);
    printf("\n");

    for (int i = 0; i < GetLength(list2); ++i)
    {
        Insert(list1, i, Get(list2, i));
        printf("Insert an item from list 2 to list 1 [%d]: %d.\n", i, Get(list2, i));
    }
    printf("\n");
    Print(list1);
    printf("\n");

    item_t elem = 999;
    printf("Find item in list 1: item %d at [%d].\n", elem, Find(list1, elem));
    printf("\n");

    int length = GetLength(list1);
    for (int i = 0; i < length; i++)
    {
        Delete(list1, 0);
        printf("Delete an item from list 1.\n");
    }
    printf("Is list 1 empty? %s.\n", IsEmpty(list1) ? "yes" : "no");
    printf("\n");

    DestroyList(list1);
    DestroyList(list2);
    printf("Destroy all lists.\n");

    return 0;
}

运行结果

测试的时候只需要

1

gcc main.c LinkedList.c && ./a.exe

就可以了。

运行结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

Insert an item to list 1 [0]: 1.
Insert an item to list 1 [1]: 2.
Insert an item to list 1 [2]: 3.
Insert an item to list 1 [3]: 4.

Insert an item to list 2 [0]: 233.
Insert an item to list 2 [1]: 666.
Insert an item to list 2 [2]: 888.
Insert an item to list 2 [3]: 999.

Reverse list 1.
Now print the list elements:
[0]: 4
[1]: 3
[2]: 2
[3]: 1
That's all.

Insert an item from list 2 to list 1 [0]: 233.
Insert an item from list 2 to list 1 [1]: 666.
Insert an item from list 2 to list 1 [2]: 888.
Insert an item from list 2 to list 1 [3]: 999.

Now print the list elements:
[0]: 233
[1]: 666
[2]: 888
[3]: 999
[4]: 4
[5]: 3
[6]: 2
[7]: 1
That's all.

Find item in list 1: item 999 at [3].

Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Delete an item from list 1.
Is list 1 empty? yes.

Destroy all lists.

最后

其他数据结构也是这样的，代码我都放到了GitHub上：Data-Structure。

还记得我十个月前写的那篇文章：浅谈计算圆周率吗？

在那篇文章里我用的是这种方法计算耗时：

1
2
3
4
5
6
7
8
9
10

clock_t start, end;

start = clock();
// method_1(N);
// method_2(N);
// method_3(I);
method_4(I);
end = clock();

printf("time: %.2lf s\n", (double)(end - start) / CLOCKS_PER_SEC);

显然，这种方法很不方便，因为要比较不同的算法耗时的时候，只能一个一个注释再运行。如果要想要一次运行就把所有算法耗时都显示出来就需要把上面这段代码封装成为一个函数，该函数的入口参数是被测函数的地址，就需要用到函数指针。当时想到了这一点，但是因为懒没有去实现它。该来的总会来，在向IT行业转型的时候肯定需要用到这些东西，今天就把它搞定！（其实早就搞定了，只是今天才写文章）

一共有两个例子，并由这两个例子引出比较算法时间复杂度的模板。话不多说，首先来看第一个例子。

计算多项式

比较不同的计算多项式的算法的时间复杂度。

给定多项式：

$$
f(x)=a_{0}+a_{1} x+\cdots+a_{n-1} x^{n-1}+a_{n} x^{n}
$$

计算当 $x$ 等于某一值时 $f(x)$ 的值。

暴力算法

一个很直接很暴力的算法就是按照定义来算：

1
2
3
4
5
6
7
8
9
10

// n是最高幂次，a[]是升幂排列的多项式系数，x是要计算的那一点
double method_1(int n, double a[], double x)
{
    double y = 0;
    for (int i = 0; i <= n; i++)
    {
        y += a[i] * pow(x, i);
    }
    return y;
}

这种算法的时间复杂度是 $O(N^2)$ 。

秦九韶算法

除此之外，还记得高中学过的一个计算多项式的算法——秦九韶算法吗？

将多项式化成如下形式：

$$
f(x)=a_{0}+x\left(a_{1}+x\left(\cdots\left(a_{n-1}+x\left(a_{n}\right)\right) \cdots\right)\right)
$$

因此代码可以简化为：

1
2
3
4
5
6
7
8
9

double method_2(int n, double a[], double x)
{
    double y = 0;
    for (int i = n; i >= 0; i--)
    {
        y = a[i] + x * y;
    }
    return y;
}

这种算法的时间复杂度降到了 $O(N)$ 。

怎么直观地看出区别呢？写个时间测试函数吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void time_test(pfun_t method)
{
    clock_t start, end;
    static int i = 0;
    i++;

    int loop = 1e7; // 多次运行取平均值
    double a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 升幂排列的多项式系数
    double result; // 计算结果

    start = clock();
    for (int i = 0; i < loop; i++)
    {
        result = method((sizeof(a) / sizeof(a[0]) - 1), a, 1.1); // 计算f(1.1)的值
    }
    end = clock();

    printf("method %d result: %lf\n", i, result);
    printf("method %d duration: %.2e s\n\n", i, (double)(end - start) / CLOCKS_PER_SEC / loop);
}

其中 pfun_t 是在开头定义的函数指针类型：

1

typedef double (* pfun_t)(int n, double a[], double x);

好啦，这时候就可以在主函数里面直接调用测试函数了，想测几个就测几个。

1
2
3
4
5
6
7

int main(void)
{
    time_test(method_1); // 暴力算法
    time_test(method_2); // 秦九韶算法
    getchar();
    return 0;
}

运行结果：

可以看到，在只有十项的时候耗时就已经差了一个数量级，如果是一百项，一千项呢？

计算最大子列和

什么是最大子列和问题？就是说，给定N个整数序列：

$$
\left{A_{1}, A_{2}, \dots, A_{N}\right}
$$

求函数

$$
f(i, j)=\max \left {0, \sum_{k=i}^{j} A_{k}\right }
$$

的最大值，其中 $1 \le i \le N, 1 \le j \le N$ 。

暴力算法

首先，最直接的就是暴力循环，求出所有可能的连续子列和：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int method_1(int n, int a[])
{
    int thisSum, maxSum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            thisSum = 0;
            for (int k = i; k <= j; k++)
            {
                thisSum += a[k];
            }
            if (thisSum > maxSum)
            {
                maxSum = thisSum;
            }
        }
    }
    return maxSum;
}

这种算法的时间复杂度是 $O(N^3)$ 。

改进的暴力算法

很显然上面的算法中，在计算子列和时，可以利用前一步的计算和的结果，并不需要每次从头累加，因此得到改进的暴力算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int method_2(int n, int a[])
{
    int thisSum, maxSum = 0;
    for (int i = 0; i < n; i++)
    {
        thisSum = 0;
        for (int j = i; j < n; j++)
        {
            thisSum += a[j];
            if (thisSum > maxSum)
            {
                maxSum = thisSum;
            }
        }
    }
    return maxSum;
}

这种算法的时间复杂度是 $O(N^2)$ 。

俗话说，一个专业的程序员在看到一个算法的时间复杂度是 $O(N^2)$ 的时候都要下意识的想办法把它优化到 $O(N\log N)$ ，因此有了下面这个算法（这些算法当然不是我想出来的）：

分治法

顾名思义，分治法就是将问题一分为二，缩小问题规模，递归求解。通常这种算法都是最快的了。快速排序算法也是基于这种思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

int divideAndConquer(int a[], int left, int right)
{
    int maxLeftSum, maxRightSum;
    int maxLeftBorderSum, maxRightBorderSum;
    int leftBorderSum, rightBorderSum;
    int center, i;

    if (left == right)
    {
        if (a[left] > 0)
            return a[left];
        else
            return 0;
    }

    center = (left + right) / 2;

    maxLeftSum = divideAndConquer(a, left, center);
    maxRightSum = divideAndConquer(a, center + 1, right);

    maxLeftBorderSum = 0;
    leftBorderSum = 0;
    for (i = center; i >= left; i--)
    {
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }

    maxRightBorderSum = 0;
    rightBorderSum = 0;
    for (i = center + 1; i <= right; i++)
    {
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }

    return MAX(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

int method_3(int n, int a[])
{
    return divideAndConquer(a, 0, n - 1);
}

其中 MAX() 是我定义的一个宏：

1

#define MAX(A, B, C) ((A) > (B) ? (A) > (C) ? (A) : (C) : (B) > (C) ? (B) : (C))

原来是一个函数，改成宏能快一点（点点点……）。

这种算法的时间复杂度是 $O(N\log N)$ 。

在线处理算法

事实上所有你能想到和想不到的算法基本都已经有了，比如这个在线处理算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int method_4(int n, int a[])
{
    int thisSum = 0, maxSum = 0;
    for (int i = 0; i < n; i++)
    {
        thisSum += a[i];
        if (thisSum > maxSum)
        {
            maxSum = thisSum;
        }
        else if (thisSum < 0)
        {
            thisSum = 0;
        }
    }
    return maxSum;
}

根据问题的定义，结果必定是一个非负数。因此可以通过抛弃负子列，来保证最大子列和是递增的。当扫描一遍，最大子列和不再递增时，当前的最大子列和即为解。

太优雅了有木有！

这种算法的时间复杂度是 $O(N)$ ！

同样的，时间测试函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void time_test(pfun_t method)
{
    clock_t start, end;
    static int i = 0;
    i++;

    int loop = 1e5; // 多次运行取平均值
    int size = 100;
    int a[size];
    srand(0);
    for (int i = 0; i < size; i++)
    {
        a[i] = rand(); // 给定的整数序列
    }
    int result; // 计算结果

    start = clock();
    for (int i = 0; i < loop; i++)
    {
        result = method(size, a); // 计算最大子列和
    }
    end = clock();

    printf("method %d result: %d\n", i, result);
    printf("method %d duration: %.2e s\n\n", i, (double)(end - start) / CLOCKS_PER_SEC / loop);
}

只需要改一下函数指针和参数，就可以了。

主函数如下：

1
2
3
4
5
6
7
8
9

int main(void)
{
    time_test(method_1); // 暴力循环法 O(N^3)
    time_test(method_2); // 改进的暴力循环法 O(N^2)
    time_test(method_3); // 分治法 O(NlogN)
    time_test(method_4); // 在线处理算法 O(N)
    getchar();
    return 0;
}

运行结果：

大概就是这种感觉。

为什么要将键盘规范成现在这样的“QWERTY”键盘按键布局呢？ 这是因为最初，打字机的键盘是按照字母顺序排列的，而打字机是全机械结构的打字工具，因此如果打字速度过快，相邻键的组合很容易出现卡键问题，于是Christopher Sholes发明了QWERTY键盘布局。他将最常用的几个字母安置在相反方向。众所周知，这种键盘主要的设计目的是使击键的速度不至太快而导致卡住。不过在很多文章中的说法有一个小小的错误，就是这种键盘的键位设计并不是要“使击键的速度不至太快而导致卡住”，而是“在不至卡住的前提下尽量提高打字速度”。 Christopher Sholes在1868年申请专利，1873年使用此布局的第一台商用打字机成功投放市场。正如很多事情一样，习惯的力量是难以抵挡的，这就是为什么有今天键盘的排列方式。这不得不说是一个历史遗留问题。

建议：

• 把键盘上的字母按顺序重新安排一下，我个人觉得按照ABCD顺序排列就挺好的。
• 把加、减、乘、除、模、幂、等以及大括号、中括号、小括号单独拿出来放一起。每次输入小括号还要Shift真的不方便，如果小括号不用按Shift的话LISP说不定都会有更多的人用了。

技术上真的不难，主要是人们不愿意去改变旧有的习惯。用政治术语来说就是缺少革命精神，一点都不符合马克思主义。

数学和编程

举一个非常简单的例子。如果你说 $cos^2θ$ 表示 $(cos θ)^2$，那么理所当然，$cos^{-1}θ$ 就应该表示 $1/(cos θ)$ 了？可它偏偏不是！别被数学老师们的教条和借口欺骗啦，他们总是告诉你：“你应该记住这些！” 可是你想过吗：凭什么？ $cos^2θ$ 表示 $(cos θ)^2$，而 $cos^{-1}θ$，明明是一模一样的形式，表示的却是 $arccos θ$。一个是求幂，一个是调用反函数，风马不及，却写成一个样子。这样的语言设计混淆不堪，却喜欢以“约定俗成”作为借口。
如果你再多看一些数学书，就会发现这只是数学语言几百年累积下来的糟粕的冰山一角。数学书里尽是各种上标下标，带括号的上标下标，x，y，z，a，b，c，f，g，h，各种扭来扭去的希腊字母，希伯来字母…… 斜体，黑体，花体，双影体，……用不同的字体来表示不同的“类型”。很多符号的含义，在不同的子领域里面都不一样。有些人上一门数学课，到最后还没明白那些符号是什么意思。
直到今天，数学家们写书仍然非常不严谨。他们常犯的一个错误是把 $x^2$ 这样的东西叫做“函数”（function）。其实 $x^2$ 不是一个函数，它只是一个表达式。你必须同时指明“$x$ 是参数”，加上 $x^2$，才会成为一个函数。所以正确的函数写法其实看起来像这样：$f(x) = x^2$。或者如果你不想给它一个名字，可以借用 lambda calculus 的写法，写成： $λx.x^2$。

建议：

• 可以参考C语言，引入头文件。按照标准的学科分类把符号进行分层分级，整合成为一系列标准符号库，然后像C一样在论文或者学术文章里进行引用。
• 可以参考C++语言，引入namespace。
• 必须确保符号一致性，比如右上角的角标如果是实数那就只代表幂次，这个具体在头文件里定义。

无论怎样，这都不是一蹴而就的事情，因为习惯很难改变，而这件事又没有显著的短期利益。可能随着符号体系越来越臃肿，直到人们受不了了才开始思考改变。

从根本上说，数学和计算机科学的融合是未来的趋势，符号体系的改进是迟早的事。

上课

任何一门课上课之前都进行一次“摸底考试”，试题内容是这门课这学期所有要讲的比较难的那部分综合知识。满分100分，依据考试成绩分三个档次：

1. 0-60分者，每节课都要来，要点名；要按时交作业，和现在所有大学里的考勤制度一样。
2. 61-80分者，每节课都要来，要点名；但不用强制性地交作业；交作业那部分的平时分按照（得分 / 100) x 交作业那部分的平时分总分来算。
3. 81-100分者，不用强制性地来上课，不用点名；也不用强制性地交作业；平时分按照（得分 / 100) x 平时分总分来算。

最后的期末考试都还是一样的。

这样一来，才能真正做到“有教无类，因材施教”。

这样一来，部分学生也就不用浪费这么多时间在他们早就会的课上了（关于这个问题我问过我校教学秘书，教学秘书给的答复是：“必修课就算会了还是得去上，也不能免修，不然没学分”）。

其实以上是一种比较折中的办法，我真正希望的是：上课爱来不来，作业爱交不交，期末考试见真功夫。

学知识，学的是知识本身，而不是这样那样的形式。有人可能会说，不强制上课的话有些人根本就不学这门课了，对此，我从正反两方面来说。一方面，保证学生主动去学习的不是上课，而是期末考试。因为期末考试这个关卡存在着，学生不得不去学习。君不见，每当期末考试来临前图书馆人满为患。另一方面，有些学生确实不想学说明这个专业就不合适，就应该找到自己适合的专业然后转专业，关于转专业这个下面说。

转专业

为什么要限制转专业呢？这个问题我想了很久都没想明白，前段时间刚刚想明白。之前没想明白是因为我想问题的角度没对，我是站在学生的角度想的：完全开放转专业，把转专业的门槛降低到最低，能最大化激发学生的学习兴趣和学习效率，提高整体的教育效率。并且管理上其实真的不难，技术实现上也不难，就是一个数据库的事儿，这么多麻烦事都做出来了这个就不能做？

但是，从宏观层面来说，具体原因很复杂，和人口、市场、产业链等等有关，也有一定的官僚因素在里面。

那么，有没有什么完美的解决办法？我目前没想到，我要能想到教育部的领导早就想到了。但我还是想写出来，让更多人看到。

实验报告

有些学校的部分课程的实验报告非得手写，连代码都要手写，无力吐槽。然后还是用的旧版Word，实验报告模板也排版混乱，无力吐槽。非得手写完打印出来，本来整块的时间就被实验报告给切碎了。

对此我建议简单的实验报告统一用Markdown来写，比Word方便太多了。然后生成PDF或者HTML文件发电子档给老师，这样既美观又快捷，都21世纪了干嘛非得打印出纸质档来呢？既麻烦又不环保，对吧。

起因是在网上看到了这么一篇文章:千万不要一辈子靠技术生存 ，我承认，说的是事实。但我想就其中几点说说我的想法。

在看下文之前，我希望你先仔细地看完那篇文章，这样你才清楚我想表达什么。

如今有一种思想，认为要想在中国混得好，主要得靠人脉。这是事实，也是从来就如此的，但是，从来如此，便对么？

要八面玲珑，要见风使舵。要学会人情往来，要知晓人情世故。小时候，我是不喜欢这样的，那时候天真，觉得世界可以很简单很美好。长大了些，发现世界上有很多“灰色”，社会的运作规律并不是我们理所当然以为的那样，渐渐地我也开始察言观色，开始见人说人话，见鬼说鬼话。现在，我越来越觉得，社会本不应该这么复杂，我们可以改变，我们只是不敢改变。

一、在中国你千万不要以为学习技术就可以换来稳定的生活和高的薪水待遇，你更不要认为那些从事市场开发，跑腿的人，没有前途。

为什么在中国就千万不要以为学习技术就可以换来稳定的生活和高的薪水待遇？

因为中国目前是“关系社会”。哪怕是在象牙塔里，你可能也能窥得一二，更别说社会上了。

为什么那篇文章的作者要在前面加上“在中国”三个字？

因为那篇文章的作者也清楚，在真正尊重科学技术的国家里，学习技术就是可以换来稳定的生活和高的薪水待遇。

二、在学习技术的时候千万不要认为如果做到技术最强，就可以成为100%受尊重的人。

如果看过原文，你就会知道这句话的前提是这个人其他方面都正常，并不是说恃才傲物之类的。也就是说，一个各方面都算正常的人，在自己领域的技术上做到了最强，也不会成为100%受尊重的人。为什么？很简单，因为人们根本就不尊重科学技术，哪里还会尊重科学技术工作者？

朋友们你知道吗?不管你技术有多强，你也不可能自由的腾出时间象别人那样研究一下LINUX源码，甚至写一个LINUX样的杰作来表现你的才能。需要做的就是按照要求写代码，写代码的含义就是都规定好，你按照规定写，你很快就会发现你昨天写的代码，跟今天写的代码有很多类似，等你写过一段时间的代码，你将领略：复制，拷贝，粘贴那样的技术对你来说是何等重要。(如果你没有做过1年以上的真正意义上的开发不要反驳我)。

这段话不知道你们读着感觉怎样，我只说说我的感觉。我感觉到了一个原本热爱技术的人，在工作后发现原来领导们并不管他技术怎么样，领导们需要的只是一颗能完成既定任务的螺丝钉，而他一边为了KPI消耗着自己的热情，一边羡慕着Linus Torvalds所处的环境，久而久之，不得不接受了现实，然后转过身劝告下一代的新人：“放弃你的幻想吧，去做一颗螺丝钉”。

三、你更不要认为，如果我技术够好，我就自己创业，自己有创业的资本，因为自己是搞技术的。
如果你那样认为，真的是大错特错了，你可以做个调查在非技术人群中，没有几个人知道C#与JAVA的，更谈不上来欣赏你的技术是好还是不好。一句话，技术仅仅是一个工具，善于运用这个工具为别人干活的人，却往往不太擅长用这个工具来为自己创业，因为这是两个概念，训练的技能也是完全不同的。
创业最开始的时候，你的人际关系，你处理人际关系的能力，你对社会潜规则的认识，还有你明白不明白别人的心，你会不会说让人喜欢的话，还有你对自己所提供的服务的策划和推销等等，也许有一万，一百万个值得我们重视的问题，但你会发现技术却很少有可能包含在这一万或一百万之内，如果你创业到了一个快成功的阶段，你会这样告诉自己：我干吗要亲自做技术，我聘一个人不就行了，这时候你才真正会理解技术的作用，和你以前做技术人员的作用。

这篇文章也有我比较同意的部分，比如这第三点。

但是，我能想象这样一个社会：那不是一个以人际关系为主导的社会，而是以科学技术为主导的社会。有技术就能创业，因为所有中间过程都由一个统一的公正的透明的中间机构来处理，科学技术工作者不再需要知晓那些乱七八糟的潜规则，做到真正的“按劳分配，各取所需”，这才是真正的社会主义。但毕竟我们中国正处于并将长期处于社会主义初级阶段，未来的路，还长。

不管你是学习技术为了找工作还是创业，你都要对技术本身有个清醒的认识，在中国不会出现Bill Gates，因为，中国目前还不是十分的尊重技术人才，还仅仅的停留在把软件技术人才当作人才机器来用的尴尬境地。

是的，正因为中国目前还不是十分的尊重技术人才，所以所有的技术人才必须先自己尊重自己！这是一切革命（是的，你没看错，就是革命，一场决定中国近未来科技发展速度的思想革命）工作的前提。

“尊重知识、尊重人才”是邓公提出来的。

1977年5月24日，邓小平与中央两位同志谈话时指出：“我们要实现现代化，关键是科学技术要能上去。发展科学技术，不抓教育不行。靠空讲不能实现现代化，必须有知识，有人才。”，“一定要在党内造成一种空气：尊重知识，尊重人才。”这是对“文革”极“左”思潮泛滥时期盛行的“知识越多越反动”、“知识分子是臭老九”等谬论的有力批驳。它为当时教育、科技战线的拨乱反正指明了方向。从此，“尊重知识”、“尊重人才”以及重申“知识分子是工人阶级的一部分”成了新时期党的知识分子政策表述的代表性口号。

“科学技术是第一生产力”也是邓公提出来的。

1988年9月，邓小平同志根据当代科学技术发展的趋势和现状，在全国科学大会上提出了“科学技术是第一生产力”的论断。邓小平同志的这一论断，体现了马克思主义的生产力理论和科学观。“科学技术是第一生产力”，既是现代科学技术发展的重要特点，也是科学技术发展必然结果。

科学技术工作者在这个革命中失去的只是锁链，我们获得的将是整个世界。

全世界科学技术工作者，联合起来！

我接触网络也快十年了，深感国内烂书太多，垃圾信息太多，愚昧之人太多。

于是愤而写下此文，是为了提醒自己，也是为了分享给你。

言语过激之处还请见谅。

如何获取信息

• 专业相关的问题少用百度，多用Google或Bing。有问题上网查是好习惯，但别把“百度一下”当成习惯。
• 社会热点、争议话题、娱乐八卦等等看看就好，不看更好。
• 今日头条、抖音、快手这三个APP别碰。除非闲的没事干只想消磨时间。
• 少关注微博或者知识星球上的那些大牛，跟牛人走得近不代表自己也就牛了。
• 别指望通过微信公众号或者知乎学习知识。长长见识，开开眼界可以，但系统的知识还得看完整的教程。
• 要会翻墙，墙外有更广阔的天地，前提是政治觉悟要过关，因为外网上有迷惑人的意识形态输出（虽然国内也有吧……）。

如何学习知识

• 开阔认知 ≠ 学习知识。仰望星空的同时也要脚踏实地。
• 懂了 ≠ 会用。实践出真知。
• 虽然生活中总是时不时冒出一大堆琐碎事，但尽量别用碎片化的时间学习。给自己腾出整块连续时间学习。
• 别成为一个学习资料的“收藏家”。
• 只会用“死记硬背”的方式来学习的话大概率会失去信心。
• 别做“伸手党”，很多资料自己其实找得到，说不定找的还更好。
• 学会看答案之前自己先思考。
• 做任何事最好都追求一种优雅和极致，否则很“廉价”。
• 别相信什么《XX天速成XXX》，这些只能入个门。
• 只是囫囵吞枣地读完一本教材，约等于没读。
• 要多学习高阶的、抽象的知识，别以为只需要用简单的知识和技能加上不断拼命重复现有的工作，就会成功。
• 要善于通过网络获取学习资源。
• 很多时候，并不是学不会某个领域的知识，而是缺少这方面的热情。

如何提升格局

• 要看大的趋势，别只看眼前的一亩三分地，否则很容易沦为井底之蛙。比如，要看到计算机和互联网改变人类社会的趋势，而不是死盯着工资和房价。
• 别相信一夜暴富和“快速挣钱秘籍”，赌博和传销别碰（除非你是高手），股市和数字货币也没大众想的那么简单。
• 别跟别人比较，众生平等。所有的区别都是建立在个人后天被人类社会赋予的观念基础之上，破除这种观念，走自己的路。
• 偶尔丧一丧，完全可以，但尽量别让“丧”成为常态。
• 也别看了上一条就觉得“青春就是用来拼的”，一昧使蛮力还不如丧着好。
• 新事物会代替旧事物，这是普遍规律。固守旧事物拒绝学习新事物，大概率会被时代淘汰。
• 适合自己的、能让自己觉得舒服的学习方式才是最好的。自以为是的“努力”换来的大概率是现实无情的打击。

正确地获取信息 -> 高效率地学习知识 -> 沉淀、升华、进而提升格局 -> 得到成长。

这是我偶然在网上看到的一篇文章，深以为然。原文如下，译文在后。

原文

来源：https://zachholman.com/posts/how-github-works-hours/
作者：Zach Holman

Hours are bullshit

Hours are great ways to determine productivity in many industries, but not ours. Working in a startup is a much different experience than working in a factory. You can’t throw more time at a problem and expect it to get solved. Code is a creative endeavor. You need to be in the right mindset to create high-quality code.

Think back to the last time you were depressed or angry. How productive were you? Now think back to the last time you were truly productive. Code flying from your fingertips. Not just the sheer quantity- the sheer quality of that code. When you’re in the right mindset, your best day of coding can trump weeks of frustrated keyboard-tapping.

We want employees to be in the zone as often as possible. Mandating specific times they need to be in the office hurts the chances of that. Forcing me in the office at 9am will never, ever get me in the zone, but half of GitHub may very well work best in the morning.

By allowing for a more flexible work schedule, you create an atmosphere where employees can be excited about their work. Ultimately it should lead to more hours of work, with those hours being even more productive. Working weekends blur into working nights into working weekdays, since none of the work feels like work.

A day

Everyone at GitHub is different. I don’t really have an “average” day, but this is a close approximation:

• Wake up around 10am, check Campfire logs, clear overnight support tickets
• Bus into work and grab lunch around noon or 1
• Work from 1pm to somewhere around 6-9pm at the office
• Go home and work/relax from my couch until 2am, or:
• Go out and drink with coworkers (more on this later)

We have a contingent of (insane) people who come into work around 7am, we have some who come in at 3pm. We have some who are more productive at home. You don’t have to come into the office every day if you don’t feel like it (although most of the time everyone comes in).

Why is our day so “loose”? Because 1) working in chat rooms lets us work when and where we want, and 2) we want to create an environment where people are most productive. There’s no one work day that fits everyone’s productive hours, so we don’t enforce one.

Enforcement

We’re currently at 35 employees and growing, and this approach still works great. But managers love to assign hours for a reason: it gives them the illusion that hours can measure performance.

If you don’t go hard on hours, you do have to look at different metrics. How good is their code? Are they fixing bugs? Are they involved in work, or is the greater flexibility not motivating them?

It’s difficult to make these qualitative judgements, but they’re still going to be more valuable than “did this guy put in his ten hours of work today”. Because as soon as you make it about hours, their job becomes less about code and more about hours.

译文

小时制是扯淡

小时制是决定许多公司生产率的好方法，但不是我们的。在创业公司工作与在工厂工作的体验大不相同。你不能把很多的时间扔在某个问题上，然后期望它得到解决。编程是一种创造性的努力。你需要以正确的心态才能创造高质量的代码。

回想上次你沮丧或生气的时候。你有多有成效？现在回想一下你上次真正有成效的时候。代码在你指尖飞舞。不只是绝对的数量——也是绝对的质量。当你处于好的状态时，你一天的创造胜过数周机械地敲键盘。

我们希望员工尽可能的处于这种状态中。规定他们在办公室的具体时间会减少这种可能性。强迫我早上9点在办公室里永远不会让我处于那种状态，但在GitHub会工作得很好。

通过允许更灵活的工作日程，你可以营造一种员工对他们的工作感到兴奋的氛围。最终，它会导致更多的工作时间，这些时间甚至更有成效。把工作日和休息日混在一起，让工作感觉不再像工作。

一天

GitHub 的每个人都是不同的。我真的没有”平均”的一天，这只是一个近似：

• 上午 10 点左右醒来，查看 Campfire 日志，清除夜间支持票
• 坐公交车上班，正午或1点左右吃午餐
• 在办公室从下午1点到下午6-9点左右工作
• 回家，工作/放松到凌晨2点，或者：
• 与同事一起出去喝酒（稍后介绍）

我们有一组（疯狂）的人在早上7点左右上班，我们有一些人在下午3点上班。我们有一些在家里工作效率更高的人。如果你不喜欢，你不必每天都进办公室（尽管大多数时候每个人都会来）。

为什么我们的日子如此”散漫”？因为 1） 在聊天室中工作，让我们在需要的时间和地点工作，2） 我们希望创造一个人们工作效率最高的环境。没有一个工作日程适合每个人的作息时间，所以我们不强制统一时间。

强制

我们目前有35名员工并且还在增多，并且这种方法仍然很有效。但是管理者喜欢分配工时是有原因的：这给了他们一种幻觉，让他们觉得工作时长可以衡量绩效。

如果你不在工作时间内努力，你确实得看看不同的指标。他们的代码有多好？他们正在修复漏洞吗？他们是否参与工作，或者更大的灵活性没有调动他们的积极性？

很难做出这些定性判断，但它们仍然比”这家伙今天投入十个小时来工作”更有价值。因为一旦你用时长来评判，他们的工作就变得与编程本身关系不大，而与耗时关系更大了。

HelloOS

虽然说我是电子信息工程专业的，平时学的基本是硬件和MCU，但我比较偏向软件，思来想去，写一个操作系统算是比较贴近这个专业，而且应该也挺有意思的。

写这个操作系统并不是拿来用的，我想没人会使用一个本科生写出来的操作系统吧。写这个操作系统的主要目的是学习计算机底层原理，把计算机知识融会贯通，还可以拿来做毕设。

不是在Linux内核上删删改改，而是真正的从零开始写一个“麻雀虽小，五脏俱全”的64位操作系统出来。

写应用程序可以借助丰富的库函数支持，而写操作系统则一切从零开始。为此，我进一步学习了计算机组成原理、操作系统、x86 Assembly、ANSI C和GNU C。

因为遇到不会的地方还得现学，平时还要上课、做项目等等，所以开发速度会很慢很慢很慢……

对了，我的操作系统得有个名字吧？就叫HelloOS吧！灵感来源于HelloWorld。

开发环境

写操作系统需要nasm汇编器和bochs虚拟机，因为微软的masm汇编器在64位Win10下已经不能用了，并且bochs能调试虚拟机内的操作系统，那就重新安装一个CentOS虚拟机专门拿来写操作系统吧。登陆官网一看，居然CentOS 8都出来了！安装！安装完之后发现屏幕分辨率总是800x600，太小了，更改了设置之后重启还是800x600，更改设置然后重启了几次都是这个分辨率，上网查发现是xrandr配置问题，毕竟这是CentOS 8的第一个版本，可能还有bug，那就换成之前的CentOS 7吧。CentOS 7我没安装GUI，而bochs虚拟机最好需要一个GUI，于是乎我开始安装GUI，Gnome感觉太臃肿了，最后决定用Xfce，然而似乎安装不了，源出了一点问题，又换源，换成阿里的折腾半天感觉太麻烦，索性不用CentOS了！我还有个Ubuntu，开启Ubuntu安装nasm和bochs很顺利，然而因为bochs的配置是基于命令行的，我又是自制操作系统，虚拟硬件环境配置问题很多，于是乎，卡在了第一步……

想了想，主要是虚拟机软件和汇编器这两个软件，虚拟机软件有现成的VirtualBox，汇编器就比较麻烦，微软官方的masm已经不能运行在64位的Win10下了，emu8086又不支持一些我需要用到的伪指令，最后抱着试一试的心态上网一查，欸嘿！nasm居然有64位Windows版本的！太好了！终于可以开始写操作系统了！

BootLoader

写操作系统不是一件容易的事儿，因此我需要找一本适合开发操作系统的参考书。一开始找的是川合秀实写的《30天自制操作系统》这本书，写得是很不错，最后完成了一个多任务带窗口的32位操作系统。但问题是这本书年代有点久远了，工具链早就更新换代了，而电脑也早已进入64位的时代了。我想最后能写一个64位的操作系统，于是又找找找，找到了田宇写的《一个64位操作系统的设计与实现》，感觉还不错，于是就用这本书当参考书了。

当然，还是得从16位的8086实模式到32位的保护模式再到64位的IA-32e，不能一步登天。

同理，一开始我用虚拟软盘而不是虚拟硬盘，因为软盘的逻辑比较简单。这里选用3.5英寸的标准软盘格式，2个磁头，每个面80个磁道，每个磁道18个扇区，每个扇区512字节，所以初始容量是2 x 80 x 18 x 512 B = 1474560 B = 1440 KB

简单说一下计算机启动过程：首先，计算机上电后主板BIOS进行硬件自检以及初始化，然后查找并调用显卡BIOS程序，显卡BIOS进行初始化，这时候屏幕就有画面了。接着主板BIOS会查找其它设备的BIOS程序，找到之后同样要调用这些BIOS程序来初始化这些设备。一系列初始化完成之后CPU的CS:IP被设置指向逻辑地址0000:7c00处的指令，开始执行0000:7c00处的程序（为什么是0000:7c00，这要问当年Intel的BIOS工程师们）。通常这里的程序被称为BootLoader，还不是kernel。BootLoader和kernel的关系就像运载卫星的火箭与被火箭运载的卫星之间的关系一样。

第一个BootLoader程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

    org 0x7c00

start:
    mov ax, cs
    mov ds, ax
    mov es, ax
    mov ss, ax
    mov sp, 0x7c00

    ; clear screen
    mov ax, 0x0600
    int 0x10

    ; set focus
    mov ax, 0x0200
    mov bx, 0x0000
    mov dx, 0x0000

    ; display
    mov ax, 0x1301
    mov bx, 0x000f
    mov cx, 10
    mov dx, ds
    mov es, dx
    mov dx, 0x0000
    mov bp, StartBootMessage
    int 0x10

    ; reset floppy
    xor ah, ah
    xor dl, dl
    int 0x13

    jmp $

StartBootMessage:
    db "start boot"

    times 510 - ($ - $$) db 0x00
    db 0x55
    db 0xaa

这个程序只实现了Boot没实现Loader，先看看能不能运行。编译出来只有512B，一开始我总想着要填满1440KB因为软盘容量就是1440KB，然而当我抱着试一试的心态把这个512字节的程序加载进虚拟机开机运行的时候，奇迹出现了！

成功运行~

从开始写这篇文章（9月10日）到今天（10月13日），一个多月过去了，期间上课写作业做项目然后断断续续地学习操作系统相关知识，到今天总算能在虚拟机里面看见我写的程序成功运行了。感觉万里长征终于走完了第一步……

上面那个程序是参考的书上的，但那个jmp $让我感觉很不好，因为会占用CPU，应该换成hlt更好。实验了一下，果然如此：

这是jmp $版本的结果。可以看到，CPU 1（从0开始计数），就是被VBOX选中执行HelloOS的那个，跑到了100%，电脑上的风扇不一会儿就转得更快了。

这是hlt版本的结果。可以看到，几乎不耗费任何CPU资源。

待续

时光荏苒，白驹过隙，接触编程正好两年了。总结一下我用过的一些软件吧。

编程之路

C

Microsoft Visual C++ 6.0 -> Visual Studio 2017 -> Code::Blocks 17.12 -> Sublime Text / Visual Studio Code

一开始当然是受了谭浩强那本“经典”教科书的影响，用的VC6。我不想再吐槽VC6的落后了，毕竟是上个世纪的IDE，不过我不后悔用过VC6，因为没有对比就没有现在的思考嘛，并且我用VC6的时间也不长。如果现在还有谁用VC6写C，那么我不得不怀疑他/她的C水平。

之后用了一段时间的VS2017，不得不说VS2017比较臃肿，而且对于一个刚开始学C的人来说，大部分功能都用不上。

后来我又找到了CodeBlocks，这个IDE还算不错，开源跨平台，代码高亮、自动补全也还行，最主要的是比较轻量（年轻的我尚且还不知道Sublime）。

Java

Eclipse -> Sublime Text / Visual Studio Code

Eclipse相信是很多初学Java的人的第一个IDE，我也不例外。但启动还是不够快，有时候写个测试类我用记事本+命令行都比它快。

Python

IDLE -> PyCharm -> Sublime Text / Visual Studio Code

IDLE是Python附带的一个简单的IDE，如果现在还有谁用IDLE写Python，那么我不得不怀疑他/她的Python水平。当然，有一种情况下是很适合用IDLE的，那就是初学Python的时候。IDLE简单的功能和直白的界面能让初学者专注于Python本身。

之后用了一段时间的PC，同VS2017一样，比较臃肿，而且对于一个刚开始学Python的人来说，大部分功能都用不上。

HTML + CSS + JavaScript

DreamWeaver -> Sublime Text / Visual Studio Code

不知道为什么，我就是不习惯那些大而全的IDE，比如VS2017，比如PC，比如这里的DW。根本原因在于我还只是处于入门的阶段，很多的功能我都用不上，写程序的主要目的是练习而不是工程性质的开发。当务之急是学习更多编程语言本身的知识乃至计算机的基础理论而不是怎么用工具。

如你所见，以上的编程语言（HTML和CSS不算）最后我都是用的Sublime Text / Visual Studio Code，原因很简单：轻巧、快捷。小的、临时的、测试性的程序我用Sublime写，大的、长期的、工程性的程序我用VS Code写，这两个严格来说都只是编辑器，但可以配合各种插件达到和IDE差不多的效果而且高度定制化，美滋滋。

软件之道

这是我现在电脑上全部的软件：

Code是编程或专业相关的，Tool是工具类，Game是游戏类。我觉得我在说废话。

注意那个红色背景的和黑色背景的，不一般。

下面我逐一介绍一下，软件名加粗的是我喜欢的。

Code

• Wolfram Mathematica：神器。请看Mathematica——万物皆理
• Android Studio：写Android的。
• MATLAB：写MATLAB的。说到MATLAB，我不得不吐槽一下它那像是大一新生才能写出来的函数命名，不过MATLAB的精髓不在于写程序而在于它那（据说）很强大的工具箱。
• DrRacket：写Scheme的。

这第一排都是IDE。

• Keil uVision5：开发51单片机和STM32的。
• PZ-ISP：普中烧录软件。用Keil写好程序后用这个烧录进51单片机里。
• Altium Designer：画原理图和PCB的。
• NI Multisim：电路仿真的。

这第二排都是和嵌入式开发相关的软件。

• NetLogo 6.0.4：请看NetLogo建模之美
• NetLogo 3D 6.0.4：同上。
• Behaviorsearch 6.0.4：同上。
• HubNet Client 6.0.4：同上。

这第三排都是和计算机模拟复杂系统相关的软件。

• VirtualBox：轻巧但强大的虚拟机软件。
• Unity：开发游戏的（虽然我下载了下来就没动过……打算有空了玩玩）。
• Cygwin：Windows下的Linux shell工具。
• Git Bash：同上，不过比较轻量，专注Git。

这第四排都是和“虚拟”这个概念相关的软件。

• Visual Studio Code：我常用的编辑器之一。
• Sublime Text：我常用的编辑器之一。
• Typora：写Markdown的利器（虽然我经常用Sublime写）。主要是它的即时预览很不错，还能在Markdown、PDF、HTML、LaTeX、Word甚至图像之间进行转换。
• TeXmacs：请看TeXmacs：一个真正“所见即所得”的排版系统。

这第五排都是文本编辑器。

Tool

• Inno Setup：制作安装包的。
• Mathpix Snipping：这个就厉害了，能够通过神经网络识别手写的数学公式然后给出LaTeX源码，某些时候非常方便。
• aiXcoder：一款利用AI自动补全代码的插件。
• Zeal：函数手册大全，什么语言都有。

这第一排都是编程相关的小工具。

• TIM：QQ的精简版，比QQ轻聊版还精简。
• 网易云音乐：听歌的。
• 幕布：记笔记、写提纲的（虽然我习惯用Sublime或者Typora）。
• 格式工厂：进行格式转换的小工具。

这第二排都是实用软件。

• 百度网盘：不解释。
• PanDownload：百度网盘下载太慢了就用这个。
• 迅雷极速版：没有广告的早已绝版的迅雷（我保存了安装包哈哈哈）。
• Teleport Pro：爬网站的，有这个还写啥爬虫啊。

这第三排都是和下载相关的软件。

• 计算器：Windows 10 自带的计算机，还可以。
• Snipaste：截图神器，比Windows或者TIM自带的截图好用多了。
• GifCam：录gif的。
• Captura：录屏的。

这第四排后三个都是演示会用到的。

• 网易有道词典：翻译的，划词翻译比较方便。
• Everything：找文件的。
• EncodeConvert：批量编码转换的。
• Bandizip：解压/压缩。

这第五排都是比较实用的小工具。

• Word、Excel、PowerPoint、OneNote：Office2016正版。

话说pdf转word怎么做？直接右键->打开方式->Word。

Game

• 仙剑奇侠传四：情怀。
• Golly：玩元胞自动机的。
• kodoyuri：百合文字游戏。
• SpaceEngine：太空引擎，偶尔看看还是不错的。
• MineCraft：情怀。

都是广义上的游戏。

啊，终于介绍完了，不容易啊，写了一天……

这篇文章应该算是我的一个心血了……

这些软件都是很好用的，能大大提升效率，此即为“软件之道”。

这篇文章的灵感来源于释放比特自由

原文片段节选：

CA模拟股市

可能更多的人关心的是Wolfram的新科学有什么用呢？这的确是一个很有争议的问题，因为你既可以说NKS非常有用，也可以说它什么都不能做。

我们都知道，简单程序可以模拟自然界的生长现象，例如雪花的形成、树的生长、动物表面上的花纹等等。运用细胞自动机还可以模拟自然界的一些复杂的非线性过程，例如复杂的流体、交通流等。然而，这些应用其实又回到了一般计算机模拟的老路上，即针对具体问题，赋予每一个比特一定的意义，然后让系统去演化。

然而，NKS强调的是忘掉模拟和比特的意义。这样一种哲学会给我们带来什么好处呢？下面这个简单的应用会给我们耳目一新的感觉。

该应用研究是想用CA生成一个时间序列曲线，然后用这个曲线去拟合股票的价格波动，它是由Wolfram公司的研究员Jason做出的。

考虑一个特定的细胞自动机，例如CA90（对1维的、邻居为两个的细胞自动机的编号，确定了一个编号就确定了它的一组规则），它形成的图形和一个时间序列曲线，如下图：

上面的是CA90的运行情况，下面的是它生成的时间序列曲线

这个时间序列曲线的具体做法是，将每一步CA90生成的黑细胞方格作为1，白细胞方格作为-1，然后对所有方格求和，得到该时刻的总的数值s(t)，然后在下一时刻，同样求得这样一个总和数，把这个数加上s(t)，得到s(t+1)，这样反复不停的运用这一方法就能得到一个上图所示的时间序列曲线。

进一步，Jason考虑由两个细胞自动机混合得到的时间序列。例如给定两个细胞自动机CA90和CA110，然后我们把它们进行一定比例的混合。例如混合比例是3:7。具体做法是，从任意一个随机初始条件开始演化3步CA90，然后再演化7步CA110，这样我们得到一个混合的细胞自动机，Jason叫它ICA，用同样的方法，可以画出这个ICA生成的时间序列曲线：

下面，Jason就用这个生成的时间序列曲线去拟合真实的股票价格数据。具体方法可以是通过调节两种细胞自动机的混合比例，例如从3:7调到8:2，使得生成的序列能够和真实数据在均方误差的条件下拟合的很好，如下图：

Jason试了很多种两两细胞自动机组合的情况，都能够得到较好的拟合曲线。然而，很奇怪的是，这个方法并没有对股市建立任何显式的模型。

这个研究的意义在于，即使我们完全忘掉股市运行的内在规则，我们仍然可以找到拟合股票数据的方法。这反过来说明了复杂的行为并不一定需要复杂的微观机制。仍然是那个观点：从某种意义上说，行为的复杂性增加到一定程度就停止增长了。

我的想法：

黑和白可以认为是两种力量：黑代表 混乱/暴力/邪恶/深邃/冷峻，白代表 秩序/和平/善良/天真/温暖。这两种力量在CA90的规则下演化。

为什么要两种规则呢？要知道，股市其实是各方利益集团博弈后的一个综合结果，而股市的规则是顶层的那些组织制定的，组织是由人组成的，而人会变，组织的核心利益也会随之改变，股市规则也就随之改变了。

CA90和CA110可以认为是两种顶层力量（规则制定者）的博弈，这种博弈会在一个较短的时间内保持平衡，当比例恰好符合现实中的博弈结果后，自然大体上也就符合真实的股市了。

来源：http://swarmagents.cn.13442.m8849.cn/vm/articles/foreordination.htm
作者：星新一 著 李有宽 译

不知从什么时候起，这个星球上就有了机器人。这儿是机器人的一统天下。也许是由于大气压中含有某种有毒成分吧，在整个星球上找不到任何有生命的动植物，只有机器人在到处活动着。除此以外，就是一望无际的奇岩怪石，乌黑如墨的海洋人……

这些机器人不知疲倦地努力工作着，挖掘出大量的矿石并加以冶炼，进行加工，制作出各种各样的零件，然后把这些零件装配成和自己一模一样的机器人，连镌刻在躯体表面的号码都完全相同。

无论是大雨滂沦、水流成河的雨季，还是滴水成冰的严寒隆冬，机器人们从未休息过，始终是勤勤恳恳地埋头工作着。在不懈的努力之下，机器人的数目不断地增长着。

有时候，机器人也会互相谈论起一个问题来。

“我们为什么会存在于这种地方的呢？”

“首先，在这片陆地上出现了最初的第一个，然后，那个家伙就像我们现在这样，开始进行增添伙伴的工作，于是就产生了我们大家。除此以外的事情就不知道了。”

——最初的第一个，这是事实，并非神话。机器人的电子头脑极为填密精细，容不得半点含糊不清或加以美化的想法。

机器人每制造出来一个新的伙伴，就把自己的全部记忆都输入对方的电子头脑之中。因此，无论是谁都知道这件事情。这样一来，最初的第一个究竟是谁这个问题就无法解决了。因为大家的知识是均衡平等的。有关最初第一个出现以前的记忆在电子头脑里没有留下一丝一毫的印象，完全是一片空白。这里的所有的历史都是从那个时候开始的。如果从那以后的事情来考虑的话。可以推测，当初的第一个不可能是从天而降的。但是这又没有什么根据，只不过是一种假设而已。并且，机器人们在某种本能的愿望的驱使下，不顾一切在热衷于增添伙伴的工作，并不过多地考虑这件事情。

可是，一旦达到了某个数目以后，机器人们就停止了增添伙伴的工作。当然，决不会开始寻欢作乐，嬉戏游玩的。机器人们全力以赴，转入了制造宇宙飞船的工作。

与似前相比，这是一项更为艰难困苦的工作。从地面上开采大量的矿石，加以破碎，并对矿石进行精炼，然后制造出各种极其复杂的零件。为了获得宇宙航行所必需的能源矿藏，机器人们不得不挖掘了一个非常深的矿井。曾经有过好几次因为井壁塌陷而前功尽弃，不得不从头开始挖掘。但善于吃苦耐劳的机器人们全然不顾从井壁里渗透出来的污水，毫不停息地日夜奋战在井下。兢兢业业地挖掘着宝贵的能源矿藏。

有时候势不可档的狂风暴雨呼啸着卷地而来，有时候惊心动魄的落地响雷隆隆不息，有时候天崩地裂般的强烈地震此起彼伏。但勇敢的机器人齐心协力地向极其恶劣的自然条件作着艰苦的斗争，奋不顾身地建造着宇宙飞船。虽然不知失败了多少次，但仍然是毫不泄气，信心百倍：决不肯放弃这一计划。

“为什么我们如此热衷于这项工作呢？”

“这是由于某种义务感或者说是责任感在鞭策着我。这是一种无论如何也无法抑制的冲动。如果能够制作成功，乘坐着宇宙飞船到星星的海洋里去邀游的话，肯定会遇上许多有趣的事情的。难道你们不想到宇宙之中去吗？”

“啊，当然想去啦！虽然说不出什么理由，但必须把飞向宇宙作为我们的最高目标。也许这可以称之为宿命或者命运吧。”

经过长期的艰苦奋斗，宇宙飞船终于制造出来了。每个机器人都折腾得焦头烂额，缺手断脚，破烂不堪，已经再也找不到一个完好如初的机器人了。

在这种情况下，大家只好推选了一个相比之下伤势最轻的机器人乘上了宇宙飞船。在全体机器人的注目送行之下，宇宙飞船出发了，尾部喷射着鲜亮的火焰腾空而起，向着茫茫太空直奔而去。

一旦到了完全失重的太空之中以后，这个机器人的电子头脑中就发生了某种变化，一种新的想法油然而生。于是，机器人便准确无误地指引着宇宙飞船沿着一条航线前进，在不计其数的星球中选定了一个明确的目标。

机器人驾驶着宇宙飞船，穿透死一般的寂静，在虚无缥缈、广袤无垠的太空中努力地向着那个唯一的目标前进，前进，不断地前进！十万火急，刻不容缓！也不知从什么地方来的一股巨大的力量，宇宙飞船的速度越来越快，已经达到了最大限度。

最后，太空旅行结束的时候终于来到了。毫不犹豫，立刻着陆！可是，不知什么缘故，着陆缓冲装置突然发生了故障，宇宙飞船并未减速，呼啸着冲向大地。一声惊天动地的巨响，所有的一切都变成了大大小小的碎片，翻滚旋转着向四处飞散。

远处响起了震耳欲聋的欢呼声，人们从四面八方如同潮水一般蜂涌而来。其中有一个声音格外响亮，那是一位拿着麦克风的男子在拼命地呼叫。

“诸位，请安静一下，请安静一下！终于有一个勇敢的机器人凯旋归来啦！这是本世纪规模最大的竞赛！我们向每个星球上都派遣了一个机器人，并且按照不同的号码向大家发售了彩票，看哪一个机器人最早返回地球。这是一场史无前例的大：很抱歉，让大家翘首踏足、望眼欲穿地盼了好久，但现在这位勇士终于冲破重重艰难险阻，胜利返回了地球。如果您手中持有的彩票上的号码与这个机器人的号码相同的话，那就是万分幸运地中了头彩，立刻就能得到一笔数目极其惊人的巨款……”

机器人已经粉身碎骨，再也无法用电子头脑进行思考了。如果电子头脑能够进行正常的工作的话，那么听到这番话以后……

——即使一切都完好无损，并且能够听懂刚才的那些话，机器人也决不会产生任何感想的。因为所有这一切都是按照事先设计好的程序进行的，并没有发生丝毫差错。