Shell's Home

全局初始化

Jan 17, 2007 - 1 minute read - Comments

大家写代码的时候,假如写了一个组件,自身需要开一个线程的。那么多数是在初始化代码中直接写开线程的。如果要求这个类不在初始化代码中添加函数,怎么做? MSDN中有个例子,不是解决这个问题的,但是可以用。 class DialogWindow{ public: static short GetTextHeight(){ return 1; }; private: static short nTextHeight; }; short DialogWindow :: nTextHeight = GetTextHeight(); int main(){} 在这里,把GetTextHeight里面添加上你需要的代码就可以了。 但是注意,这些代码的运行时间要早于main(准确的说,是在wmainCRTStartup里面运行的_c_init函数)。所以很多自然而然就有的初始化没做,你自己在main里面调用的初始化(例如WSAStartup啦,GDI+初始化啦)更是没做。所以必须严格测试。

KMP

Jan 16, 2007 - 3 minute read - Comments

KMP是一个给人捧滥了的算法,其实单看同时有三个发明人这点,就知道这个算法是自古华山一条路,没别的想法的。KMP的算法每步虽然难想但是自然有道理,没有别的方法的。不像排序算法,一嘟噜的算法还没完。根据各种侧重点不同有不同的算法可用。 KMP的比较算法核心在于不回朔。我们先看一个正常的例子。 SSSSSSSSSSSSSS TTTTT i=0, j=1,2,3… TTTTT i=1, j=1,2,3… TTTTT i=2, j=1,2,3… 我们用T去匹配S,先对齐T和S的头部,然后对比T和S。如果T的范围内,TS内容一致,则匹配成功。不成功的话就将T向后移动一个字符。再次匹配T范围内TS的内容是否一致。ij的范围最大会在0<=i<=“j KMP算法的核心在于,如果T范围内TS的内容不一致,那么T向后移动不是一个字符,而是多个。而当前比较位置永远不向前移动。如果您写出来的算法当前比较位置向前移动了,那么肯定是写错了。 我们假定T范围内第i个字符匹配失败(0<=i 为什么能移动一个以上呢?Next[i]怎么确定呢?我们看一个抽象的例子:M代表匹配,N不匹配,U不知道。 MMMMMNUUUUU TTTTTTTTTTTTTTT TTTTTTTTTTTTTTT 我们可以看到,向后移动字符的时候,T自身有重合的部分。这时候有三种状况,我们先假定一种重合的状况。假定T向后移动了一些字符,P代表当前比较位置。在这个位置上TS出现了不匹配。 ..MMMNUUU.. ..TTTTTPTTTT.. ..MMNTTTTTT.. 在这个T向后移动一些距离后,在当前比较位置前已经出现了自身和自身不匹配的状况。根据上面我们知道,当前位置以前的T和S是匹配的。那么就是说,移动了这些字符后。T当前的位置上不可能取得匹配。我们称这种情况为这个位置的自身完全不匹配。 然后是另外一种匹配状况,符号和上面一致。 ..MMMNUUU.. ..TTTTTPTTTT.. ..MMMNTTTT.. 这个时候,T在当前匹配位置上自身不匹配,前面位置都匹配。同理可以知道,T在滑移到这个位置后可能取得匹配。我们称这种情况为这个位置的自身部分不匹配。 最后一种匹配情况是。 ..MMMNUUU.. ..TTTTTPTTTT.. ..MMMMUUU.. 这个时候,T在在前面和当前位置都匹配。我们知道前面是匹配的,然而当前既然已经被证明了和S不匹配。那么滑移这些位置后,新的位置上T也不可能和S取得匹配。我们称这种情况为这个位置的自身完全匹配。 然后我们可以回头看看比较过程了。当我们对齐TS,然后进行比较的过程中。出现了不匹配。 注意一个问题,我们回朔是为了知道移动后的T是否仍旧匹配。所以如果我们知道T匹配不匹配,就不用回朔。 这个时候我们不移动一次T,然后回朔。而是将T滑移一下,先滑移1位好了。假设出现了当前比较位置的自身完全不匹配或者自身完全匹配,那么滑动1位肯定也无法获得一个有效的匹配。那么就继续滑动,直到出现了自身部分不匹配,或者T已经完全的滑动到了当前位置的后面。这时候T的位置才是有可能获得匹配的位置,其余的位置就没必要浪费时间了。 也就是说,滑移距离Next[i]是i这个位置上滑动距离逐渐增加的时候,首次出现自身部分不匹配情况的位置。如果这情况不出现,那么就设定为<1的值。操作上将整个T滑动到当前位置的后面,并且从下一个位置开始比较起。 然后附上初始版的代码和比较过程。 int *cul_next (char *lpTpl) { unsigned int i = 0, j = 0, l = 0; int *next; l = strlen (lpTpl); next = new int[l]; memset (next, 0, l *

查找重复文件

Jan 15, 2007 - 1 minute read - Comments

算是介绍一个奇淫巧技吧。查找重复的文件,这个应该有很多软件都可以做的。不过在Linux里面,利用系统工具,一句语句查找应该就比较少见了。 $find . -name "*" -type f -size +0 -exec md5sum {} ; | sort | uniq -d -w 32 原理是这样的,先用find查找当前所有文件。我们加上限定类型必须是文件,目录不要。限定大小不为0,空文件不要。然后对所有满足条件的执行md5sum,获得md5和文件的列表。然后排序,再针对md5的部分做唯一限定。就得到了所有md5相同的文件的列表。 问题是,这时候我们得到的还只是一堆重复的文件的md5。我们可以把以上步骤拆开来获得完整的输出。 $find . -name "*" -type f -size +0 -exec md5sum {} ; | sort > file_md5 $cat file_md5 | uniq -d -w 32 $grep "..." file_md5 相信大家都看出是怎么回事情了,就不赘言了。 Windows下以前我总是执行不出,原因在于要这么写。 find . -type f -size +0 -exec md5sum {} ; | sort > report.txt 差一个转义,因为不需要。 总结一下,我们可以用一个脚本来处理这些问题。 --------------------------fine_rep------------------------------ find $1 -type

构造过程

Jan 13, 2007 - 1 minute read - Comments

在进入正题前,我们首先回顾下我们的基础C++常识。如果调用某个对象的某个方法,那么会调用到什么? 一般来说,如果这个方法是普通函数,则按照这个对象的声明类型去调用。就好像(&obj)->obj_type::function(param…);。而如果是虚函数,则是按照这个对象的构造类型去调用。就好像(&obj)->((&obj)->_v_ptr[n])(param…);。或者说简单点,一个是按照这个类看起来像是哪个类来调用,一个是按照这个类实际是哪个类来调用。 那么,如果在一个基类的某个成员里面调用这个类的另外一个虚函数,调用的是哪个呢? 任何正常人来说,都应该说是,按照这个类的构造类型来确定。基本上没错,不过有一个函数例外。 那么先看一个问题。 class B { public: B(){test ();} virtual void test (){printf ("parentn");} void out (){test ();} }; class D:public B { public: virtual void test (){printf ("childn");} }; int _tmain(int argc, _TCHAR* argv[]){ D d; d.out(); return 0; } 想像下输出,再运行下。想想为什么,再看下面。想通了就不用看了。 ———————我是无敌的分割线———————– C++标准规定,任何一个带有虚函数的类都有一个_v_ptr成员,这个成员必须存放在这个类内存地址中头部。这个成员指向了这个类的虚函数表。于是,调用虚函数的时候,我们首先确定这个是虚函数。(按照这个逻辑,如果父类不声明为虚函数,子类重载为虚函数,还是没用的)然后,我们确定这是第几个虚函数(严格来说,这并不符合面对对象的设计规范,应该是按照函数名字查表的,_v_ptr也不应该仅仅指向虚函数表,而应该是类形态表)。最后,我们去虚函数表中取得入口地址进行调用。 那么为什么在构造函数中调用就无法调用子类的虚函数呢?问题在于_v_ptr的初始化时间上。某个类的构造函数启动前,这个类的_v_ptr才能完成初始化。如果是多重继承,那么首先调用最初类的,然后是次类的,最后是子类的。_v_ptr首先指向基类的,再是继承类,最后是子类。我们在父类构造函数中,_v_ptr指针还指向了父类的虚函数表,所以调用不到子类的虚函数。 其实我们可以这么说,构造函数以前,子类不存在。

IDE

Jan 12, 2007 - 1 minute read - Comments

现在真是深深的为IDE所苦啊。 基本来说,现在用的IDE有几种,eclipse,MSVC,Anjuta,MingStudio,Code::Blocks。不过都有毛病。 eclipse好用的很,功能齐全,插件多,支持多,跨平台。可惜开发Java是本行,C就稍微有点小毛病,而且消耗资源太大。MSVC也是功能强大,可惜Linux下面没法用,而且不支持CVS。Anjuta只是Linux下面的开发程序,而且使用了Automake和Autoconf。MingStudio不开源,Code::Blocks编译困难。 不过想想也是,IDE都又好用又免费了,M$要$哪个去? 其中唯一好用点的也就是Code::Blocks了。前两天看一个论坛上说Code::Blocks是针对单语言的,所以要用Anjuta。我立刻喷笑。说起来一个人能会多少语言呢?三种?五种?要真的是多语言,不如用Eclipse或者Emacs。Eclipse支持Java/C++/Php,Emacs配置好了啥都支持。问题是支持多了,效果就差了。Eclipse在支持C++上就和MSVC没的比。 要比较一个IDE,基本来说是比较三个方面,自动写作,生成和版本管理,统一化测试/调试。 自动写作有四个主要方面,自动完成,符号提示,参数提示,自动格式化。说明白点,自动完成,就是使用某个范围的某个东西,例如变量或者方法。在写好范围(例如对象名或者类名)后会提示这个东西的名字。好比写了::Messa就基本可以自动给出::MessageBox。符号提示则更加智能些,在写作的时候自动判断当前最可能使用的对象并且给出提示。参数提示是指调用函数的时候提示应该传入的参数类型和个数,当然也有自动将最可能的变量传入的例子。自动格式化,就是乱糟糟的代码自动格式整齐。针对C++来说,MSVC可以自动完成,符号提示,参数提示,外挂插件可以自动格式化。Eclipse可以自动完成,参数提示(这就是那个自动填写最可能参数的例子),外挂插件可以自动格式化。Anjuta和Code::Blocks没用过,不过Code::Blocks可以外挂插件格式化。 生成和版本管理来说,MSVC,Code::Blocks和Eclipse用的是自身的格式,脱离了IDE基本就没用了。Anjuta用的是Autoconf和Automake,即使没有IDE也可以编译。便于跨语言和发行原码包。 统一化测试/调试来说,基本都有行调试的功能,不过都不带测试工具的。

用户和软件制造商的博弈

Jan 11, 2007 - 1 minute read - Comments

作为用户来说,软件越便宜越好。制造商来说,越贵越好。 软件的价格和很多因素相关,生产基础成本,市场竞争,应用市场,技术含量。不过我们今天分析三种因素,服务,技术和市场。 软件的价格中,有很大一部分是用于服务的。大致上包括客户服务费用,安全保证费用(例如出现产品造成客户损失等等),软件升级和维护费用。免费软件和收费软件在这方面区别最大,收费软件自然可以做好(应该说是必须做好)服务,免费软件也可以做好服务。但是免费软件既然是免费的,让我免费写了大家用我不介意,反正没人用也是浪费,有人用还可扬名。但是还要提供服务,恐怕没人乐意了。所以免费软件的服务基本都是空白,或者是收费的(例如apache的文档)。这个因素基本和我们今天讨论的主题不相关,只是讨厌于某些厂商的服务质量有感而发。 市场的领域和含义非常复杂,大致上领域包括了某个产品理论可以用于的领域和当前用于的领域。理论上说记事本可以用于超大的程序开发,实际上你看到有人在用记事本写代码吗?含义的话,市场不仅仅是一个可用的范围,还应当包括所有用户和所有竞争对手,以及所有人的互相关系和当前状态。其实这已经是非常简化的状况了,软件的市场远远没有传统行业来的大,但是复杂程度却尤有甚之。美国的一个农民可能出售牛肉到日本,中国的一个农民也可能出售牛肉到日本。但是这两个农民互相间不认识,他们不构成直接的竞争动力。他们的代理出售者可能竞价,但是他们本人基本不可能调整自己的产品(当然,我也想像不出来牛肉可以怎么调整——除去中国某些恶心商人的手段外)。然而美国的一个公司卖软件到日本,中国公司也卖,他们一定认识,而且会根据对手行为和当前处境,以及客户状态来调整他们的产品。 最后一个是竞争的关键,技术。这里讨论的是广义上的技术,即抛却含量,纯粹从跑马圈地的角度来讲。如果讲技术的发展性,那最好大家公开所有技术内幕,不过看来不可能的。 技术的意义在于做别人不能做的事情。windows的进程管理器不能显示用户加载模块,sysinternals的就可以。这就是技术。有技术就有仿制。为了保持技术,一般有两种方法。一种是持续研发,成本高,但是优势十足。还有就是专利,恶心人的无奈东西。 如果说技术只是单纯能或者不能的问题,结合到市场上就有复杂的变化。最重要的一种就是利用技术特性来占领市场。如果某个产品是开放的,例如开放标准,出售代码。就可能出现很多不准确的免费仿制品。这些仿制品的大量应用奠定了这个产品的基础,使得产品具备非常大的市场和价值。然而市场,准确的说是用户,是具备产品粘着度的。也就是说,如果喜欢一个产品,就会一直使用这个产品。如果一个产品不具备粘着度,那就完全的没有价值了。因为他的用户随时都会转变为别人的。培育市场,就是培育大量的用户,并且使得他们具备高的粘着度。技术上说,存在这么一种情况,专利A,开放标准,出售研发代码(SDK)。专利B,封闭标准,出售研发代码,但是兼容专利A。那么专利B的产品会给客户一种导向,就是B比A更好。如果价格一样的话,我们不难想像客户的选择。这样的话A不仅仅是流失客户的问题,而且在后续产品上,用户会有惊人的粘着度。一直都是B专利兼容A专利,一直被压了打。 理论上这样会导致大家不愿意在核心格式上开放标准,然而标准的开放会带来非常广阔的兼容性好处。例如著名的开放标准XML,从技术角度讲几乎就没有什么难以理解的高级技术。然而这个标准本身却是伟大的发明。所以比较流行的方式应当是授权标准,标准是免费的,但是是授权的。如果在此上面衍生变化必须得到标准化委员会的认可,然而其中还是有很大问题的。例如微软就变更了java的标准,并且在事实上(虽然从来不承认)变更了html的标准。IE可以浏览标准的html,但是标准的html浏览器却不能浏览IE的格式。由此可以看出各个生产厂商在专利上的竞争方式。 作为厂商来讲,最好的运作模式是没实力兼容标准,这样用户觉得你功能强大。有实力就修改标准,这样可以养成用户粘着度。然而在用户看来,最好选择仅仅使用最开放最便宜的标准的软件。虽然这样会在使用中造成不便。然而却杜绝了大厂商篡改标准圈地的可能,在用户和软件公司博弈的时候获得更大的优势。

code2dia和cpp2dia

Jan 10, 2007 - 1 minute read - Comments

前两天找自动化工具,发现两个工具,叫dia2code和cpp2dia。两个都已经玩过了,还不错。这两个工具是基于UML的建模工具,和IBM Retional有异曲同工之妙,只是没有那么完整好用而已。 dia是一种矢量图编辑工具,其中包含了UML模块。不过只有UML图的建模工具是不完整的,dia2code可以将UML转换成多种语言的定义文件,其中包括了C++和java(我也就要这两种就够了)。画出关系图后,一条指令就可以自动生成代码框架,套用indent格式一把就可以拿来写了(java的话自然是eclipse)。美中不足的是,如果生成代码框架可以自动扩充就好了。例如当前我已经在某个框架上写了代码,然后发现要添加一个函数。难道还要重生成一遍,然后再Ctrl+C,Ctrl+V吗?回头估计要写一个程序来解决这个问题。 cpp2dia到是可以部分的解决这个问题。如果说dia2code是以UML模型为基础,cpp2dia就是以程序代码为基础。cpp2dia可以从代码中生成出dia模型来(当然,看名字就知道,只支持C++)。如果要添加函数,尽管修改代码,回头重新生成dia就是。不过这个毕竟不是比较完美的解决方案。 我做了一个测试。画了一个图形a.dia,然后用dia2code生成一堆框架。拿框架去套cpp2dia,结果出来一个output.dia。output.dia和a.dia拓朴结构一致,但是位置就差很多了(这也没办法)。最后用output.dia生成框架,生成结果和原来框架完全一致。 这两个工具的意义,在于编写代码的同时,可以清晰的看到代码的相互关系。代码写好了,文档也自然有了。UML图在手里面,代码自然也好写多了。同类的解决方案有IBM的Retional,Sun的JavaStudio,Microsoft的Visio,虽然都是要收费的,而且是白花花的银子啊~~~

超级牛力

Jan 8, 2007 - 1 minute read - Comments

用过debian的朋友,在用apt-get和aptitude的时候会发现有句声明。 #aptitude --help ... 这个 aptitude 没有超级牛力。 #apt-get --help ... 本 APT 有着超级牛力。 什么是超级牛力呢? 超級牛力是 Debian 系統中一股神秘的力量。 /* ..暴打ing.. */ 其实说明白点,超级牛力就是一个彩蛋。详细可以参看SuperCowPowers。 $ apt-get moo (__) (oo) /------/ / | || * /---/ ~~ ~~ ...."Have you mooed today?"... $ apt-build moo (__) ~ (oo) / _____/___/ / / / / ~ / * / / ___/ *----/ / / / ~ ~ ..."Have you danced today ? Discow !"... $ aptitude moo 此軟體沒有復活節彩蛋程式。 $ aptitude -v moo 此軟體真的沒有復活節彩蛋程式。 $ aptitude -vv moo 我不是已經告訴你這個軟體真的沒有復活節彩蛋程式了嗎?

中国的出国网络断了

Jan 5, 2007 - 1 minute read - Comments

同志们,由于人力不可抗拒因素(中国的出国网络海底光缆给地震震断了),所以我的blog不定期更新。 敬请耐心等待。

getline的效率问题

Dec 26, 2006 - 1 minute read - Comments

用过C++的肯定都知道getline(cin, str)这个用法吧,用于将某行读入到一个字符串对象中。但是根据我的测试,这个方法有严重的效率问题。 正则表达式行匹配器,匹配一个23M文件。用getline的总运行时间是21秒,用直接文件读取方法只有7秒。getline方法在屏蔽对读入数据的正则匹配后还运行了9秒上下。这里有人可能弄不懂,即使读取不用时间,getline花费的时间加正则运算时间不应该是总时间吗?结论是不是的,因为多个接口上下调用需要时间,str对象得到指针需要时间。所以其中还有一些时间差。不过getline方法效率差是显而易见的。 原因在于istream的类型和行的长度。我们是从文件中读取的,一次获得一个字符的取得的。ifstream应该没有弱智到一次只ReadFile一个字节,估计是用了1-4K的缓冲簇。对于大型文件,这个缓冲簇应该越大效率越高。但是stream不会知道输入流的长度,所以—— 而且即使知道了,50W个byte就是50W次call调用,花多少时间自己考虑吧。 还有一个是string类型的问题。getline istream一般都是用string作为接收对象的,因为string几乎可以无限制的接收。在STL的实现中,string是vector一样的连续块分配。当长度超出的时候,就必须重新分配,然后复制数据,删除原先块。因此STL中建议给string对象reserve一个块来提高效率。不过getline开始的时候会earse string对象,可能在这里面保留区域就被OOXX了—— 所以在大规模数据处理中,还是手来吧。