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

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 4.17 )
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

好烂啊有点差凑合看看还不错很精彩 (39 人打了分,平均分: 4.51 )
Loading...
做个环保主义的程序员

做个环保主义的程序员

十多年前刚走入社会工作的时候,那时的中国软件开发根本没有什么版本管理,也没有什么编程规范,软件开发相比起今天来说非常地混乱,那时仅凭自己的一些学习总结了一些C语言编程中的好的小笔记,后来,这些笔记写成了一篇叫《编程修养》的文章。今天,又有些感触,想把这个话题扩大一下,从“个人修养”扩大到“环境保护”,所谓,穷则独善其身,富则达济天下,今天的技术人员比十多年前在技术和环境上都富有了许多,所以,也应该或多或少地担负起“达济天下”的责任了。

环境保护说白了就是保护一个良好的环境,为好的环境添砖加瓦,与破坏环境的人和事做斗争。其实,从技术人员来说,我们可以做一些力所能及的事。因为我们身边的技术环境还有很大的改善的空间,而一些来之不易的东西还需要我们去小心维护。另外,对于我们自己来说,少吃一些垃圾食品,健康生活,对自己也有益。

环保主义软件开发

先说说软件开发中的环保。比如:

  • 环保需求。当我们分析需求的时候,如果我们能做到不要像“这是到底是谁的错”一文中那样的来者不拒,如果我们在面对需求能多问这样几个问题:为什么 要有这样的需求?这个功能主要能解决什么 样的问题?为什么不是另外那一种?可不可以简化一下?其实,我们并不需要创新,只需要真正地问好这几个问题,我们就可以少看着一些弯路,少一些苦逼的加班,少一些内耗,少一些埋怨,也就可以为这个社会节省下一些资源,从而环保。
  • 环保开发。当我们做设计写代码的时候,如果我们多花一些时间去思考一下,我们就可以少一些代码(参看“多一些时间少一些代码”)。如果我们在一开始多思考一下,不要急着马上去用迭代的方式认识世界,多思考一下怎么把复杂的东西解藕,把复杂的东西简化,怎么做出一个优雅的设计,怎么让我们的程序少一些tricky的东西,怎么让我们的程序变得更简洁,更清楚,更直,在一开始思考一下未来需求可能的变化,未来软件需要怎么测试,未来的系统需要怎么的运维,那么,我们可以少一些返工,少一些重构,少欠一些债,少一些低级错误,少承担一些系统上线后的压力,那么,我们同样可以为这个社会节约一些资源。说得再直白一点,你用更少的代码产生出更高的效益,少耗一些CPU,就能省一些电,间接地保护了环境。(参看 Why C++?
好烂啊有点差凑合看看还不错很精彩 (150 人打了分,平均分: 4.47 )
Loading...
游戏:VIM大冒险

游戏:VIM大冒险

不知道大家是否还记得“Vim简明攻略”呢?你是不是对Vim的那一大堆热键很头痛呢?现在好好,下面这个游戏是一个使用VIM热键玩的游戏。你可以在玩游戏的过程中熟悉Vim的热键。

你可以点击图片,或是图片下的网址打开这个游戏

http://vim-adventures.com/

VIM大冒险

我试玩了一下这个游戏,真的很不错,下面是一些我给的游戏攻略。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (37 人打了分,平均分: 4.43 )
Loading...
这到底是谁之错?

这到底是谁之错?

【感谢 @风枫峰 投递本文】

故事一:
背景介绍:RT是一个外包公司,ZWZX是项目承接公司,YD是甲方。

RT公司每天下班的时候都会接到ZWZX负责人的电话,询问一天的工作情况,然后布置任务要求晚上加班做完,RT公司的员工很无奈也很气愤因为每天都要加班,员工们就问项目经理:“为什么天天加班赶需求,今天才提一个需求,明天就要上线,还让不让人活了?” 项目经理无奈的说:“我有什么办法啊?这是人家ZWZX负责人说的啊,对方逼得紧。”

多次以后项目经理也忍不住了,就问ZWZX的负责人怎么天天这样啊,ZWZX的负责人就说了:”明天就要向YD的负责人展示这个页面,我也没有办法啊?YD那边老总就是这么要求的,我怎么办,我也不想这样啊?”

然后RT的项目经理实在受不了了就辞职了,新上任的项目经理又会走他的老路,因为从开始我们就被培养“满足客户的需求是最重要的”。RT的员工也就这样一直抱怨着,一直忍受着。天天在心里咒骂YD的老总真是没有人性,不拿人当人看啊!

人换了一批又一批,加班也就慢慢的变成了应该的,你不加班说明你不敬业,不合格。

故事二:
IE6一直存活着,所有的前端开发人员都痛恨它,都不想兼容它,可是产品经理看到IE6的市场占有率还是这么高,就会要求前端开发人员必须兼容IE6。

阅读全文 Read More

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

挑战无处不在

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

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

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

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (62 人打了分,平均分: 4.56 )
Loading...
谈谈数据安全和云存储

谈谈数据安全和云存储

前些天,创新工场李开复同学在2012博鳌亚洲论坛表示

“你们有多少人丢过手机?大概有15%。你们有多少人数据放在微软掉过的?我想不见得很多吧。所以相对来说是安全的。放在大公司里比自己拿着掉的概率更大,你不相信的话,可以问陈冠希先生。

两种安全

看到这个消息的时候,我觉得李开复同学混淆了云存储和安全这两个概念,在英文里,有两个单词,一个是Safety,一个是Security,很不幸的是,这两个英文单词翻译成中文都叫“安全”,因此总是被混淆,熟知英文又熟悉IT业的李开复同学在这个句子中混淆了这“两种安全”,我在我的微博上指出来后,居然还有很多网友继续混淆这两点,所以,这让我产生了写篇博文的说明一下,并顺着说说云存储和数据安全的个人理解。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (28 人打了分,平均分: 3.71 )
Loading...
CSS 布局:40个教程、技巧、例子和最佳实践

CSS 布局:40个教程、技巧、例子和最佳实践

感谢 Neo 投递本文 – 微博帐号_锟_

前言: 布局是WEB开发一个重要的课题,进入XHTML/CSS后,使用TABLE布局的方式逐渐淡出,CSS布局以众多优点成为主流,本文将介绍40个基于CSS的web布局的资源和教程。文章的出处在http://www.noupe.com/css/css-layouts-40-tutorials-tips-demos-and-best-practices.html。文中的不少的例子在一本经典的CSS书籍《CCS: The Missing Manual, 2nd Edition》中都可以找到,据我所知,第二版在中国没有翻译出版。你可以从这里下载英文版(不过需要注册个用户名)

正文
基于CSS的布局能提供更灵活布局方式和更强的用户视觉体验。一些重要技巧和关键点可以帮助初学者理解CSS布局的基础和本质。这也是本文成文的原因 ——找到那些完美的布局,完全灵活的,等高栏和工作完美的布局。
因此下面这个列表就是我们整理了网络上关于基于CSS布局的一些技巧,教程和最佳实践的列表。
当然你也可能对下面这些和CSS相关的主题有兴趣:

The 7 CSS Hacks that we should use
Using CSS to Do Anything: 50+ Creative Examples and Tutorials
Using CSS to Fix Anything: 20+ Common Bugs and Fixes

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (19 人打了分,平均分: 3.68 )
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

好烂啊有点差凑合看看还不错很精彩 (58 人打了分,平均分: 4.59 )
Loading...
软件开发的“三重门”

软件开发的“三重门”

自从上次写了“程序员技术练级攻略” 以来,就觉得似乎还有很多东西没有谈到,但当时没有继续思考了。而春节前有人问我,是做底层技术,还是做业务。这问题让我思考了很多,不由自主地回顾了一 下我这十多年的软件开发经历,并顺着整理分类了一下自己解决过的若干问题,还发散想了很多,经过了一个春节假期的发酵,产生了下面这篇文章。

前言

这篇文章必然是通过我的个人经历来写的。所以,我先说说个人经历吧。我的经历基本分成三个阶段。

第一阶段:我 刚毕业时在家乡的某银行工作,做些银行的业务系统,还搞些网络,电子邮件系统,OA什么的,因为大四的时候在老师的公司里实习,银行里的人际关系太复杂, 而且技术都包给了产商,所以在银行的每一天都觉得不能适应里面的工作环境。两年后离职,单位分的房也不要了,直接去了上海,在上海呆了两年,本来想做互联 网的,但是泡沫来了,最终去了一家做系统集成的国企公司还是继续做银行业务。这四年来,主要解决的都是一些业务上的问题,银行里的会计业务,OA业务,国 际业务,中间对公业务都非常地复杂,而且因为当时的软件开发相当的不规范,所以基本上是在一种比较混乱的状态下度过的,而银行方面又很强势,所以,这段时 间主要是做业务。所以,技术上主要是积累了如何使用那些技术。C+/Java, Windows编程,Unix编程,网络编程主要是这段时间学的,看了太多的书(我大学课程里没有C++和Java,也没有Windows/Unix和网 络编程,所以,只能拼命地看书和自学)。

第二阶段:然后,我来了北京,到了一家做分布式计算系统的公 司,整天和一个高性能技术高可用性的企业级的集群式的软件产品打交道(这家公司去年被IBM收购了),在这家公司把Windows/Unix和网络编程有 了更深入的了解,对我长进比较大的是明白了怎么做一个性能高,可用性高的集群式的系统,天天和底层打交道,干了4年多。然后去了一家金融信息公司,这家金 融公司主要做全球的金融信息数据处理,而我主要还是做核心数据发布系统的性能调优的项目,金融数据的实时性要求的高,数据量非常地大,高可用性要求得高, 得想尽一切办法省网络带宽,增加系统性能,还要保持高的可用性,不当机,不丢包。又干了4年多,入职的时候从国外接过来两个系统,其性能单机每秒可处理 120K message,我走的时候,我和团队把其优化到了每秒1.4M messages 的吞吐,另一个系统,从接手时的100k message/s优化到了500k message/s。这八年多的时候,全是在和这些高计算高性能的项目打交量,几乎没有什么业务,都是纯技术,积累到了很多和性能有关的高并发高计算系统 架构级的知识。

阅读全文 Read More

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