每周推特 2010-04-18

4月 18th, 2010 | Posted by | Filed under 生活轨迹
  • RT @rtmeme: RT @Hecaitou: 以前总是觉得自己很牛逼,BBS里开战,Blog里写文章,看到苍井空( @aoi_sola )一个小时飙3000Follower,突然感觉到自己做得很不够,不如一个AV女优,她们才是服务广大人民群众,所以也为人民群众所拥护。 #
  • 培训中不少应届的哥们回答问题纯从出题的意图去考虑,而不考虑问题本身,本来很简单的问题被分析的巨复杂,应试教育深入骨髓。 #
  • If now now, When? If not you, Who? #
  • @sdh5724 校长用什么算法做的? in reply to sdh5724 #
  • Itouch上可以维护mysql了 #
  • @yanzisky1989 马总的话,热血沸腾…… in reply to yanzisky1989 #
  • 面对小组5个女生都在高空抓杆抓到了,我感到压力很大……跳了一次没抓住,再跳第二次,终于抓住了……就算第二次不行还会来第三次…… #
  • @jxu 女生都抓住了,有的女生还是哭着跳出去抓住的,不抓住以后怎么混啊…… in reply to jxu #
  • @tinyData 只要自己足够胜任,相信公司会给你机会的,我也是这么进去的。想做就去做,并且证明出你能做的好。If not now, when? If not you, who? in reply to tinyData #
  • 审核SQL,建索引,本身是一件比较有意思的事情,并不想太自动化,也不太可能自动化,能直接看SQL执行计划已经比较满意了 #
  • RT @yanzisky1989: 唉,还以为是写给我的呢~心瓦凉瓦凉滴~RT @plinux: @yanzisky1989 马总的话,热血沸腾…… {也可以这么理解吧……就当是写给你的哈……} #
  • RT @jessie0816: RT @hecaitou: 肯德基终于为优惠券事件发布了珊珊迟来的道歉,而且没有任何补偿。网友夜壶评论说:道歉要有用,还要麦当劳干什么? #
  • 静静的积累,成为大牛;开放的分享,让团队都成为大牛;继续学习,再更牛。这是一个团队的良性循环,每个人都Open,让大家进步,也砥砺自己更进步。 #
  • @asword2000 MySQL的好说明,有源码。Oracle的从文档中来看,也是差不多的,要从文件结构来看,这得靠范牛把文件解析出来…… in reply to asword2000 #
  • RT @asword2000: 我们部门也是 RT @karlzheng: 我的主管刚刚和我说,我们需要两种人,1、牛人,2、女人,可见技术部门女性同胞的缺乏啊! in reply to asword2000 #
  • 看到测试人员辛苦的造测试数据,我感到非常非常的内疚,并且他们并没有因此不断的抱怨我,我更觉得无地自容。今后要像维护产品库一样保护测试人员的心血,对测试库要一样的投入心血保障安全。 #
  • @whitepoplar 原因是机器Crash了,并且再也没起来……同时没有备机 in reply to whitepoplar #
  • RT @hellodba: 希望今年我们团队把Greenplum这套系统接手过来,不仅仅是基础管理,更重要的是象Oracle,MySQL一样,把GP的思路和原理搞清楚,我相信这会让我们受益匪浅。//数据仓库的么,期待 #
  • 坐在休息区,一个不认识的同事过来,问我B树,一顿狂坎,我汗…… #
  • @asword2000 是你哇? in reply to asword2000 #
  • 趁着培训的空闲,查看了一遍产品库的status,发现产品库的参数还是有些问题,可能有潜在的隐患,下个季度应该要逐一人肉调整下。 #
  • @asword2000 不会吧,图在Flickr上,我看了也没红叉,难道你那Flickr被墙么 in reply to asword2000 #
  • @fire9 汗,这么严重,我这还好好的,GFW不同步么 in reply to fire9 #
  • 百阿结束,黄埔即将开始。今晚吃的很Happy,从来没有这么开放过,我竟然会跳舞…… #
  • David同学今天的交流还是比较实在,追求人生的小平衡还是大平衡,每个人都有自己的想法,都没错,都很好,但是永远不要去后悔自己的选择。 #
  • 哥哥结婚,很Happy,我也要~~~~~~ #
  • @yanzisky1989 已经结束了啦~ in reply to yanzisky1989 #
  • @yanzisky1989 真的哇? in reply to yanzisky1989 #
  • @yanzisky1989 ……嘛,还生气么 in reply to yanzisky1989 #
  • @yanzisky1989 你要我怎么赔……我蹲墙角…… in reply to yanzisky1989 #
  • @yanzisky1989 好吧……好吃的你自己挑 in reply to yanzisky1989 #
  • 到杭州了,好累~婚礼好好玩~ #

Powered by Twitter Tools

标签:

遗传算法聚类程序

4月 12th, 2010 | Posted by | Filed under 人工智能

何为遗传算法,概念性的描述我就不说了,摘自维基百科:

遗传算法是计算数学中用于解决最优化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。
遗传算法通常实现为一种计算机模拟。对于一个最优化问题,一定数量的候选解(称为个体)的抽象表示(称为染色体)的种群向更好的解进化。传统上,解用二进制表示(即0和1的串),但也可以用其他表示方法。进化从完全随机个体的种群开始,之后一代一代发生。在每一代中,整个种群的适应度被评价,从当前种群中随机地选择多个个体(基于它们的适应度),通过自然选择和突变产生新的生命种群,该种群在算法的下一次迭代中成为当前种群。

更详细请参考:百度百科维基百科

我来描述下我的问题,需要从数百万个5维点中选出32个聚类中心(可以不是原集合中的点),将点全部按就近原则聚类到这个三十二个区域,要求最终所有点到自己聚类中心的点最短。
初看这个问题,很多人会采用K-均值算法,不过我觉得这个问题用遗传算法做正好。
遗传算法

遗传算法实际上就像是在图中的曲线上放了个小球,小球会滚向我们所选区间的最低谷,如果选的区间大,运算量就大,但是不容易错过最低点,极限就是区间是全部X轴,这就成枚举了。而区间适当放大,在区间内滚动,然后随着滚动校正区间,可能就会获得最优解。但是也可能所选的区间不够大,小球落在极小点,而不是最小点。

可能描述有点混乱,请谅解,我文字描述能力实在是不强……

我解决这个问题的思路是,将32个点当做一条“染色体”,初始化随机100个“染色体”,计算适应度(每个点选择一个最近点,把距离加到总和)。
得到适应度后,为了保存优秀“基因”,我采取了“精英保留法”,每代选择最佳适应度的4个“精英”抽中其中一个直接进入下轮进化,而不参与变异,这样可以保证最接近结果的“染色体”被保留,又可以避免极小点被一直保留。
剩下的“染色体”每次随机选取两个,根据杂交率参数控制是否进行“杂交”,如果进行“杂交”,互换一部分DNA(中心点),得到新的“染色体”。
然后对新的“染色体”根据变异率参数控制是否进行“变异”,如果进行“变异”操作,则对“染色体”中的DNA随机根据最大干扰度参数改变值(就是对点的维度坐标稍微修正)。
最后为了程序不一直无限执行下去,设定最大遗传代数,来控制到了最大代数则停止,输出结果。

我的程序中Dat.txt是一部分测试数据,我转换成了二进制,在Dat.bin中,程序为了速度实际是读取Dat.bin中的数据。最后结果输出在Best.txt,包含选中的32个聚类中心,Res.txt包含了程序执行的全过程,包括每代的进化情况和适应度变化。
参数在Params.ini都可以修改,含义见“说明.txt”。

想测试准备好一下午,测试数据有十几万个点,可以算两到四个小时,算法还有优化的余地……

  GenAlg.7z (4.2 MiB, 1,200 hits)


阅读全文…

PostgreSQL的规则系统

4月 11th, 2010 | Posted by | Filed under 数据库

PostgreSQL提供了一种叫做规则(Rule)的机制,来实现一些与触发器不同的更加自定义的功能。规则系统介于查询编译器和执行优化器之间,根据规则及修改查询。

基本语法:

CREATE RULE 规则名 AS
    ON {SELECT | INSERT | UPDATE | DELETE}
    TO 表名 [WHERE 规则条件]
    DO [INSTEAD] {NOTHING | 命令 | (命令, 命令...)}

PostgreSQL中的视图实际上就是通过RULE来实现的。

例如建立一个视图:

CREATE VIEW view_1 AS SELECT * FROM table_1;

PostgreSQL实际将这个语句翻译为规则:

CREATE TABLE table_view_1 (涉及的列名);

CREATE RULE return AS 
    ON SELECT TO table_view_1 DO INSTEAD 
    SELECT * FROM table_1;

这样在查询view_1视图时,PostgreSQL实际上把它转换为对隐含的表table_view_1的查询。

在仅仅需要查询的时候,CREATE VIEW是更合适的语法,但是这这样建立的视图是不能做修改操作的,但是通过规则是可以做到的。

例如我们要更新view_1视图:

CREATE TABLE table_view_1 (涉及的列名);

CREATE RULE update_view_1 AS 
    ON UPDATE TO table_view_1
    DO UPDATE table_1 SET col_1 = new.col_1
       WHERE col_2 = new.col_2;

有了这样的规则,我们执行UPDATE view_1 SET col_1=x WHERE col_2=y;的时候,实际上就更新了table_1,这样就实现了更新视图。对于多表的视图,也可以这样操作。

每周推特 2010-04-11

4月 11th, 2010 | Posted by | Filed under 生活轨迹
  • @sdh5724 校长开始研究模式识别了哇 in reply to sdh5724 #
  • 看《风林火山》,也就武田和上杉能算得上有点战略,其他大名“大战”就是村长械斗抢地盘,不过我始终不理解日本无论哪个时代,天皇都没人敢动,虽然幕府将军掌握实权,但是为啥就是不敢篡位,在天朝,历朝历代将军权倾朝野,皇帝必然死翘翘。 #
  • @sdh5724 咱们的环境不太好模拟,从CodePK的平台接口来看,数据没有共享区,全靠字符串参数传数据,本地多线程方式调通了,改成接口传上去隐含的指针操作依然会Crash掉Master,因为Worker会跑在不同主机上,但是全局内存不会传过去,就这点麻烦。 in reply to sdh5724 #
  • 花了两天搞CodePK,明天要搞XML提取SQL的程序了,wxWidgets功能有点弱,长远考虑还是QT写吧,免得以后又重构麻烦,自带的OCI接口可以静态编译,搞成单文件方便。 #
  • 相比MFC和wcWidgtes的消息驱动,我还是喜欢QT/C#这样的事件驱动,事件去连接操作,代码控制起来会比较容易。 #
  • 我觉得一个能让开发人员快速上手的分布式系统,或者能提供自动序列化的接口,让数据的序列化与反序列化交由系统统一完成,或者对集群进行统一重新编址,分派到Worker的代码,能通过变量的全局地址去相应的主机自动寻址需要的数据。 #
  • RT @Fenng: 王江民的自强不息曾经不知鼓舞了多少IT人,王先生一路走好! in reply to Fenng #
  • 不知道为啥QT的XML解析组件总是报iBATIS的XML不符合标准,用Perl的XML::Simple就行,QT就纯做界面好了。 #
  • 提取SQL完成,下面通过information_schema获取列的类型,然后填充到抽象的SQL,丢到数据库去拿执行计划。 #
  • RT @lewvip: 昨天配了眼镜花了1100多,其实也就是公司能给报眼镜费我在配那么贵的,没觉得和几百块的眼镜什么区别 {配眼镜都能报销……} in reply to lewvip #
  • 今天是蒋公逝世35周年 #
  • 看进度明天让MySQL团队也用上SQL审核辅助工具是可能的~ #
  • CodePK,53进18胜出,18进6挂的很惨,只有一件T-shirt,但愿明年还有,很好玩 #
  • @asword2000 Oracle的搞出了原型,MySQL的我搞了XML提取SQL和执行计划提取,自动建议还没搞好,我想先做出自动建索引的部分,自动建议才好搞。 in reply to asword2000 #
  • 明天GF生日,送啥捏 #
  • @asword2000 成本太高,后半个月我就得要饭了 in reply to asword2000 #
  • 226路的司机我只想说,草泥马,连续两天到站不停,公交车开成F1,敢去投胎一样,逼我打车回家 #
  • @asword2000 把自己送过去就难了,我也想哇……飞机还得两小时呢 in reply to asword2000 #
  • RT @dttoo: 我喜欢工科的男银,不是读纯理论的,比如在我们家遥控板或者电话坏的了,我哥就能拆开,然后鼓捣鼓捣就好了,我就可以继续看电视了= =|| #
  • PGSQL连锁和信号量的控制都放出参数,NB #
  • @yanzisky1989 这种事情还是我来吧,你不专业~ in reply to yanzisky1989 #
  • 国家每年财政收入这么多,还好意思号召我们捐款,自己的钱哪去了,我们交了税还得捐款,我们P民就是党的ATM #
  • 测试库虽然没有线上库重要,但是单点也是需要避免的,停机一天的浪费的工资,估计能买好多台新服务器了。 #
  • 向一个正在做压力测试的数据库导入数据是一件多么悲剧的事情…… #
  • 关于二叉查找树、红黑树、平衡二叉树、B树的区别和联系,貌似大部分同事们都不太了解,做个PPT,有时间分享一下。 #
  • 就剩最后两笔导入了,速度…… #
  • 已经做好了RT @asword2000: @plinux 做完share一下,建议群发ali-tech^_^ #
  • 我竟然走到家了,我的体能还是很彪悍的,不过真的很累,一路上盼望taxi的期望都落空了,哎。。。睡觉! #
  • RT @qiyi: 哎,IE是各种不支持 {更悲剧的是只支持IE} #
  • @xlight 做成数据库算法与数据结构系列,会发在博客的 in reply to xlight #
  • 我的iBUS怎么就挂了捏 #
  • DBUS的socket拒绝访问导致I-BUS不能启动,HAL的错误导致DBUS不能正常读写socket,I-BUS的问题最终归结于HAL #
  • 貌似来了个PostgreSQL大牛 #
  • 越看设计模式越觉得我不会写程序,只是Writing,不是Coding #
  • 百阿就要来了,同事苦了,要顶我这一堆数据库 #
  • 看到CodePK颁奖的邮件,很郁闷的说,如果能早点反应过来不用sqrt,不带来精度问题,也许能冲进决赛 #
  • RT @kisafran: 真好…RT @yanghengjun: 最新新闻:波兰发言人表示,现在的波兰没有左派和右派,人民团结一致。啊,太美了,中国现在左中右都有啊,建议领导人集体自杀以团结国人,让我们重拾对未来的信心! #
  • 看07年的Discovery宇宙特辑,讲太阳的这一集,说如果太阳的耀斑正好旋转到对准地球,一次爆发相当于把一个珠穆朗玛峰的质量抛向地球……算算太阳活动周期,科学家认为下次太阳活动周期大约在2012年。我觉着2012这时间挺靠谱的,地球真不行了么 #
  • 如果太阳风暴袭向地球,强大到逆转地球的磁力线,离子随着磁力线到达地球表面,地球上跟电有关的一切东西将不可使用。而且这事发生过,1859年,只不过那时受影响的只是电报。现在可不一样了,全球停电几周,引发的混乱就不是那么简单了。 #
  • 火星果然比地球安全,火星是个铁核,强大的磁场足以保护火星表面不受太阳风的影响。也许生命的起源就是火星,火星的早期碎片把生命带到了地球,咱们以前都是火星人。地球太危险,咱还是回火星吧,这句话多么有前瞻性啊,哈哈。 #
  • RT @zhyu: 说我呐 RT @HolicAS: 考的再糟糕也比线高30+分RT @smy20011: 要达到什么成绩高考才叫“上一本没问题” //提前拿到保送资格 #
  • 帮朋友配了7台服务器的监控,累死了 #
  • RT @whitepoplar: 数据库系统概念无疑是数据库领域的bible {书太厚了,先从Ullman的数据库系统基础教程开始看,看了看也不基础……} #
  • @whitepoplar 我从大三看到现在才看了155页……悲剧啊,纯学术性的概念有的还是蛮难懂得,你看完了我来请教你 in reply to whitepoplar #
  • 为GF找一份在杭州的工作,PS.英语专业。 #
  • 补充:目前大三,实习。 #
  • PGSQL的遗传查询优化器真TMD牛B,处理45个表的关联查询都能给出不错的执行计划,System R的动态规划算法在这种情况下处理时间已经明显不行了。 #
  • RT @sdh5724: 其实, ubuntu对中文来说, 缺乏一个很好的字体。 需要去windows/mac上去偷几个字体, 这让我觉得很不爽。{文泉驿的字体还是蛮不错的吧,我很喜欢这套字体} #
  • @asword2000 没有编辑之类的办公室工作么,不指望她赚钱,满足下她想工作的愿望,还有就是能待一公司 in reply to asword2000 #

Powered by Twitter Tools

标签:

数据库算法与数据结构系列——B树相关

4月 10th, 2010 | Posted by | Filed under 数据库

后续还会有排序相关,缓存相关,锁相关等内容。