Max-flow min-cut (最大流-最小割定理)

最大流-最小割定理是网络信息流理论(Network infomation flow)的基石。这个定理我的理解就是“多粗的管子,水就最多多大流量”,比如从自来水厂到用水大户工业小区A 能达到的水的最大流量是多大?考虑到可能从水厂到小区有不少到达的水管,那么最大的流量等于拆掉最少最细的水管后水厂不能给小区A 供水的那些水管流量的集合。当然这种说法并不不严谨,因为这里水管不是双向的,而在网络中谈论的信息流却可是是双向的。下面详细介绍最大流—-最小割定理。

继续阅读

希腊英雄排名

在介绍希腊英雄之前普及下希腊神话中英雄的小知识。和中国神话中盘古开天辟地前的混沌一样,在希腊神话中混沌之中诞生了第一位神—地神盖亚(gaia),盖亚是女神,生下了天神乌拉诺斯。盖亚和乌拉诺斯又生下了三个独眼巨人,三个百臂巨人和十二泰坦神(六男六女)。十二泰坦神之一的克洛诺斯(Uranus,众神之怒2 中满身岩浆的终极boss)在母亲盖亚的怂恿下杀死了父亲乌拉诺斯,成为新的天神,克洛诺斯和自己姐姐十二泰坦神之一的瑞亚结婚,为防止出现和自己父亲的情况发生,克洛诺斯将自己的子女们都吃了,最小的儿子宙斯在母亲瑞亚的保护下成长并推翻了父亲的统治,成为新的天神,因为杀手锏是雷电,故也称雷神。

一般而言,神和神生下品质优良的还是神,品质较差的则是怪兽(一般为英雄和神所杀),神可永生,并具有较强魔法技能。神和人所生为半神,为英雄(Hero,物理攻击比较强悍)或者巫师(wizard,具有神的部分魔法技能)。

继续阅读

Cuckoo Hash 布谷鸟哈希

布谷鸟哈希最早于2001 年由Rasmus PaghFlemming Friche Rodler 提出。该哈希方法是为了解决哈希冲突的问题而提出,利用较少计算换取了较大空间。名称源于该哈希方法行为类似于布谷鸟在别的鸟巢中下蛋,并将别的鸟蛋挤出的行为。它具有占用空间小、查询迅速等特性,可用于Bloom filter 和内存管理。

算法描述

算法使用hashA 和hashB 计算对应key 的位置。

  1. 当两个哈希任意位置为空,则选择一个位置插入
  2. 让两个哈希有位置为空时,则插入到空位置
  3. 当两个哈希位置均不为空时,随机选择两者之一的位置上keyx 踢出,计算踢出的keyx 另一个哈希值对应的位置进行插入,转至2执行(即当再次插入位置为空时插入,仍旧不为空时,踢出这个keyy)

图例

1. 插入key1 两个位置均为空,则插入任意位置.

1

2. 插入后

2

3. 插入key2 两个位置有一个位置为空,则插入空的位置中

3

4. 插入后效果

4

5. 新插入keyi 发现对应两个位置均被占据

 

5

6. 随机选择一个位置提出所在位置的key(key1),将踢出的key 放置在另一个哈希结果对应的位置上

6

7. 如果踢出的key(key1)又占据/踢出了其他key(keyj)的位置,则反复执行上面的过程直到结束

7

其他

  1. Cockoo hash 有两种变形。一种通过增加哈希函数进一步提高空间利用率;另一种是增加哈希表,每个哈希函数对应一个哈希表,每次选择多个张表中空余位置进行放置。三个哈希表可以达到80% 的空间利用率。
  2. Cockoo hash 的过程可能因为反复踢出无限循环下去,这时候就需要进行一次循环踢出的限制,超过限制则认为需要添加新的哈希函数。
  3. 在SOSP 11 的SLIT 文章中有使用Cockoo hash。

增加哈希表过程如下:

当新插入一个key hashA 在上面哈希表位置和hashB 在下面哈希表的位置分别被key1 和keyx 占据,任选一个key 提出(这里选择key1)。

11

计算key1 hashB 的值然后插入到下面的hashB 对应的哈希表中。

 

12

PS

文中图使用graphviz 绘制,图例第七张图片生成文件如下:

   1: digraph G {

   2: "node0" [

   3: label = "<f0>null | <f1>null | <f2>keyi | <f3>null | <f4>null | <f5>key1 | <f6>key2 | <f7>......"

   4: shape = "record"

   5: ];

   6: 

   7: "node2"[

   8: label="key1"

   9: ];

  10: 

  11: "node3"[

  12: label="key2"

  13: ];

  14: 

  15: "node1"[

  16: label="keyi"

  17: ];

  18: 

  19: "node1"->"node0":f2[color="red",shape="record",label="hashA"];

  20: "node1"->;"node0":f6[color="red",shape="record",label="hashB"];

  21:  

  22: "node0":f2->;"node2";

  23: "node0":f5->;"node2"[style="dotted"];

  24:  

  25: "node0":f2->;"node3"[style="dotted"];

  26: "node0":f6->;"node3";

  27:  

  28: "node0":f5:s->;"node0":f7:s[color="blue",shape="record",label="keyj"];

  29: }

在GVEdit 在使用的时候,F5 是生成图片,并在对应的目下生成了响应的图形文件,相关设置在Graph setting 里面,第一次用的时候总是找不到export image 的方法,总导出不了对应图片。

我的自白书

翻之前的日志发现了08 年写的稿子:


和长辈说话时,他们往往会议过去种种,常常计算自己的一生之中时间是如何流淌过去的,有多长的时间花费在学习上,有过多少时间沉溺于游戏人生,有多少时间花费在亲人和朋友身边,无论是为没有虚度人生而宽慰,还是因碌碌无为而不安,生命中的黄昏总让他们感到不安和遗憾,即使是朝气蓬勃的年轻人,不也为自己的未来或暗淡或迷茫而苦恼么?难道不会为与一起步入大学校门的好友至今却感到恍若隔世的巨大差距而懊悔么?走过人生的每一级台阶,我们或欣喜、或骄傲、或繁忙、或彷徨、或懊悔、或痛苦。我们异或为逃脱惩罚而庆幸,异或为他人超出自己许多而抱怨上天的不公。每个人的想法都是大同小异的,而与此相应我们却会发现人生的轨迹会小同大异。

  二十余年的记忆仍旧觉得匆匆和短促,我不惧去怕死亡和衰老,我却害怕自己年岁大后会不记得现在的自己,我也害怕未来的自己想起现在的自己而多生懊悔,但我尽力去保持住记忆中那最鲜艳的部分,虽然鲜艳背后的灰色半点同样挥之不去,那又会是些生么呢?有时是盛夏长江边的楼顶上,相伴的是抚面的江风和远处发电站隐约的轰鸣、年久失修的隔热层、白天晒化又凝固的陈沥青,踏上去总会给孩童许多额外的惊喜,没有城市亮化工程带来的光污染,亦没有城市建设带来的空气污染,一切洁净得让繁星都起了倦意……不久迁到了城市,在这个陌生的环境中我慢慢的体会成长的痛苦,我也第一次有了回忆过去,因为环境、性格、家庭等原因,我深深被一种情愫所折磨,在四面恶意和伤害中捕捉偶尔闪现的善意和机会,或是友谊或是给予我的善意的期待,就像在黑暗中不停碰撞受伤从没有想象在阳光下会是如何,而一切都只会象倾盆大雨过后的头盔盛满的水,多年过后,我才发现失去的不仅仅是几年的时间、更是在心理上失去了某些本来属于我的东西,而这也将一直影响着我,后来,自己也渐渐学会了一个词汇去描述当时的情愫,这个词就是无助。

   江边城市的天气总体就象我的生活一样波澜不惊的平和,可是真正的突袭一场暴风骤雨也会让你对它改观很多。这种天气通常在午后,瞬时的天气变化令原本阳光明媚的气氛完全打乱,天空变得如同昼夜,风会击碎玻璃夹杂着碎片划伤同学,电压会因为电线的摇摆变得不稳定甚至中断,于是一切似乎都在一瞬间被破坏,一切又都在一瞬间改变。在记忆中也就是那一瞬间,一天早晨起来,对着镜子发现自己长高了不少,也发现脸上不知从何冒出了小痘痘,当发现自己身边环境又完全改变时,我告诉自己,不回避但不关注过去,即使无法决定要走向何处,但我努力做好我自己。接下来的记忆也就是最清晰的部分,这里有叫我多去观察的老师,告诉我面包会有的、房子会有的。还有一起上黄山,爬庐山的朋友和一段段美丽和激动的情感,其中失败和挫折过后的些许快乐就如同晌午空寂的校园的广播中放送着你最喜爱的beyond的歌曲。

  在百多年历史的九江一中里度过了我的高中三年,高一经历了学校的百年校庆,觉得中午免费的午餐特别美味,高二800 米穿着钉鞋昏天暗地跑了第一名的我,高三,看着和自己一起学竞赛的同学报送到了北大(上了college 才发现当时的自己还不够获得成绩的觉悟),失衡了段时间,后来,时间又是同样平静的把我推倒了华中科技大学的门口。

   我大步的跨过了这扇门,而也学明年我又将同样平静而从容的跨过这扇门,过去的几年里,我迎面接受了许多,有些事情做后不久我便能辨别自己做错了或对了,而许多事也许只有期待未来的我来评判,最后还是老套的用萨特的话来结尾:人,就是他行为的全部,这也许最能概括现在的我,因为我在走我毕生都未走过的路。

If you miss the train I’m on,You will know that I am gone

Five hundred miles 是最喜欢的英文歌曲之一,淡淡的忧伤和惆怅中讲述了一个外出工作的男人,在没有挣得钱后害怕也没能力回到自己的家乡,见到自己的爱人,仿佛就像一个落魄的铁道工人圣诞前夕在自己工作的铁路上走着,口袋没有一分钱,没勇气回家。火车从身边一趟趟地飞驰而过,笛声渐近又渐远,这火车上会有自己的爱人么?会不会离自己越来越远呢?……此情此景,这个工人想到了离开家时的情景,不也是这样么——自己在火车上向她们道别,恋恋不舍,自己当时却对未来充满期望,希望能够富足而归,衣锦还乡,结果却是现在此般穷困潦倒。怎么不能叫同样身处异地,为事业和爱情奋斗的人唏嘘感叹、伤感酸楚呢?

歌词中“一百里,两百里,三百里…五百里”和“away from home”反复出现,声音低沉缓慢,无不表现了歌中人对家的眷恋,而“no penny to my name”和“no shirt on my back”却又说明了他穷困潦倒的尴尬处境。道出了外乡人在异地的人生酸楚。

继续阅读

如何开发一个chrome 插件

一、新建一个空文件夹,创建manifest.json 文件

新建文件夹名字是应用的名称,manifest.json 是应用的一些信息,我们以插件scholarsea为例,文件夹名为scholarsea,对应的的manifest.json 如下所示,具体内容参考chrome 扩展文档。

   1: {

   2: "name": "Google Scholar \u641c\u7d22",

   3: "version": "0.1",

   4: "description": "use Google Scholar to find the paper you selected",

   5: "icons": { "48": "4848.png" }, 

   6: "page_action": { "default_icon": "1919.png" },

   7: "background_page": "background.html",

   8: "permissions": [ "contextMenus","tabs" ],

   9: "background_page":"background.html"

  10: }

 

二、为你的应用找一个好看的图标

在文件夹下放你的图标,和manifest 中属性相同。我是的19×19 和48×48 大小的png,还不错吧!自己PS的哦

  1919这个是右键时显示的图标   4848这个是插件介绍用

 

三、新建一个html 文件和manifest 中html 属性一致

内容很简单包含一个后面要用的js 文件,这个js 文件名可以随意

   1: <script src="js.js"></script>

 

四、新建js 文件

这里js 文件名和上面html 内js 文件名一致,用于执行插件的核心工作。scholarsea 将所选的文字作为关键字在Google scholar 进行搜索。内容如下:

   1: //open new tab to search

   2: function searchdblp(info,tab){

   3:     var url="http://scholar.google.com/scholar?hl=en&q=

   4: "+info.selectionText+"&btnG=&hl=en&as_sdt=0%2C5"

   5:     window.open(url);

   6: }

   7:  

   8: //add right button click

   9: var menutitle="Google Scholar \u5e2e\u4f60\u641c"

  10: var parent= chrome.contextMenus.create({"title": menutitle,

  11: "contexts":["selection"],"onclick":searchdblp,});

chrome.contextMenus.create 在浏览器邮件添加一个选项,名称为“Google Scholar 帮你搜”,当点击后调用函数searchdblp ,info.selectionText 是我们在浏览器所选的内容。

 

五、发布插件

看看我们这个名为scholarsea 的文件夹下有了哪些内容:

image

最后只需要在chrome 中发布即可,在chrome 的菜单中选择“工具/扩展程序”,然后打包扩展程序即可。这样会生成一个crx 类型的插件安装文件,和一个pem 的密钥文件(用于管理你的插件)。因为所有插件都是源码开放的,需要确认这个插件是你所有的只有这个密钥了。

 

六、一点注意

在上面没有提到重要一点是manifest 和js 内都不支持中文,采用的是unicode 编码,如果你需要写中文的话,请用unicode 编码,有个简单的中文转unicode 的编码方法,如果你装了python 的话就好办了,看看我怎么解决的

   1: >>> u"帮我搜"

   2: u'\u5e2e\u6211\u641c'

   3: >>> u"搜索此人"

   4: u'\u641c\u7d22\u6b64\u4eba'

看到了吧,很方便哦~~

最后提供两个插件,用于搜索作者的文章dblpsea,和google scholar 搜索文章的插件:

dblpsea】  【scholarsea