LevelDB阅读笔记 之 SkipList

在leveldb中,插入与查找操作是高频操作、无删除操作。因此使用物理上线性的有序结构是不现实的,那么就是经典的二叉有序树及其变种,如AVL、红黑树甚至B\B+树,但这类数据结构都会牵扯到一个问题:随着节点的插入,需要频繁地进行平衡调节。而且为了保证线程安全,在平衡调节时需要锁住大面积地子树。而有一种以随机概率思想实现的类似平衡树的线性表结构:跳表,具体见论文继续阅读

MillWheel学习及持久化流式计算总结

MillWheel 是Google 2013年公开的其内部主要的流式计算平台,其与自己所在公司研发和使用的流式计算平台(TM)在设计本质上有相似之处,这里就借助对论文的解析,边阐述MillWheel的设计原理和亮点,边总结一下在设计上取“持久化”模式流式计算的技术特点。 继续阅读

SICP 读书笔记 - 构造抽象数据

SICP中的基础抽象数据与本科看过的一本算法书中提到的ADT有异曲同工之妙,即对数据用过程进行封装,数据的具体表现形式隐藏在过程接口下,用SICP的原话,这叫“抽象屏障”。如此,可以在保持操作接口不变的情况下,调整内部的数据实现形式。

相对于基础抽象数据与后面的带标志数据,让人震撼的是后面的数据导向的程序设计,这完全就是“代码确定规则,数据实现策略”的真实写照。即将由于程序属于一种逻辑范畴,一旦固定便难以只执行一种特定逻辑的局限性,通过数据(易调整,易加,易减)对程序进行边界扩展。用SICP中的原话:“可加性”,即可扩展性。目前,这种设计范式还不是特别熟悉,只是偶尔用一下,但其精髓还需要学习。

采用数据导向设计风格将通用型操作的系统实现了一把,在实现复数时看到TCP/IP协议栈分层的影子,由于SICP在80年代初即已在MIT作为教案被使用,因此可见分层思想影响之深远。其分层思路为:由于复数有两种形式(例如协调栈中某层有多种协议),因此,在打上复数标记“complex”前,需要将其具体复数类型(rectangular还是polar)打上。这样在查找操作表时,可由复数找到相关的复数计算,然后由具体复数类型找到其具体的计算方式。

在通用型操作的系统实现中,还发现了一个特殊的设计,但书中并没有着重强调,觉得这个设计也是数据导向设计的精髓之处:即操作所需要的参数类型作为查表中的维度。即二维表中:第一维是操作类型名,第二维是操作参数类型列表;两维确定唯一的操作过程。

后续添加扩展操作时,由数据导向设计带来的“可加性”之震撼,对得起近三个月晚上都献给SICP。读到后续的扩展跨类型操作时,看到“强制”策略,不免想到流式计算系统TM中使用ChunkFile向RefFile强制转换的策略。即进行跨类型操作时,可将“低“层次类型转换为”高“层次类型,这样就可以采取统一的操作进行处理(前提是类型间存在继承关系)。

后面提到的猜想:对类型的通用型操作处理,在没有知识表示与自动推理的帮助下,仅仅通过程序设计语言很难办到。首先,不清楚这里的知识表示与自动推理的准确定义是什么,不过看到这里,想到了公司最近在做的项目:类SQL-【ANTLR】->C++完成复杂统计报表的表达与计算是否在理论上就有障碍。

The Imitation Game

看完这部电影,愣愣地站在窗前半个小时没回神来,看着外面的路灯和树影摇曳的马路,任由思考蔓延。为Turing为人类作出如此大的贡献,却受到如此待遇而感到痛心,又联想到自己每日工作的基础-计算机-源头是这里,同时又想到Turing回答警官的话:机器与人的思考方式不同,就如同我们每个人思考方式不同一样,“机器是否可以如同人一样思考”- 这是一个傻问题。
每个人的思考方式的确是存在着不同,但在一个社会中,为了更好地与他人交流,人类从儿童便开始了趋同的练习。对于那些异类的思考方式,功利点说,不符合当前人类社会普遍的思考方式,就会进行有意或无意的打压和改造,而且这个过程对于一个个体,即有被动也有主动的形式。
因此,一个能再产生Turing的社会,必然需要有包容各种“异类”思考方式,甚至其它方面“异类”的环境和舆论氛围。

曾经与机器一起思考过,由于外部干扰,无法再与机器产生共鸣与对话;掌握并验证一个全新理论,而且还因此拯救了数千万人性命与国家命运的的人,确不为外人所认可和理解,想想该是多么的痛苦和无助,这也许已经超出了人所能的承受。

SICP 读书笔记 - 构造过程抽象

一、求平方根问题
 
虽然,以前使用递归解决过问题,但从未像使用scheme一样,如此直观地编写递归过程。
这也是一种自上而下地分解问题、解决问题的思维方式,即将一个复杂的问题按过程进行拆解。
递归求解问题,需要有一种接近解和结束递归的机制,否则计算过程将无限地递归下去。
接近解的机制是由数据性质决定的,即按照(y+x/y)/2递归下去,将无限地从x/2接近x的平方根;
而这个问题比较有意思的是,结束解的方式:
第一种,也是最容易想到的方式就是比较当前解与上一次解之间的差值,差值越小说明越接近解,因此可以取一个极小数作为阀值,如0.0001,当差值小于此阀值时,即表示可以接受当前解作为待求的平方根。
换句话说,这是一种用绝对距离来判断当前解是否接近真实解。从字面上也可以理解,绝对距离只针对某一区域有效。比如,如果求0.00001的平方根,那么很明显用0.0001这个绝对距离去度量针对0.00001的平方根的前后两次解,是不准确的(粒度太大)。因为由于接近解的分布非常密集,以至于任意相邻两个解的距离都会大于0.0001,从而无法得到较精确的解。
按理说,求一个大数,如果采用0.0001作为阀值终止计算,应该是可以了,实际是也存在问题。
原因就在于计算机实质是一种离散模型计算,这就导致计算机在表达实数集合时,只能妥协地采取地离散化表示。
即计算计中的浮点数(符号位:阶数:尾数)无法像数轴一样将所有的实数表达出来,对于大的浮点数,由于尾数数位有限,能将整数部分表达出来就错了,有时可能整数部分都要截断。
因此,如果一个数的平方根恰好为 计算机无法表达的数字,且其前后相邻的浮点数差值又大于0.0001,或甚至相差的都是整数部分,而非小数部分(小数表达不出来了)。这样,在递归计算时,可能就会在真实值左右来回计算,前后两次差值永远不会小于阀值。
仅从数学上说,一个绝对的阀值只会影响一侧的实数集计算,
即任意选一个数作为阀值,只会影响比其更小数的求解,但由于计算机的限制,对大数也产生了影响。
那么如何才能避免这个问题呢?
这时就体现了数学的魅力,我不用绝对距离,因为绝对距离只适用于特定区域。
由于上述公式是无限地逼近,相邻数之间的距离会越来越近,即(y1-y2)越来越小,同时由于上面推理我们知道这个差值会在实数的两个端相对于固定阀值不是太小就是太大。但无论你在哪个区域,如果快要接近解时,相对于那个区域的数值而言,变化会越来越小。即取其变化率:|y1-y2|/y1,即当前相对于上一个解变化了多少。以此来作为判断递归终止就将上述两个问题FIX掉了。

二、分钱问题

这是在讲树型递归过程的一个例子,即其递归计算过程展开平面上像一棵树一样,而且树中存在重复计算过程。
实际上就是动态规划中的0-1背包高级算法问题,但在SICP中却用来讲递归计算过程,可见SICP的高度。
SICP中有一句话,觉得算是解决分钱问题的核心思想:
“递归地归约为对更少的钱或更少的硬币种类的问题”
具体为将任何一种分钱分钱划分为两个集合:
1. 采用除x类型硬币外,其它硬币来分钱y
2. 采用所有各类的硬币,来分钱y-(x),其中(x)代表x类型硬币的面额,即先使用x类型硬币分了一次,剩下的钱再进行分
这样,每次剩下的钱再用上述这两个步骤进行计算,一直递归下去。
如同Fibonacci递归一样:
对问题进行递归拆解,但最后都必须要进行退化处理,否则会一直递归拆解下去。
即什么是终点,终点的计算值是多少。
对于分钱问题而言,由于有两个变量,即当前硬币种类k,和剩余的钱y。
那么枚举来看,无非有:
k >0 && y=0,这时是钱已分完,但还剩下几种类型硬币没用,算一种分法,所以应该返回1
k >0 && y<0,  这时是钱不仅分完,而且还出现负数,即上一种硬币分钱时,钱根本不够分的,所以这种分法失败,返回0
k >0 && y>0,  这时表示分钱还没进行完,需要继续应用上述递归算法
k =0 && y=0,  这时表示,硬币类型也用完了,钱也分完了,算一种分法,所以返回1
k =0 && y<0,  这时表示,硬币类型用完了,但上一次分钱失败,返回0
k =0 && y>0,  这时表示,硬币类型用完了,但钱也没分返回,即这种分法失败,返回0
k <0             ,这时表示,不管还有没有钱,硬币类型上次就没有了,分钱失败,返回0
即退化处理条件归纳为:
if k < 0,返回0
else
   y = 0,返回1
   y < 0,返回0
另外一个需要分析的是书中对硬币类型的处理,其原话是
“过程first-denomination以可用的硬币种数作为输入,返回第一种硬币的币值。这里认为硬币已经从最大到最小排列好了,其实采用任何顺序都可以”
 
即从上面两个递归子过程可以看出,计算关心的硬币类型x的面值|x| 和 当前剩余钱数;
同时从后面的退化处理可以看出,还关心当前还有多少种硬币类型没有使用。
因此,我们可以对硬币类型固定一个顺序,在所有的递归过程中都保持这个顺序,
这样能保证在递归树中,从根到叶子,对硬币的使用不会重复。
同时为了取到硬币的面值,书中就有了first-denomination这个函数,即在一个固定的使用顺序中:
剩余硬币类型个数 与 其将要使用的类型硬币面值 的映射关系。
这里蕴含这样一个常理:
对于一种分钱方式中采用的硬币类型,不同类型的使用顺序并不影响分钱的最终结果。
所以才有上面“采用任何顺序都可以”。

智能手机带给了我什么?

零零散散的一些事情,开始思考这个问题。从最近停用微信的朋友圈,到开始有意识地避免无意识地浏览手机,再到今早看见一个人一周读一本书的事情(其读书不在记忆知识,而在引起思考)。这些信息碰撞在一起,就触发了自己开始思考智能手机到底带给了我什么?
我想便利是毋庸置疑的:支付、打车、地图、即时搜索、即时购物、音乐。但细想起来,在智能手机上花费时间最多的不是这些带来便利的服务,是什么?
是无意识地浏览朋友圈、浏览论坛、浏览新闻,但再细想起来,这种快速消费的信息很少沉淀成知识、经验、甚至引发思考,更多的是一种娱乐。
再结合自己的读书计划的一次又一次的中止和达不到预期,再看看别人天天满世界飞,却能保持一周一本书的阅读量。现在看来,自己也许真的不是工作时间紧张,而是时间被一些意识不到的信息切走了。我想最近两年的智能手机上的各种无意识浏览算一个,而上学时的无意识地阅读各类书籍资料也算一个(尤其在图书馆,看到一类书籍,就读上几页,然后就在心里默想,这类知识要好好看看,然后就。。。奔下一个类别的书籍了)。