Coding Honor Logo

CODING HONOR

programming and critical thinking

Dev Notes 01

These days I am trying my best effort to adapt to the new environment. A lot of things need to learn, a lot of people need to know.

During this period, I read a number of articles. Some of them are really good ones and worth to record here.

git

Most of my spare time is spending on reading git related articles, which is well worth. After a lot of reading, finally, I got agreed with the point of view that we should “Commit Often, Perfect Later, Publish Once”.

1 Commit Often, Perfect Later, Publish Once: Git Best Practices

Git is amazing for its free branching, so we’d better make use of this. After learning from the article below, we could become a guru in git branch technology.

2 A successful Git branching model

At last, there is a very cool site, where we could find some really good tutorials and articles about git.

3 https://www.atlassian.com/git/

linux performance

There are many very useful tools in linux. I have a chance to use several of them during the work, like: strace, ltrace, pdb, etc.

Above is a detailed “Linux Performance Observability Tools” diagram, from here:

5 http://www.brendangregg.com/linuxperf.html

unit test

Before joining this team, I seldom wrote unit tests. So there are lots of things I need to catch up. There are two articles about BDD test:

6 Introducing BDD

7 Mocks Aren’t Stubs

timing and profiling

When I tried to analyze my python code, these tools (lprun, mprun, timeit, etc) in IPython help a lot.

8 Timing and Profiling in IPython


That’s all.

正则表达式中的IP提取与质数判断

本文介绍两个正则表达式的应用实例,希望能有所帮助。

IP提取

判断IP是否合法的正则表达式网络上有很多,一般只需注意IP的数值边界就可以。以下就是Java中该类正则表达式的写法:

1
((2[0-4]\\d|25[0-5]|1\\d\\d|\\d\\d?)\\.){3}(2[0-4]\\d|25\\d|1\\d\\d|\\d\\d?)

但直接用上面的正则表达式抽取文本文件中的IP存在一个问题,虽然这里考虑了0-255边界的问题,但诸如“Current IP: 2255.0.0.1”中的“2255.0.0.1”还是会以“255.0.0.1”的方式被抽取出来。实际上这是一个不合法的IP,并不应该被匹配。

为了解决这个问题,考虑过用正则表达式中的零宽度匹配。不过这里给出的是另外一种解决方案,利用正则分组的方式。代码如下:

IP Extract
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
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test {

  List<String> extract(String line) {
      List<String> ret = new ArrayList<>();
      if (line != null) {
          String regex = "(^|[^\\d])(((2[0-4]\\d|25[0-5]|1\\d\\d|\\d\\d?)\\.){3}(2[0-4]\\d|25\\d|1\\d\\d|\\d\\d?))";
          Pattern p = Pattern.compile(regex);
          Matcher m = p.matcher(line);
          while (m.find()) {
              ret.add(m.group(2));
          }
      }
      return ret;
  }

  public static void main(String[] args) {
      String line = "Current IP: 192.168.1.1, 2255.0.0.1 and 1.0.0.0";
      System.out.println(new Test().extract(line));
  }

}
Console Result
1
[192.168.1.1, 1.0.0.0]

质数判断

除了常规的字符串抽取以外,正则表达式还可以做一些以前我根本没有想到过的事情,比如这里的质数判断。

Prime Valid
1
2
3
boolean valid(int num) {
  return num >= 0 && !String.format("%0" + num + "d", 0).matches("^0?$|^(00+?)\\1+$");
}

利用的是能否被其它数整除来做,思路挺巧妙的。具体解释这里就不作说明了,网络上有大量的介绍文章。每次看到这种近乎于炫技的代码,自己虽然不排斥,但过后总会思考,这些到底算不算茴香豆的四种写法。

Morris二叉树遍历算法

背景

二叉树的前中后序遍历算法是计算机领域的基础算法,一般采用递归或者栈来实现。时间复杂度为O(n),空间复杂度为O(logn)。1968年,Knuth提出说能否将该问题的空间复杂度压缩到O(1),同时原树的结构不能改变。大约十年后,1979年,Morris在《Traversing Binary Trees Simply and Cheaply》这篇论文中用一种Threaded Binary Tree的方法解决了该问题。

Threaded Binary Tree

为了实现O(1)空间复杂度的遍历,Threaded Binary Tree对普通二叉树进行了一些改造,将每一个节点在中序遍历时的前驱节点的右子树指向自己。说起来比较绕口,不过参考下面的示意图就会马上明白是怎么回事。

Morris算法在遍历过程中动态的构建Threaded Binary Tree,同时在结束时又将树恢复原样,在满足O(1)空间复杂度的同时也恰好满足Knuth对树结构不能改变的要求。

前序与中序遍历

下面给出前序遍历的Morris实现,程序最核心的部分是寻找每个节点的前驱节点,并根据前驱节点右子树是否为空来决定当前节点是否被访问过。

Preorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<Integer> preOrder(TreeNode root) {
  List<Integer> ret = new ArrayList<>();
  TreeNode cur = root;
  while (cur != null) {
      if (cur.left == null) {
          ret.add(cur.val);
          cur = cur.right;
      } else {
          TreeNode pre = cur.left;
          while (pre.right != null && pre.right != cur) {
              pre = pre.right;
          }
          if (pre.right == null) {
              pre.right = cur;
              ret.add(cur.val);// 前序遍历
              cur = cur.left;
          } else {
              pre.right = null;
              cur = cur.right;
          }
      }
  }
  return ret;
}

中序遍历与前序遍历相似,只需要将第15行的 ret.add(cur.val) 添加到第19行 cur=cur.right 的前面就可以了。掌握了前序和后序遍历的O(1)空间复杂度实现,大家可以暂时停下来想一想,我们该如何实现后序遍历?

后序遍历

算法思想与前序和中序遍历一致,只不过我们需要添加一个新的根节点,这个新的根节点的左子树为原树的根节点,右子树为空。假设当前节点为cur,在遍历完了cur.left的左子树以后,我们逆向遍历从cur.left到cur的中序遍历前驱节点间的所有节点,这样就可以实现cur的左子树的后序遍历。因为最开始我们添加了一个新的根节点,它的左子树是原树,所以可以保证最终我们能够得到整个树的后序遍历。

Postorder Traversal
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
List<Integer> postOrder(TreeNode root) {
  List<Integer> ret = new ArrayList<>();
  TreeNode cur = new TreeNode(-1);
  cur.left = root;
  while (cur != null) {
      if (cur.left == null) {
          cur = cur.right;
      } else {
          TreeNode pre = cur.left;
          while (pre.right != null && pre.right != cur) {
              pre = pre.right;
          }
          if (pre.right == null) {
              pre.right = cur;
              cur = cur.left;
          } else {
              pre.right = null;
              reverse(cur.left);
              TreeNode node = pre;
              while (node != null) {
                  ret.add(node.val);
                  node = node.right;
              }
              reverse(pre);
              cur = cur.right;
          }
      }
  }
  return ret;
}
Reverse
1
2
3
4
5
6
7
8
9
void reverse(TreeNode node) {
  TreeNode prev = null;
  while (node != null) {
      TreeNode next = node.right;
      node.right = prev;
      prev = node;
      node = next;
  }
}

时间复杂度

表面上看我们的程序中包含有两层的while循环,但实际上Morris算法的时间复杂度仍然是O(n)。对于前序和中序遍历,假设有n个节点,二叉树中的n-1条边每条边最多被访问2次。第一次是确定当前节点的前驱节点,第二次是从前驱节点返回到当前节点以后的再次访问。所以总体上来看,算法复杂度是O(2n)=O(n)。

对于后序遍历,因为比前序和中序遍历多了两次反转操作(reverse),这就导致每条边最多被访问4次,最终算法复杂度是O(4n)=O(n)。

总结

Morris算法虽然在时间复杂度上有着系数级别的差异,但却带来了空间复杂度量级上的降低。总体看来,在某些空间苛刻的场景中,该算法非常实用。

戚继光与俞大猷

最近翻历史,读到对比戚继光与俞大猷的一段文字时,觉得对于今人做事也有非常的借鉴意义,摘抄分享与君:

让战术全面现代化的建议,曾经被名将俞大猷提出过。他准确地指出,倭寇的特长是娴习陆战,水战的技术反而低劣。俞大猷主张,以有效的战船和火炮歼灭倭寇于海上,根本不让他们有登陆的机会。在战术原则上,在他所著的书里也明白指出:“海上战无他术,大船胜小船,大铳胜小铳,多船胜寡船,多铳胜寡铳而已。”他给总督的禀帖中,曾经请求把陆军军费的一半用来配备水师。但纵使俞大猷的声望和战绩都十分卓著,这些有益的建议却始终没有被采纳,因而壮志未酬,赍恨以殁。

然则俞大猷本人也不可能理解,他的建议,所牵涉的问题和将要引起的后果已经超出军备问题而及于政治。他要求亲自率领“闽广大船数百艘,兵数万”,如果一旦成为事实,有关各省的财政就要从原来小单位之间的收支而被集中管理。与之相应,这些后勤人机构的人员必须增加,而且必须一扫苟且拖沓的办事作风,保证规格和数字的准确,才能取得预期的行政效率以与现代化的军事技术相配合。而且和他们往来的各个机构,也必须同样地注重实际。然而我们这个庞大的帝国,在本质上无非是数不清的农村合并成的一个集合体,礼仪和道德代替了法律,对于违法的行为作掩饰则被认为忠厚识大体。各个机构之间的联系,从来也没有可资遵守的成文条例。俞大猷当然更不可能预见到,在未来的好几个世纪之内,上面这些情况在我们这个以农业经济为基础的国家里竟不能发生根本的改变。现代化的技术和古老的社会组织断然不能相容,要不是新的技术推动社会组织趋于精确和严密,那就是松散的社会组织扼杀新的技术,二者必居其一。

这种为个人力量所不可抗拒的社会因素,使俞大猷的计划毫无实现的希望。相形之下,戚继光的方案就比较现实。他没有去触动整个的国家体制,而只是脚踏实地,做他职责范围内力所能及的事。他从1559年开始招募3000名士兵。两年之后,兵员增加一倍,1562年更扩大为10000人。可是他的部队从来也没有一个后勤司令,也没有一个固定的军需处和兵工署。在整个国家机构之中,也没有委派过向他的部队作后勤供应的专职人员。他部队中的装备和武器,来源于各府县的分散供应。这种情况自然不能保持武器的质量。在戚继光的著作中,就明确提到各地所造的鸟铳铳管常有炸裂的危险,以致使士兵提心吊胆,不敢双手握铳以作精确的瞄准。有的火炮,铅弹与口径的尺寸不合;有的火炮,则导火线无法燃点。有鉴于俞大猷的壮志难伸和火器的实际情况,戚继光所拟打的战术仅仅把火器的应用限制在有限的范围内。他说:“火器为接敌之前用,不能倚为主要战具。”在练兵的后期,他规定12个人的步兵队配备鸟铳2枝,一局(相当于一连)的鸟铳手,必定要有一局的步兵“杀手”协同作战。

单纯的靠理想主义做事往往非常难成,以一己之力抗衡整个庞大的规则体系其中的阻力可想而知。知不可为而为之,精神是否可嘉尚且存疑(此处多出贪恋名誉之辈),更何谈目标达成。俞大猷的计划理论上来讲对于国家军事单位的现代化大有裨益,但考虑当时国家之状况,即便要完成此项任务,沿海诸民必然多得耐受数年倭寇之苦。

借鉴与当下,往小可类比做手机,往大也可类比实现国家的民主化进程。万不可像海瑞那样不识大势不懂循序,最后留得一个“志大才疏”的评价,唐捐了几十年的辛苦。

摘抄自黄仁宇《万历十五年》

帕尔哈提

帕尔哈提的酸奶子乐队在德国的表演

好声音第三季上最熠熠生辉的学员肯定是帕尔哈提了,至少他打动了我。

在当下,每个人都不停的被灌输做人需要有梦想。虽然对多样性的包容是社会进入文明的一个标志,可即便在这种语境之下,我们对于那些表达不清楚(或者干脆没有)自己梦想的人的包容也只是停留在礼节层面而已。骨子里,整个社会更欣赏那些怀揣梦想并坚持实现的人。虽无可厚非,但也使得我们的包容白璧微瑕。

“我没有什么梦想,就是很认真地做自己的事情。”

帕尔哈提在好声音的舞台上朴素的表达了自己,无论是音乐还是语言。这种朴素的表达令人醍醐灌顶。没有梦想却要装作有梦想来趋同于大环境是一件非常痛苦的事情,这往往也是不自信的一种表现。当帕尔哈提坦然的说出自己没有梦想就是认真做事的时候,顿时觉得这才是一个自信内敛的人该有的样子!

“99年我有个朋友问我,如果有机会去国外演出,你去哪儿?当时我跟他说德国。结果我十年以后就去德国演出了。我一直在弹、一直在唱,是梦想自己找我,不是我去找这个梦想。”

所谓的人格魅力,大抵如此。

传奇克洛泽

梅西或者C罗那样的天赋异禀必定令人羡慕,但克洛泽式的勤奋自律却注定更能激励人心!

在2014年世界杯半决赛德国对阵巴西的比赛中,克洛泽打进了自己世界杯上的第16粒进球,让他超越了罗纳尔多站在了世界的巅峰。

相比其他巨星,克洛泽除了体力以外其他资质并不算绝佳。而且在竞技体育行业里面,他偏偏入门又相对比较晚。21岁才签下第一份职业合同,之前没有任何系统的青训经历,是一个专业的木匠。不过这些都不能阻挡他最后成为德国战车的灵魂人物。

在追平罗纳尔多15球纪录时,克洛泽表演的前空翻落地并不是那么的顺利,令所有球迷唏嘘不已。可这会儿的罗纳尔多已经成了看台上的一名顾问,看着自己的队伍被德国战车冲的七零八落,他也只能有心无力。

克洛泽到今年36了,愈老弥坚,居然依然能在国家队和顶级联赛立足。他不断追求进步的职业态度堪称典范,值得所有人尊重。让我不禁想起了二郎,他们都是精益求精的职人典范。

人的成长要经历两个阶段:第一阶段是接受世界的不完美;第二阶段是接受自己的不完美。大多数人敢于接受世界的不完美,却不那么敢接受自己的不完美。至少从我的切身体会来讲,接受一个不太努力的自己是相当困难的。可事实如此,不努力就是不努力。不破不立,只有看清自己才能有所改变。

散列的探测次数

散列是一种用于以常数平均时间执行插入、删除和查找的技术,想必大家对此都非常的熟悉。但如果问每次插入、删除亦或是查找平均都需要几次探测时,不见得就有那么多人能迅速答出来了。本着Flaunt的目的,本文将会带领大家一探究竟。(这么简单的一句竟然两次目的得逞!星宿老仙,法力无边!)

理想的散列表数据结构只不过是一个包含有关键字的具有固定大小的数组,并将关键字从0映射到TableSize-1的数组空间中去。但有人的地方就有江湖,有数据的地方就会有冲突(我叫王家卫)。特别是当关键字数量无限数组空间大小已定时,冲突几乎是无法避免的。这时自然就需要一个专门处理冲突的大侠来主持公道了。

总的来看,这位大侠处理冲突一般有两种思路:

1.分离链接法:将所有散列到同一个值的元素保留到一个链表中,理论上可以插入任意多的元素。

2.开放定址法:冲突发生时,尝试选择另外的单元,直到找到为止。(大侠和的一手好稀泥!)

直观上来看,两种散列在实现效率上必定有所差异。如何来量化这种差异,便要引入平均探测次数的概念了。这里我们以开放定址法为例进行讨论。在冲突函数的选择上,由于线性探测、平方探测或者双散列都不是本文的讨论重点,所以采用随机冲突解法(理论上最优)。另外数组中数据的多少明显也会影响到插入或者查找时所需探测的次数,所以还得引入装填因子λ的概念。我们定义散列表的装填因子λ为散列表中的元素个数与散列表大小的比值。

有了这些铺垫后便可以探讨随机冲突解决方式的平均探测次数了。假设有一个很大的表,并且每次探测都与前面的探测无关(其实就是想表达随机探测的意思),首先让我们来看看一次不成功查找的期望探测次数。由于空单元所占的份额为1-λ,因此我们预计要探测的单元数是1/(1-λ)。一次成功查找的探测次数等于该特定元素插入时所需要的探测次数。当一个元素被插入时,可以看成是一次不成功查找的结果。因此,我们可以使用一次不成功查找的开销来计算一次成功查找的平均开销。

由于λ在0到当前值之间变化,早期的插入操作开销肯定较小,所以平均开销会相应有所降低,不是简单的1/(1-λ)。我们可以通过使用积分计算插入时间平均值的方法来估计平均值,最终可得:

$$ I(\lambda) = \frac{1}{\lambda} \int_0^\lambda \frac{1}{1-x} \mathrm{d}x = \frac{1}{\lambda} ln \frac{1}{1-\lambda} $$

明显小于前面的预计探测次数1/(1-λ)。根据公式,我们绘制曲线图比较了线性探测与随机冲突解决方法的性能优劣,如下图所示:

S为成功查找;U为不成功查找;而I为插入

使用线性探测方法插入与不成功查找的期望探测次数为0.5*(1+1/(1-λ)2),对于成功查找为0.5(1+1/(1-λ)),这里不做推导。

可以看出随机方法的成功查找平均探测次数显然优于线性探测方法(理论最优嘛!)。例如λ=0.5时,随机方法的成功查找平均需要1.39次探测,线性探测方法成功查找需要1.5次探测(插入需要2.5次探测)。如果λ大于0.75,线性探测所需的探测次数上升明显,已经非常不适合继续使用。这种情况下只能再散列或者使用可扩散列的办法解决散列表过满的问题。

打完收工!

所有内容均参考自《数据结构与算法分析 – C语言描述》

暴君

《暴君》的创意是我见过的电视剧中最棒的一部,这部剧让我兴奋。 — 李安

最近在看《暴君》这部美剧,由《国土安全》制作人 Howard Gordon、Gideon Raff 及《迷失》制作人 Craig Wright 共同制作,讲述一个普通美国家庭被卷入中东国家暴乱的故事。

二分查找

Donald Knutha computer scientist

逸闻趣事

计算机领域内人才济济,各路神仙竞相释放大招。创世神们的事迹就不一一列举了,单是那一个个优美的小算法,在我眼中也是一件件上古奇兵。

对没错,前面这段是欲扬先抑。虽然领域内的能人堪比北京的处级干部般多如牛毛,但依旧阻挡不住下面这件令我震惊的事的发生:

Donald Knuth在叙述查找算法的历史时指出,尽管第一篇有关二分查找(折半查找)算法的文章在1946年就发布了,可16年后才有人发表了(这是一个很好的限定)能正确查找各种规模的列表算法。

诸位感受下,这16年来的计算机界(至少是学术界),竟然连个简单的折半查找都没正确的实现出来。这至少说明有相当一部分的从业人员算法基本功是不过关的。当然,你可以说这不重要。但我觉得算法便如武侠世界中的内功,练得好绝对对以后修炼各派神功大有裨益。

说起老爷子,还有一段逸闻趣事值分享。当年老爷子觉得现有的排版系统不好开始制造Tex时,第一版的源码老爷子是写在一个很厚的笔记本上的!请注意,这里是一个真正意义上的纸质笔记本。

When I wrote TeX originally in 1977 and ’78, of course I didn’t have literate programming but I did have structured programming. I wrote it in a big notebook in longhand, in pencil.

Six months later, after I had gone through the whole project, I started typing into the computer. And did the debugging in March of ’78 while I had started writing the program in October of ’77. The code for that is in the Stanford archives—it’s all in pencil—and of course I would come back and change a subroutine as I learned what it should be.

看到这里时我已热泪盈眶,这六个月高老爷子到底是如何组织自己的代码的,这才应该是真正意义上的最强大脑。当然也可以理解这是一种偏执,见仁见智罢了。有时候不去过分的迷信权威其实对于破立是非常有好处的(推荐阅读王垠的《我和权威的故事》)。

那些坑

回到正题,接着说二分查找。究竟这里的二分查找难在什么地方,竟引得无数英雄折腰于此!我觉得这个问题至少存在以下3个坑(对那些基本功扎实的程序员来说:空中飘来五个字,这都不是事儿!):

1.中值的计算方式

这里最容易忽略的就是溢出问题。如果我们理所应当的认为,中值应该这样计算:

1
int mid = (high + low) / 2;

那么就肯定会被这种方式甩出一条街:

1
int mid = low + (high - low) / 2;

当然,如果你用这种方式,那明显会更好一些:

1
int mid = low + (high - low) >> 1;

这里核心的问题就是在避免两数相加以后 int 溢出的问题,后面的两种方式就很好的避免了这种情况的发生。第三种方式因为采用了位运算,在速度上更优。当然,别习惯性的在这里 >>2 就可以了。

2.选择区间是否对称

这又是一个让很多人栽倒的地方,边界问题考虑稍微有点疏忽,很容易就会掉进坑里。假如我们这里选择定义一个闭区间的话,那应该这样写:

1
int low = 0, high = n - 1;

相应的循环体应该是这样的:

1
2
3
while (low <= high) {
  // TODO
}

当然,这里你也可以写成一个半开半闭的区间:

1
int low = 0, high = n;

但对应的循环体就应该是这样的:

1
2
3
while (low < high) {
  // TODO
}

好多人在这里定义的时候想当然,没有仔细考虑边界,在循环条件是 <= 还是 < 的时候掉进了坑里。另外,如果这里采用指针的话,还存在另外一个问题,第一种闭区间的写法在计算 n-1 的时候容易指向一个无效地址:

1
2
3
int *low, *high;
low = a;
high = a + n - 1;

如果这个时候 n 是 0 的话,那又会妥妥的掉坑里。不过,这种情况对于半开半闭区间不存在问题。

3.重复元素的处理

大部分人在这里理所当然的认为找到就应该直接跳出循环体,根本没有考虑到重复元素这种情况。如果要返回的是第一个元素的话,那么简单的跳出肯定有问题。

最终的实现如下:

Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
public int binarySearch(int[] a, int v) {
  int low = -1, high = a.length;
  while (low + 1 < high) {
      int mid = low + ((high - low) >> 1);
      if (v > a[mid]) {
          low = mid;
      } else {
          high = mid;
      }
  }
  return high < a.length && a[high] == v ? high : -1;
}

小结

学习各种新的技术无疑对开阔眼界大有帮助,也可以让自己的工具盒里有着各式各样顺手的工具。但基础依旧是基础,经典依旧是经典。数据结构、算法、编译器、程序语言设计、操作系统等,对这些内容掌握的熟练程度,某种意义上决定了你在整个梯队中的位置。

Network Attacks

Facebook being massive DDOS attack by China showed on Norse Attack Timeline

This is the video on youtube.