Monthly Archives: August 2011

必然性与偶然性浅议(老贴重发)

这周的任务又没完成,只好把09年写的一篇老文章搬上来,这篇文章最早帖在88的史版上,热烈讨论了一个上午,一直讲到了量子力学,可惜后来要考试,等考完回来,发现帖子已经被版主合集了,后来放到人人上,也没几个人看。当时这文章就有很多地方言有未尽,可惜年纪越大越没心情改了,再贴一次,就当抛砖,不知道能不能引出一些有意思的讨论。 ================================================================ (以下的一切讨论基于一个大前提:世界是爱因斯坦所认为的绝对的因果系统。即没有无果之因,没有无因之果,或者按力学上的说法叫力是改变物体运动状态的充要条件) 历史的必然性与偶然性问题在某种意义上是属于历史观的基本问题,是一个人基本价值观和世界观绕不开的话题。 那么,历史,或者说我们所经历的一切究竟是偶然的还是必然的? 咋看起来,好像两种答案都有道理。 例如以硬币为例,一枚硬币落地,结果的正反已经可以认为是经典的偶然事件(或者叫随机事件)。但是,如果在世界是绝对因果系统的假设下,我们就会发现,硬币落地的结果已经由经典力学唯一确定了。如果我们能精确测算扔出硬币的角度,力量,硬币的受力点等相关参数(而且并不需要知道所有的参数,在这个例子中我们只需要知道关键的几个就行,像空气阻力之类的都可以认为没有影响),我们就可以知道硬币落地的唯一结果。所以这枚硬币抛出去的一瞬间,它落地时的正反已经只剩下唯一的答案。而且更恐怖的是,由于世界是绝对的因果系统,所以我们前面提到的扔出硬币的角度、力量等“决定”硬币落地结果的参数同样是可由之前发生的“原因”进行推算。照此推理,可以一直追溯到宇宙起源的那一刻。所以在绝对因果系统这个大前提下,宇宙中每一刻发生的一切都在宇宙诞生的那一刻,由那个唯一的输入决定好了。所以历史显然应该是必然的。这倒与古人提出的“天命”,“命运”暗合了……虽然可能出发点不大一样,意思也不完全相同。(刚想到这一点的时候还蛮兴奋的,后来才知道19世纪拉普拉斯学派早就提出类似的观点,并在欧洲风靡一时了--) 可能会有人提到“测不准原理”,其实如果承认绝对因果系统这个大前提,那么“测不准原理”也可以解释为“结果确定,只不过超出人类测量认知的极限罢了”,分子间的热运动并不是无缘无故的,显然也是受到了原子间作用力的结果。只不过人类永远不可能同时测准能量和时间(而这恰恰是由于在这个尺度下人类找不到更小的工具来测量,导致测量的过程直接干扰了结果而已)。 所以所谓的偶然和必然,不过是按照我们人类自己的观察能力进行的分类。当我们所掌握的信息能准确地预见未来时,我们就称其为必然的,当我们所掌握的信息不能准确预知,甚至毫无头绪时,我们就称其为偶然的。 而且事实上,我们永远不可能掌握完全的“信息”,因为宇宙是一个所有事物都彼此联系的混沌系统。任何一个微小的扰动都可能带来结果的巨大“变化”(这个“变化”指事实和我们的预期之间的偏差),具体的例子可以参考“千里之堤,溃于蚁穴”,“蝴蝶效应”之类,这里就不再赘述。而从微观角度讲,由于“测不准原理”的存在,我们所获得信息的“准确度”又不得不由于尺度的限制而大打折扣。所以我们平时的决策都是建立在“不完全又不精确”的前提下进行的,从这个角度来说,人类的每一次决策都是一次赌徒式的行为,我们要么看到只是装着筛子的黑盒,要么就是自以为撇到了某张牌面。这也难怪“神话”中的诸葛亮最让人敬佩的就在于他的“算无遗策,料事如神”。而基于以上的理论,我们知道这样的人几乎是不可能存在的,或者就算有接近这一高度的人,也只能称为“智慧与运气”的化身,或者“运气”的化身可能更准确一些。 现实中比较理想地反映这一事实的模型有很多。比如股票。如果你获得了所有的信息,你自然可以精确预测股票的涨落,但是如果你只获得了99%的信息(这里的百分比是指信息量),那你即使比起一个啥也不懂只掌握5%的信息的人来,也是毫无优势。因为你所缺失的那1%的信息可能恰恰会使结果与你的预测完全相反。(提前评估一条信息对结果的影响力的难度恐怕与预测这个结果本身一样难) 这里其实还可以得出一个推论,宇宙中的一切要么都可以被“精确”预测,要么都不可以被“精确”预测。因为要“精确”预测某一件事(不管是哪一件事)都必须要获得宇宙中的所有信息,或者是能够推导出所有信息的输入(根据前面世界是普遍联系的混沌系统的理论)。而一旦获得了这些,就足以“精确”预测宇宙中的每一件事,过去和未来,宏观到微观,一切尽在掌握。 所以从这个角度去看必然与偶然的话,我们可以这样说:从世界是绝对的因果系统的角度来看,历史是必然的。从人类预测能力的限制来看,世界上的一切都是偶然的。(因为都不是可以精确预测的) 当然这里提到的是“精确”的预测,模糊的预测我们还是可以做得很好的。比如天气预报。天气系统是典型的混沌系统,记得中学时就看到一本书上说,天气是无法预测的(而且当时的天气预报也确实是很不准,记得小学时还做过一个很有说服力的统计--)。但是,现在天气预报的精度提升是有目共睹的。我们在预报时永远无法得到100%的准确率,但是在不考虑某些特定的扰动的情况下,我们也许可以把准确率提高到90%以上(好像现在的晴雨预报准确率已经高于80%了)。而像抛硬币这样的活我们甚至可以让预测的结果达到99%以上的精度,无限接近100%,(因为测量那些关键数据的仪器似乎并不难做。而抛硬币者突然中风、仪器损坏、停电等小概率意外似乎也难以避免。)而即使精度达到了99.999999。我们仍不能取消偶然性,因为这0.000001%的存在,我们无论哪一次预测都不能拍着胸脯说这一次100%是对…… 回到正题,(似乎跑得有点远),其实这篇文章的本意还是想说明历史的必然性和偶然性,而不是说预测的。(当然两者有很深的联系)。按照上文的假设、推论。我们可以得出结论,以前教科书上关于历史必然性与偶然性的论述有很大的问题。历史的确是由人民创造的,但是并不仅仅是由人民创造。所有的人,宇宙中的一切都对历史的演化有着贡献,(因为普遍联系的存在)。而所谓的英雄人物也未必比自然界的一道闪电有着更大的影响。至于所谓“如果拿破仑不存在,那么会有另一个‘拿破仑’来代替它”的说法也是不正确的。这种说法其实落入了一种“宿命论”的怪圈中。如果如上文所言,世界的一切都是确定的,那么“拿破仑不存在”这样的“如果”就永远不能成立,如果这条假设成立,那么整个宇宙都将崩溃。(这一点很好想象,因为拿破仑的诞生是一系列原因作用的结果,同时它自己做为“原因”与其它条件互动将时间推动到现在,如果单独的把这一点摘去,就必然导致许多无因之果和无果之因,而这样的宇宙在开篇的大前提下是无法维持的),即使不考虑这一点漏洞,我们也可以发现,如果拿破仑的作用很大(大到直接影响“宿命”的程度),那么没有人可以代替他。如果拿破仑谁都可以代替,那么要建立法兰西第一帝国,也不一定一定要一个拿破仑式的人物了。   唉,一边写一边跑题,写得很乱,以后再改吧,欢迎拍砖。

Posted in essay | Leave a comment

写篇软文——关于CCTV2转职成baidu频道的感想

中央电视台2套节目这两天变成了“百度”频道,连篇累牍,滚动播出,”揭开百度推广背后的黑幕“,今晚还捎上了贴吧。明天不出意外可能还会继续这个专题,有些地方看过之后让人不吐不快,因此写了这篇软文。在此表示本文只表明个人观点,与任何组织机构无关。 央视头天的节目虽然有明显的偏向性,为了得到自己希望的结论,使用精心挑选的材料,并且使用自己擅长的钓鱼找托等手段曝光了一些凤巢系统的问题,但是客观地说许多问题确实是存在的。可是这种报道的手法明显不是一家大型官媒应有的做派,更不是一个有社会公德心的媒体所应有的手段。我们都知道媒体喜欢放大一些细节,因小见大,同时客观公正也是媒体应有的一个必须属性。但是央视在这里倾向性地选择材料,完全无视了百度推广帮助数十万家中小企业主找到了一个廉价的推广渠道,优化了国内工业界生态圈的普遍事实(在这里暂时不提网页搜索对网民的贡献),片面地强调虚假广告的案例。但是我们知道广告界的虚假广告问题是一直存在的,地方台各种乱七八糟的小广告和电话直销我们暂且不提,就说央视自己也曾经放过虚假广告(最大的一次就是曾经当过标王的“曲美”)。而在互联网上的推广链接,它面对的是低门槛的中小企业主,广告链接过去的网站内容是不由媒体(百度)本身掌握的,而是随时可以由广告主自己改动的网页,本身在审核上就有许多比传统媒体的审核更困难的地方。目前在这一方面,立法、监管、百度自身的审核技术和审核流程确实都有许多需要提升的地方,但是这些不能成为彻底妖魔化百度的理由。看这个节目简直就是要做到把百度停业整顿,才能对得起互联网的良心。但是事实呢,真的考虑到百度对大部分中小企业主的贡献,对那些需要在网上寻找所需商品和服务的网民的贡献,功过至少是9:1吧,如果算上百度对普通网民检索信息的贡献,这个1只会更小。 至于第二天的节目则基本上只剩下赤裸裸的攻击了,如果说第一天的节目央视还算是花了些功夫去调研百度相关的系统的话,第二天的一些结论让人感觉完全是赶工的结果——太不专业,泼脏水都能不专业到让人愤怒……首先是请了cjm,我不知道cjm教授有没有上过论坛,一个论坛出现谩骂之类的言论是可以要求斑竹删帖的,但是删帖后还要求整个论坛都关掉,合理吗?cjm之前做的事我不评价,但是既然是个教授和公众人物,提出这个提案就应该有这样的心理准备和觉悟,另外现在天涯和猫扑上还有骂您的帖,需要把这两家论坛也关掉吗?至于掘金项目是什么,建议央视的工作人员自己去好好看看介绍,不要花多少时间。没想到他家居然拍脑门子断章取义,把精准推广的广告和贴吧广告混为一谈,真是让人笑掉大牙。搜狗做假药广告当年是央视曝光过的,怎么突然就这么一脸正义地出现在摄像机前?两家都有失忆症么? 我不想评价某些中小企业主的思想,如果百度推广真得如报道般不堪的话,现在是不会有几十万家广告主还在继续在百度上投放广告的。树大招风,这么多广告主有1%的人不满,就够央视采访一年的了。我想对央视广告不满的广告主应该也不少,没有坚持一直在央视投放广告的肯定更多,我想新浪哪天是不是也可以去挑出一两个来好好采访采访,保证爆出来的料不比这次的差。那个04年5元涨到11年15元的例子,稍微有点常识和智商的人都能看出04年到11年CPI的涨幅是多少?中国的网民数翻了几倍?互联网广告市场又增长了多少?即使是身处发展缓慢的传统媒体广告业的央视自己,他家的广告收费这几年难道就都没涨么?! 还有一个广告主说停止投放广告,网站就会被加入一个“黑盒子”,三个月不能上首页。首先,我从来没听过“黑盒子”这个名词,其次,真正了解百度搜索机制的人都知道,这样的黑盒子在百度搜索现有的技术框架下是无法实现的。所有的百度rd都可以看到百度内部所有的代码,百度的离职率又不低,如果真有这个东西,早就有人爆出来了。最后,哪怕不考虑技术细节,难道央视的编导认为一个小小的销售打个电话就能操纵本来完全由机器和算法控制的搜索结果了吗?他难道以为百度内部是用人肉来给网站排序的?网站被封禁是有可能的,但是这个完全是自然搜索的封禁策略,和商务搜索无关,前方的销售更不可能接触到自然搜索的技术人员,去人为干预这个结果。而网站被封最可能的原因正是那个广告主说的,他投入大量人力物力去搞SEO,而过分地SEO导致某次不小心触犯了某些规则,而被百度的系统判定为作弊,从而被封禁,这点我想有SEO常识的人都会了解。这个广告主花了那么大的成本去投SEO,难道就一点都没关心过SEO也有SEO的规则吗? 至于后面说的很多广告主抱怨百度推广价格昂贵,效果不好,我都懒得反驳。首先这是个完全自由竞争的市场,百度虽然目前有垄断的地位,但是并没有利用垄断优势去压制搜搜、搜狗之类的竞争,如果范围更广点,在媒体广告领域百度更不具备任何优势,相比CCTV,百度只是只小虾而已。既然这些广告主觉得百度推广物无所值,成本太高,他们完全可以去别的地方推广,去别的媒体投广告,或者干脆停止做广告。百度并没有拿着枪逼他们做善事。可是我们看到很多广告主一边抱怨一边继续把“95%的利润”投到百度推广中,这是为什么?是不是说明如果停止了推广,他们连现在5%的钱都赚不到?如果不是的话,他们就应该早早停止推广,否则这样的nc言论如何能出现在中国最大的官方媒体上?事实上在百度推广以前,中小企业的生意并没有现在这么好做,要想把摊子铺到全国,有几家中小企业交得起传统媒体高昂的广告费(央视就不说了,就是地方电视台都比百度点击一下几块钱的收费贵得多得多)。可惜人心苦不知足,那些被采访的广告主似乎希望最好有一些推广效果好,又几乎不用花钱的渠道,真是有点贪得无厌了。当然买方和卖方的矛盾总是存在的,但是在市场机制下,这并有没有谁对谁错的问题,买家嫌贵,卖家还嫌便宜呢,至少百度没有自己定价,而是用了竞价,而且一个愿买一个愿卖,也没有搞央视那样的黄金时段投标和标王的噱头,至少还加入了质量度,使得结果不是单纯的竞价。我不明白央视怎么就能义正辞严地一边炒作自己每年的广告标王,一边指责百度只认钱呢? 至于最后搬出来的当当和京东就更加搞笑,完全是赶工出来的断章取义,他们确实在三月份声称过要减少甚至是停止在百度的推广,但是之后当当的营业额直线下降,不得不重新加大投入(这从侧面也看出百度推广的效果),而京东的老刘则更是直接在微博上对他之前的言论作出了道歉。还有那个搞笑的马云,阿里的公关水平确实很好,但是阿里巴巴之前的诚信危机和淘宝一直以来猖獗的假货问题……真不知道央视是怎么挑人的,选谁来讲诚信我觉得都比这家合适些(我并没有怀疑马云本人的人品,但是之前他自己在回应淘宝假货的时候说过淘宝无法监控这些假货,事实上现阶段的互联网还没有一个很好的机制来产生一个低成本低门槛的线上工商局,大家都面临同样的问题,在这种时候央视把他搬出来实在没有道理)。 这次的节目到明天不知道还会不会有续集,或者央视会不会调转它的枪口。至于这次央视报道的目的,目前来看也可能有很多种的理由,旧媒体打压新媒体也好,为加强互联网监控造势也好,收保护费也好,不管出于怎样的目的,用这样的手法都让人觉得不耻,不是一个公正客观的媒体人为达目的所该使的手段。写这篇软文,我也只是觉得有些事需要澄清一下,不管出发点如何,央视这么做至少已经伤害了在公司内所有合法守纪、为加速互联网上信息流通、健全互联网生态环境而努力的百度人的感情,拿一家公关孱弱的公司来祭旗,柿子挑软的捏,实在有失第一官媒的身份!

Posted in Uncategorized | 82 Comments

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

这篇主要是基于《精通正则表达式》的一篇读书笔记,因为书还没看完,可能以后还会有相关的笔记。(工作以后看书的效率真的很低啊……) 正则引擎主要可以分为基本不同的两大类:一种是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