Browsed by
分类:程序设计

Huffman 编码压缩算法

Huffman 编码压缩算法

前两天发布那个rsync算法后,想看看数据压缩的算法,知道一个经典的压缩算法Huffman算法。相信大家应该听说过 David Huffman 和他的压缩算法—— Huffman Code,一种通过字符出现频率,Priority Queue,和二叉树来进行的一种压缩算法,这种二叉树又叫Huffman二叉树 —— 一种带权重的树。从学校毕业很长时间的我忘了这个算法,但是网上查了一下,中文社区内好像没有把这个算法说得很清楚的文章,尤其是树的构造,而正好看到一篇国外的文章《A Simple Example of Huffman Code on a String》,其中的例子浅显易懂,相当不错,我就转了过来。注意,我没有对此文完全翻译。

我们直接来看示例,如果我们需要来压缩下面的字符串:

 “beep boop beer!” 

首先,我们先计算出每个字符出现的次数,我们得到下面这样一张表 :

字符 次数
‘b’ 3
‘e’ 4
‘p’ 2
‘ ‘ 2
‘o’ 2
‘r’ 1
‘!’ 1


然后,我把把这些东西放到Priority Queue中(用出现的次数据当 priority),我们可以看到,Priority Queue 是以Prioirry排序一个数组,如果Priority一样,会使用出现的次序排序:下面是我们得到的Priority Queue:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (14 人打了分,平均分: 4.71 )
Loading...
rsync 的核心算法

rsync 的核心算法

rsync是unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的部分进行传送。rsync可拷贝/显示目录属性,以及拷贝文件,并可选择性的压缩以及递归拷贝。rsync利用由Andrew Tridgell发明的算法。这里不介绍其使用方法,只介绍其核心算法。我们可以看到,Unix下的东西,一个命令,一个工具都有很多很精妙的东西,怎么学也学不完,这就是Unix的文化啊。

本来不想写这篇文章的,因为原先发现有很多中文blog都说了这个算法,但是看了一下,发现这些中文blog要么翻译国外文章翻译地非常烂,要么就是介绍这个算法介绍得很乱让人看不懂,还有错误,误人不浅,所以让我觉得有必要写篇rsync算法介绍的文章。(当然,我成文比较仓促,可能会有一些错误,请指正)

问题

首先, 我们先来想一下rsync要解决的问题,如果我们要同步的文件只想传不同的部分,我们就需要对两边的文件做diff,但是这两个问题在两台不同的机器上,无法做diff。如果我们做diff,就要把一个文件传到另一台机器上做diff,但这样一来,我们就传了整个文件,这与我们只想传输不同部的初衷相背。

于是我们就要想一个办法,让这两边的文件见不到面,但还能知道它们间有什么不同。这就出现了rsync的算法。

算法

rsync的算法如下:(假设我们同步源文件名为fileSrc,同步目的文件叫fileDst

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (20 人打了分,平均分: 4.90 )
Loading...
用Unix的设计思想来应对多变的需求

用Unix的设计思想来应对多变的需求

之前,@风枫峰 在“这是谁的错?”中说过开发团队对需求来者不拒,而@weidagang 也在“需求变更和IoC”中说过用IoC来最大程度地解决需求变更。今天我也想从Unix设计思想的角度来说说什么是好的软件设计,什么样的设计可以把需求变更对开发的影响降低。(注意:这并不能解决用户或是PM的无理需求,面对无理需求,需要仔细分析需求,而用技术的手段无法搞定这个事,但是可以减轻需求变更带来的痛苦) 我曾经在《Unix传奇》的下篇中写过一些Unix的设计哲学和思想(这里重点推荐大家看一下《The Art of Unix Programming》,我推荐过多次了),以前也发过一篇《一些软件设计的原则》,不过,这些东西都太多了,记不住。其实,这么多年来,我的经验告诉我,无论是Unix设计,还是面向对象设计,还是别的什么如SOA,ECB,消息,事件,MVC,网络七层模型,数据库设计,等等,他们都在干三件事——解耦,解耦,还是解耦所谓解耦,就是让软件的模块和模块间尽量少地依赖起来。

现实当中的例子

让我先举几个现实生活中的例子:

1、现实社会中,制造灯具的工厂完全不关心制造灯泡的工厂,制造灯泡的工厂完全不关心制造灯具的工厂,但是,灯泡和灯饰可以很完美地组合成用户所喜欢的样子(这和@weidagang 在“需求变更和IoC”说到的那个PC的例子相仿)。他们是怎么做到的?

2、互联网上,做网站的人完全不用关心用户在用什么样的操作系统,什么样的客户端浏览器(当然事实上,浏览器的不标准让网站那边很头痛,这里只是举个例),反过来,上网的人也不关心做网站的人在用什么的技术开发网站。但是大家在完全不关心对方的情况下,可以很正常地协同工作在一起。为什么?

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (31 人打了分,平均分: 4.87 )
Loading...
挑战无处不在

挑战无处不在

面试过一些应聘者,当我问到为什么换工作的时候,他们都会告诉我,现在的工作没有挑战,无聊,所以想换一个有挑战的工作。于是我问了一下他的工作情况,发现那些有挑战的东西他还没有搞懂。我总是为有这样的认识的朋友感到惋惜,因为我总是认为有挑战的东西无处不在啊,不能因为工作上没有,自己就放纵了自己。比如,面试过一个做地图的工程师,他的工作是做计算地图上任意两点的最短或最优路径的一部分功能。我觉得这个事很有挑战,也有难度,应聘者说,没什么挑战,因为他做的东西只是调用相关的算法库。他在这个项目干了2年了,当我问他有没有看过算法库,知不知道地图是怎么存储的?他却告诉我,因为没有去做,所以就没有去了解,等做的时候再了解(我希望有这样想法的人都去看看程序员的谎谬之言还是至理名言?)。这样的例子很多,很多应聘者在面试中不能和我一起解决某个问题的时候,比如:OOD,数据库设计,系统设计,等,他们都会告诉我,不好意思,因为没有做过相关的事情,所以就不懂了,所以,他需要一个像我们这样的项目来学习和锻炼。我并不要求你能解决你所不擅长的问题,但毕竟数据库,OO,系统设计都是软件开发的基础知识,多少要懂一些吧。

但另外一方面,他们都会告诉我他们对技术充满和热情和兴趣,有着很强的学习能力,也有很能吃苦的态度。这也许是某面试宝典上看来的,面经上可能都会说,如果面对不能作答问题,可以说一下自己的态度和决心。可惜的是,我并不这么想的,我在我的两篇关于招聘的文章里(我是怎么招聘程序员的再谈我是怎么招聘程序员的)都说过一些我对如何择人的想法。这里重点说明一下其中两个观点:

  • 关于热情和态度,说白了就是不要给自己找借口。比如:“工作忙事多没时间学所以可以不懂”,“工作中没用到所以可以不懂”,“工作没有挑战,一直没有遇到合适的项目”等等。时间可以挤,工作之余可以学,随时随地去思考,挑战是无处不在的…… 想想那些你有热情的事,你会发现,几乎没有什么可以阻止你去做那些事。
  • 对于某些事情,如果以前没有在你身上发生过,那么这个事情在未来也不会发生。如果你以前没有对你接触过的东西去学习,去深挖,去思考,去改善,那么我不会相信你会在未来面对新的东西的时候也会有这样的态度;如果你以前没有用业余时间学习一些项目之外的东西,那么我也不会相信你会在未来会这样做;如果你以前没有把你的热情和态度转换成你的知识,经验和成果,那么我也不会相信你会在未来能做到。

这两个观点可能太刻薄了,但是,当我回想我自己的经历的时候,观察程序员的成长过程的时候,我发现,优秀的程序员都是相似的,当他们还在是一个菜鸟的时候,就已经有各种成为高手的苗头了,这些苗头就是——他们热爱思考,喜欢解决难题,对新鲜事物非常好奇,总是找人讨论,可以用自己的业余时间狠命研究很多和工作无关的技术,会在业余的时间里写些有趣的小程序,或是会把自己的思路书写下来,等等,等等

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (52 人打了分,平均分: 4.87 )
Loading...
需求变化与IoC

需求变化与IoC

感谢 Todd投递本文 – 微博帐号:@weidagang

需求又变了,怎么办?

先上一个轻松的段子:

程序员XX遭遇车祸成植物人,医生说活下来的希望只有万分之一,唤醒更为渺茫。可他的Lead和亲人没有放弃,他们根据XX工作如命的作风,每天都在他身边念:“XX,需求又改了,该干活了,你快来呀!”,奇迹终于发生了,XX醒来了,第一句话:“需求又改了?”。

这个段子用幽默的方式反映了需求变化是每一个程序员、架构师或项目经理都会经常遇到的问题。面对这个问题,不同的人有不同的应对之道,最近微博上有一段关于需求变化的讨论:

@假装刺猬的猪:我们在软件开发过程中,会持续碰到客户需求变更的情况。如果没有领域建模,我们单纯将问题使用直觉将问题解决,那么等到客户需求变更或者有新的需求时,就会面临一个僵硬的前设计!无法在以前的设计上持续深入的优化模型,导致需求变更无法及时深化。设计实现均滞后与变更!

@高煥堂: <碰到客户需求变更的情况>是合理的;但<领域建模>不是美好的手段!!!

@weidagang: 要不被客户牵着鼻子走,需要自己有很强的设计能力,反过来让客户跟着你的设计来满足你的要求。能做到这点的公司很少,但这是软件行业唯一有希望的出路。

@高煥堂: <这是软件行业唯一有希望的出路>。 Great!!

如何应对需求变化? @假装刺猬的猪 的答案是领域建模,并持续优化模型,适应需求的变化。@高煥堂 则认为领域建模不是美好的手段。我进一步补充,应该“反过来”让自己在需求变化中处于主导地位,而不是被动地适应。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 4.76 )
Loading...
多版本并发控制(MVCC)在分布式系统中的应用

多版本并发控制(MVCC)在分布式系统中的应用

感谢 Todd投递本文 – 微博帐号:weidagang

问题

最近项目中遇到了一个分布式系统的并发控制问题。该问题可以抽象为:某分布式系统由一个数据中心D和若干业务处理中心L1,L2 … Ln组成;D本质上是一个key-value存储,它对外提供基于HTTP协议的CRUD操作接口。L的业务逻辑可以抽象为下面3个步骤:

  1. read: 根据keySet {k1, … kn}从D获取keyValueSet {k1:v1, … kn:vn}
  2. do: 根据keyValueSet进行业务处理,得到需要更新的数据集keyValueSet’ {k1′:v1′, … km’:vm’} (:读取的keySet和更新的keySet’可能不同)
  3. update: 把keyValueSet’更新到D (:D保证在一次调用更新多个key的原子性)

在没有事务支持的情况下,多个L进行并发处理可能会导致数据一致性问题。比如,考虑L1和L2的如下执行顺序:

  1. L1从D读取key:123对应的值100
  2. L2从D读取key:123对应的100
  3. L1将key:123更新为100 + 1
  4. L2将key:123更新为100 + 2

如果L1和L2串行执行,key:123对应的值将为103,但上面并发执行中L1的执行效果完全被L2所覆盖,实际key:123所对应的值变成了102。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 4.24 )
Loading...
Bret Victor – Inventing on Principle

Bret Victor – Inventing on Principle

Bret Victor简历) – 苹果公司的UI交互设计师(大神级的人),在 CUSECCanadian University Software Engineering Conference) 上做了一个题为 “Inventing on Principle” 的演讲(vimeo视频链接),这个演讲中展示了五个示例:

  • 用程序画树。如何把程序绘图变成实时的,如何把程序和图映射起来。
  • 游戏调试。在实时编程的基础上,可以更容易的让你看到程序参数对游戏的调整,甚至对游戏过程的可视化调试。
  • 算法调试。在写二分查找算法时可以实时看到程序的执行过程。边写边看到。
  • 电路图。可以实时地看到电路图中各个部件的对1/0信号的处理。
  • 动画。一种比flash制作动画更NB 的方法。

下面是优酷上的视频——你一定会被示例中的那些编程工具所震撼!

不过,Bret并不是在说什么编程,也不是在说什么技术,他是在说 How to live your life。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (52 人打了分,平均分: 4.92 )
Loading...
由12306.cn谈谈网站性能技术

由12306.cn谈谈网站性能技术

12306.cn网站挂了,被全国人民骂了。我这两天也在思考这个事,我想以这个事来粗略地和大家讨论一下网站性能的问题。因为仓促,而且完全基于本人有限的经验和了解,所以,如果有什么问题还请大家一起讨论和指正。(这又是一篇长文,只讨论性能问题,不讨论那些UI,用户体验,或是是否把支付和购票下单环节分开的功能性的东西)

业务

任何技术都离不开业务需求,所以,要说明性能问题,首先还是想先说说业务问题。

  • 其一有人可能把这个东西和QQ或是网游相比。但我觉得这两者是不一样的,网游和QQ在线或是登录时访问的更多的是用户自己的数据,而订票系统访问的是中心的票量数据,这是不一样的。不要觉得网游或是QQ能行你就以为这是一样的。网游和QQ 的后端负载相对于电子商务的系统还是简单。
  • 其二有人说春节期间订火车的这个事好像网站的秒杀活动。的确很相似,但是如果你的思考不在表面的话,你会发现这也有些不一样。火车票这个事,一方面会伴随着大量的查询操作,更BT的是下单的时候需要对数据库很多的一致性的操作,一方面是从起点到终点各个分段票的一致性,另一方面,买的人路线、车次、时间选择有很多,会不停地改变下单方式。而秒杀,直接杀就好了,没有那么多查询和一致性的问题。另外,关于秒杀,完全可以做成只接受前N个用户的请求(完全不操作后端的任何数据, 仅仅只是对用户的下单操作log),这种业务,只需要在内存cache中放好可秒杀的数量,还可以把数据分布开来放,100商品,10台服务器一台放10个,无需在当时操作任何数据库。可以订单数够后,停止秒杀,然后批量写数据库。而且秒杀的商品不多。火车票这个不是像秒杀那么简单的,春运时间,几乎所有的票都是热门票,而且几乎是全国人民都来了,而且还有转车业务,多条线的库存都要做事务操作,你想想吧,这有多难。(淘宝的双十一也就3百万用户,而火车票瞬时有千万级别甚至是亿级别的)(更新:2014年1月11日:来了淘宝后,对淘宝的系统有了解,淘宝的秒杀活动,本质上是用输验证码并在CDN上把用户直接过滤掉了,比如:1千万个用户过滤了只剩2万个用户,这样数据库就顶得住了)
  • 其三有人拿这个系统和奥运会的票务系统比较。我觉得还是不一样。虽然奥运会的票务系统当年也一上线就废了。但是奥运会用的是抽奖的方式,也就是说不存在先来先得的抢的方式,而且,是事后抽奖,事前只需要收信息,事前不需要保证数据一致性,没有锁,很容易水平扩展。
  • 其四订票系统应该和电子商务的订单系统很相似,都是需要对库存进行:1)占住库存,2)支付(可选),3)扣除库存的操作。这个是需要有一致性的检查的,也就是在并发时需要对数据加锁的。B2C的电商基本上都会把这个事干成异步的,也就是说,你下的订单并不是马上处理的,而是延时处理的,只有成功处理了,系统才会给你一封确认邮件说是订单成功。我相信有很多朋友都收到认单不成功的邮件。这就是说,数据一致性在并发下是一个瓶颈

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (87 人打了分,平均分: 4.84 )
Loading...
如何设计“找回用户帐号”功能

如何设计“找回用户帐号”功能

因为《腾讯帐号申诉的用户体验》一文中好多人觉得腾讯申诉是世界级先进的,并让我拿出一个找回用户的帐号的功能来。本来不想写的,因为大家看看其它系统的就行的,但是,很明显有些人就是很懒,也不会思考,而且不会观察,所以,我就只好写下这篇科普性常识性的文章。

在行文之前,我得先感谢腾讯公司的至少30名员工在《腾讯帐号申诉的用户体验》一文后的回帖(我STFG(Search The Fucking Google)看到了你们使用的那个固定IP在各个大学论坛上的腾讯的招聘广告),我感谢你们主要有两点:

  1. 你们有半数以上的人留下的是gmail而不是QQMail/Foxmail的电子邮件,这点让我感到很欣慰。
  2. 你们在加班到晚上11点的时候都能在本站回复,的确如你们的Andy Pan所说,你们的核心竞争力很强,包括水军方面。

好了,让我正式谈谈这个设计。找回用户帐号通常就用三个事就可以了:邮箱安全问答手机

邮箱安全问答手机

大多数的系统都会使用邮箱和安全问答,这足够了,很多系统直接用邮箱做帐号名(Apple ID,Facebook,新浪微博 ….),这样一来,就算你的系统口令被盗,帐号的是改不掉的,于是你可以用邮箱找回(注:这些系统都会验证你的邮箱是否正确)。但是,如果用邮箱做帐号,会导致你的邮箱暴露了,这样为成为垃圾邮件的受害者,而且如果你还比较2的把邮箱的口令和帐号的口令设置成一样的,那么就相当坑爹了(你可以看看本站的这篇文章——如何设计你的口令)。所以,但凡是用邮箱用为帐号的系统都不会让人看到你的注册邮箱,比如,大家就不知道我新浪微博帐号注册的邮箱,就算是知道也应该是受信的人知道(新浪微博帐号的邮箱地址的默认可见度是“你关注的人”)。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (33 人打了分,平均分: 4.48 )
Loading...
API设计:用流畅接口构造内部DSL

API设计:用流畅接口构造内部DSL

感谢@weidagang (Todd)向酷壳投递本文。

程序设计语言的抽象机制包含了两个最基本的方面:一是语言关注的基本元素/语义;另一个是从基本元素/语义到复合元素/语义的构造规则。在C、C++、Java、C#、Python等通用语言中,语言的基本元素/语义往往离问题域较远,通过API库的形式进行层层抽象是降低问题难度最常用的方法。比如,在C语言中最常见的方式是提供函数库来封装复杂逻辑,方便外部调用。

不过普通的API设计方法存在一种天然的陷阱,那就是不管怎样封装,大过程虽然比小过程抽象层次更高,但本质上还是过程,受到过程语义的制约。也就是说,通过基本元素/语义构造更高级抽象元素/语义的时候,语言的构造规则很大程度上限制了抽象的维度,我们很难跳出这个维度去,甚至可能根本意识不到这个限制。而SQL、HTML、CSS、make等DSL(领域特定语言)的抽象维度是为特定领域量身定做的,从这些抽象角度看问题往往最为简单,所以DSL在解决其特定领域的问题时比通用程序设计语言更加方便。通常,SQL等非通用语言被称为外部DSL(External DSL);在通用语言中,我们其实也可以在一定程度上突破语言构造规则的抽象维度限制,定义内部DSL(Internal DSL)。

本文将介绍一种被称为流畅接口(Fluent Interface)的内部DSL设计方法。Wikipedia上Fluent Interface的定义是:

A fluent interface (as first coined by Eric Evans and Martin Fowler) is an implementation of an object oriented API that aims to provide for more readable code. A fluent interface is normally implemented by using method chaining to relay the instruction context of a subsequent call (but a fluent interface entails more than just method chaining).

下面将分4个部分来逐步说明流畅接口在构造内部DSL中的典型应用。

1. 基本语义抽象

如果要输出0..4这5个数,我们一般会首先想到类似这样的代码:

//Java
for (int i = 0; i < 5; ++i) {
    system.out.println(i);
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (14 人打了分,平均分: 3.36 )
Loading...