Category Archives: Uncategorized

(笔记)正则表达式的几种引擎

这篇主要是基于《精通正则表达式》的一篇读书笔记,因为书还没看完,可能以后还会有相关的笔记。(工作以后看书的效率真的很低啊……) 正则引擎主要可以分为基本不同的两大类:一种是DFA(确定性有穷自动机,学过计算理论的应该都知道),另一种是NFA(非确定性有穷自动机),DFA和NFA都有很长的历史,NFA的历史更长一些,两者在二十多年的发展中产生了许多不必要的变体。而POSIX标准的出台是为了规范这种现象。POSIX标准不但清楚地规定了引擎应该支持的元字符和特性,还明确规定了使用者期望由表达式获得的准确结果。DFA已经符合新的标准,而NFA则需要修改才能符标准。这样一来,正则引擎可以粗略地分为3类:DFA、传统型NFA、POSIX NFA,表格 1是从书中摘出来的,基本涵盖了现在主流的大部分程序。 表格 1 引擎类型 程序 DFA awk (大多数版本)、egrep(大多数版本)、flex、lex、MySQL、Procmail 传统型NFA GNU Emacs、Java、grep(大多数版本)、less、more、.NET语言、PCRE library、Perl、PHP(所有三套正则库)、Python、Ruby、sed(大多数版本)、vi POSIX NFA mawk、Mortice Kern Systems’ utilities、GNU Emacs (明确指定时使用) DFA/NFA 混合 GNU awk、GNU grep/egrep、Tcl DFA和NFA反映了将正则表达式在应用算法上的根本差异。NFA可以称为表达式主导的引擎,DFA则可以称为文本主导。所谓表达式主导是指在每一个匹配过程中,每一个子表达式都是独立的,或者可以认为一条由多个子表达式组成的正则表达式在表达式主导的引擎中等效于基本等效于多条表达式串行执行(当然公共部分是不会被重复执行的)。而在文本主导的引擎中,多条子表达式会在扫描文本时同时进行匹配。 在书上举了个例子,基本说明了这两种方式的不同:用to(nite|knight|night)匹配文本’tonight’,当表达式主导引擎来匹配时,在匹配完to后会依次匹配nite、knight、night直到匹配成功为止(即匹配night时)。而文本主导的引擎匹配时,会记录当前有效的所有匹配可能,所以当匹配完to时,由于knight的k不能匹配,所以被淘汰出局,这时剩下的是两个有效的可能匹配(nite和night),当扫描到g时就只剩下一个可能匹配了,当h和t完成匹配时,引擎发现匹配完成,报告成功。 以上的匹配过程其实引出了几个概念,同时我们也可以从这个例子中看出两种引擎的不同。在NFA中由于表达式主导的串行匹配方式,所以用到了回溯(backtracking),按照书中的说法,这个是NFA最重要的部分,每一次某个分支的匹配失败都会导致一次回溯,因此如何正确的选择表达式,减少回溯次数就成为了提高NFA引擎下正则表达式工作效率的关键。具体内容可以参考相关资料。另外还有两个DFA中没有的概念:“匹配优先量词”和“忽略优先量词”。(在DFA中只有匹配优先,这个也很好理解,一方面是DFA没有也不需要回溯,另外一个原因是DFA的最左最长原则,在下文会提到)这里也不展开了,网上有不少资料讲这两个概念,以及如何灵活选择两种量词来提高效率的范例。 总的来说DFA和NFA的明显区别之一在于效率,正如上面说到的,由于DFA没有回溯,因此看起来在某些情况下会比NFA来得更快,但是在真正使用中,DFA需要进行预编译才能获得更好效果,因为DFA的匹配方式需要更多的内存和时间,在第一次遇到正则表达式时需要比NFA详细得多的方法来分析这个表达式,不过可以预先把对不同正则表达式的分析结果建好,DFA就可以获得比NFA更优的速度。虽然NFA速度更慢,并且实现复杂,但是它又有着比DFA强大的多的功能,比如支持环视,支持反向引用(虽然这个是非正则的)等。除此之外,最大的区别就在于最左最长规则(longest of the leftmost)这是在POSIX标准中规定的一条原则,即如果在字符串的某个位置存在多个可能的匹配,则返回的是最长的匹配,又由于匹配时总是从左边开始的,所以叫最左最长规则。DFA天然地支持这一条规则,而NFA由于使用了回溯,并且会在匹配时立刻返回结果,再加上忽略优先量词的存在,使得它天然地不支持这条规则……,当然如果对NFA进行一些修改,要求其在首次匹配时不是停下来而是穷尽所有结果,最后返回最长的结果,则NFA就被改造成了POSIX NFA。 正则表达式的终极境界是兼具DFA的速度和NFA的功能,比如GNU grep采取了一种简单有效的策略,在平时尽可能多地使用DFA,在需要用到反向引用的时候,才切换到NFA,可以得到很不错的结果。

Posted in Uncategorized | Tagged | Leave a comment

转:你确信你了解时间吗?

转一篇好玩的,原帖地址:http://coolshell.cn/articles/5075.html。 不过在网上考了会据,没查到1927年上海时区和北京时区切换的事迹,百度百科上的说法,从清末开始更多的时候我国用的也是东经120度的北京时间。不过考虑到1927年北伐胜利,宁汉合流,南京国民政府势头正盛,可能在国际上取代了北洋政府(难道北洋政府会使用上海时间??反正都是不靠谱的猜想,以后有时间看看能不能好好考考古),因此切换了时区……反正自己都觉得这种猜想完全不着调,大家还是好好看正文吧。 =====================转载分隔线================================= 你还记得“软件真的好难做”中的那个有意思的例子吗?那个例子告诉我们软件开发中假设可能会是致命的事。今天,我又在StackOverflow上看到一个关于时间的问题——为什么1927年12月31日的午夜时间这么奇怪?提问题的这个人给了下面的一段java代码(我做一些修改,保证让你可以copy过去就可以编译运行) 我在其中高亮了两行,这个程序就是想比较一下“1927-12-31 23:54:07”  和  “1927-12-31 23:54:08” 差几秒,很明显,是差一秒。但是程序的输出却不是这样的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import java.text.SimpleDateFormat; import java.text.ParseException; import java.util.Date; class time{     public static void main(String[] … Continue reading

Posted in Uncategorized | Leave a comment

7月16日36氪openday

今天参加了36氪openday的活动,刚一进场就是人山人海,现在确实创业的氛围很火热啊,就是不知道这样的好日子还能过多久。以下就分别大致介绍一下会上的六个项目吧。 举手网是一个可以让消费者自有发起团购活动的在线购物平台。举个例子,当一个消费者在网上看到一个产品的批发价比较诱人,而要求购买的数量较大时,消费者可以在这个网站上发起团购。当团购经过简单审核通过之后,如果用户数达到要求,则团购成功。个人以为这个网站的前景不是很明朗,从现阶段来看确实存在一定的生存空间,但是可发展的余地有限。首先,目前网上批发的商品并不多,个人认为网上直销由于省略了许多中间环节,节省了中间经销商的成本以及仓储、货币损耗之类的费用,因此其价格其实已经很接近批发的价格。在介绍会上,举手网的工作人员举的是阿里巴巴的例子,个人觉得B2B之间可能还存在增值税征收之类的问题,想以个人组团的形式去参与B2B有一定的困难。其次,即使这种方法真的可行,并且有利可图,那么其实那些批发的网站其实完全可以自己加上这个功能,因此举手网的模式很容易被更有先天优势的第一方网站所使用,当这个模式前途光明之日,便是举手网黯然收场之时,因此这个项目感觉从一开始就带上了一层悲剧的气质,不知道有哪些VC愿意冒这个险。 六人行这个网站有点像微博化的豆瓣小组。当你想要发起一个活动,而苦于周围没有同好参加时就可以在这个网站上征集同道中人,甚至小到下班后的拼桌吃饭,周末电影桌游,都可以在这个网站上征集,类似于豆瓣,但是又有微博消息更加实时醒目的优点。感觉很对拥有大量外来人口,各种周末空虚寂寞男女的大城市的胃口。所以这个网站还是有一定的前景的,只是目前宣传投入还不大,并且如何应付进一步改良后的豆瓣之类已经积聚大量人气的网站的竞争,也是个问题。但是至少目前这个项目还是值得VC一烧的。 《上海1930》是一个手机上的SNS格斗游戏,这个游戏没体验过,不过光看它的属性就挺吓人的了:移动互联网、手机游戏、SNS,基本融合了现在最火热的几个要素,从不多的几张截图来看,这家名为钻石星辰的公司拥有相当出色的美工。个人认为虽然玩游戏时,虽然剧情、设定、游戏性(平衡性)之类的因素往往被人捧得很高,而图像里更为人强调的又往往是它的引擎。但是其实很多时候个人以为一个优秀的游戏,优秀美工其实占到了50%以上的比重,(就好像我们很多时候不愿意承认自己以貌取人一样,说要更注重内涵,但是往往外表还是在印象分中占到了一个很大的比例),回顾square当年的FF7,ps秒掉N64的很大原因其实就是靠着那些华而不实与游戏内涵其实并无多少实质关系的电影级CG动画,以光荣为代表的精细画风派基本也代表了那个时代优秀的日本PC游戏厂家,而暴雪的那些经典,曾经的黑岛,乃至国内的大宇,虽然大家在评价他们的成就时时常有意无意地淡化了美工的作用,但是不可否认,他们的美工都基本代表了同一时期的最高水平。我觉得一个不要让人玩不下去的设定和一个不要太狗血的剧情,外加一个bug较少的程序和一个出色的美工就足以打造出一款80分以上的好游戏。此外还不知道这个游戏的SNS要素如何发挥,因为宣传会上透露除了几张截图其它剧情实在太少。不过从偷菜这种毫无技术含量的小游戏都能风靡一时来看,只要钻石星辰能留住他们现在的美工团队,我觉得这是一家可以期待的公司。 WSS项目管理系统,在这个时代提出项目管理系统实在有点不合时宜……而且介绍的人也太害羞了,下面叫了好几次声音也大不起来,最后也没留下什么印象,直接pass吧…… 木瓜孵化器,这个孵化器属于木瓜移动旗下,算是出身豪门了,感觉有点创新工场+行云,网上资料应该很多很全,具体就不介绍了,有兴趣的同学可以自己去搜搜。木瓜移动则号称美国最大的安卓开发者平台,感觉这个项目应该不缺钱…… 面孔网,这个比较雷,还没上线,并且号称开放所有源代码……不知道什么情况,这个项目的目的又是什么。它的功能也挺普通,感觉远没有微博强大,只有一个随时分享聚会照片的主要功能,另外还有一个比较雷的分析功能,可以告诉你,你的好友们平时都跟谁在一起(……能联想的同学自己联想吧=_=),其实就算这种功能微博应该也可以用一个应用轻松提供,感觉这个网站与微博的关系就像垂直搜索和网页搜索的关系,目前的气候远远不成熟,而且还没上线就开放源代码,并且实时公开开发进度……这、这……应该说他们的老板搞这个项目估计有别的目的吧…… 前几天在微博上看到了几个项目ppt的网址,在这里补上吧。

Posted in Uncategorized | Tagged | Leave a comment

一致性hash算法简介

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得分布式哈希(DHT)可以在P2P环境中真正得到应用。 一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。 2、单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。 3、分散性(Spread):在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。 4、负载(Load):负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。 普通的哈希算法(也称硬哈希)采用简单取模的方式,将机器进行散列,这在cache环境不变的情况下能取得让人满意的结果,但是当cache环境动态变化时,这种静态取模的方式显然就不满足单调性的要求(当增加或减少一台机子时,几乎所有的存储内容都要被重新散列到别的缓冲区中)。 一致性哈希算法有多种具体的实现,包括Chord算法,KAD算法等实现,以上的算法的实现都比较复杂,这里介绍一种网上广为流传的一致性哈希算法的基本实现原理,感兴趣的同学可以根据上面的链接或者去网上查询更详细的资料。 一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。当有一个写入缓存的请求到来时,计算Key值k对应的哈希值Hash(k),如果该值正好对应之前某个机器节点的Hash值,则直接写入该机器节点,如果没有对应的机器节点,则顺时针查找下一个节点,进行写入,如果超过2^32还没找到对应节点,则从0开始查找(因为是环状结构)。如图1所示  图 1 图1中Key K的哈希值在A与B之间,于是K就由节点B来处理。 另外具体机器映射时,还可以根据处理能力不同,将一个实体节点映射到多个虚拟节点。 经过一致性哈希算法散列之后,当有新的机器加入时,将只影响一台机器的存储情况,例如新加入的节点H的散列在B与C之间,则原先由C处理的一些数据可能将移至H处理,而其他所有节点的处理情况都将保持不变,因此表现出很好的单调性。而如果删除一台机器,例如删除C节点,此时原来由C处理的数据将移至D节点,而其它节点的处理情况仍然不变。而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法,因此也很好得降低了分散性和负载。而通过引入虚拟节点的方式,也大大提高了平衡性。 最后附一个c语言一致性hash的代码实现。  

Posted in Uncategorized | 14 Comments

Hello world!

Welcome to WordPress. This is your first post. Edit or delete it, then start blogging!

Posted in Uncategorized | 1 Comment