2012年12月17日星期一

SSH配置好RSA后还要密码的问题

之前一直都懒得给VPS配置好RSA无密码登录。今天想想反正短期内都要用,所以就写了个登录脚本,同时管理几部server。

先是改好config文件,因为我改了VPS的SSH端口。然后ssh-copy-id 把publick key传过去。按道理这时候应该可以SSH无密码登录了。但是输入登录命令后,居然提示还要密码!
然后用 ssh -vvv user@server 详细看了下登录过程,可以看到公钥验证失败。登录其他主机明明是可以的呢。。上网一阵狂搜,发现极有可能是权限设置问题。但是中文社区一般都说:
1) /etc/ssh/sshd_config 配置有问题
2).ssh/ 目录权限有问题

检查之后发觉都OK,最后终于在这里找到答案 = =
found out the culprit the permissions of the /root (770) drwxrwx--- 70 root root 4096 2011-07-27 00:37 .. was too open. Changed the permissions to drwxr-xr-x and now it's working. Couldn't imagine the fact that parent directory's permission affect the ssh.
上一层的用户主目录权限影响到子目录.ssh/的使用?....好吧,改了之后确实好了
这里感叹一下,英文社区的氛围确实不错,回答都好详细...

2012年12月4日星期二

SCUTOJ 建站手记(3)--- 压力测试 & 性能监控

又是抽一些空隙时间,基本完成了SCUTOJ的压力测试,参考的是《构建高性能web站点》,但是过程中还是遇到不少问题,这里记录下。

硬件环境:

首先是在本机用 webbench 这个小巧的测试工具对远端的服务器进行测试。小是小了,可惜功能太少,结果太简单。


可以看到,并发数分别为:100, 500,1000,2000,持续时间均为30秒。
页面响应速度分别为: (pages/min)
5244
5220
6950   fail : 0.7 %
8022   fail : 2%

从1000开始已经出现fail了, 并且随着并发数增加,失败概率不断增大。

再看一下apache mod_status 的数据:

空闲的时候其实只有4个线程(worker),并发数500的时候已经升到138了,到1000的时候好像也没有大的变化。看了一下apahce2.conf,maxClient设置为150.

由于webbench测试是在图书馆做的,带宽还是挺不错的,看了一下下行速度,有1M多每秒。应该说线路带宽当面对结果不会有太大影响,延迟就不敢保证了 = =

2012年11月23日星期五

SCUTOJ 建站手记(2)

由于这一段时间一直在忙各种实验和课设,而且目测还要忙到差不多期末,然后又差不多要考试,所以总体来说项目进度比较慢,还是断断续续的。目前只能说把网站搭起来了,但是还需要继续深入进行二次开发,而前提是需要先大概过一遍源代码,某些关键的地方还要多加留意才是。
目前主要的问题是没有专业的web前端人员啊!只能是在下先大体改了一下界面,但是毕竟不是专业美工,效果肯定不咋的。。。今天刚好有时间,就收拾了一下界面,顺便把域名弄好了(上次注册到的tk域名竟然被回收了,完全不明所以啊 = =希望这次没事。。。)

=========================
由于在理想规划中是不止一个子域名的,这就需要用到基于域名的virtualhost配置了。关于apache虚拟主机的配置网上有很多,这里就简单说一下。

#环境:ubuntu 10.04 LTS 
#创建virtualhost配置文件
cd /etc/apache2/sites-available/
copy default scutoj      //copy一份默认的配置再修改,比较方便

其实要改的只有几处:

<VirtualHost *:80>        //服务器只有单IP的情况下这里不需要修改(个人理解)
ServerName www.example.com              //自定域名
DocumentRoot /var/www/                //这个有需要的话可以该,我将它指向OJ的根目录了,也就是直接访问IP的话就进入OJ的根目录index页面,以前要手工输入目录名,不然就是默认apache的index.html
其他貌似没什么改动了,还有一个ErrorDocument的参数可以添加,可以自定义出错页面,比如diy的404...


然后就是启用域名:
sudo a2ensite scutoj    //apache2 enable site的缩写,其实就是在sites-enable/里创建symbol link,指向VH的配置文件
sudo service apache2 restart

关闭网站服务: sudo a2dissite scutoj
====================

接下来的计划其实蛮激动人心的 = =!!
因为自从我在SJUT-NIC回来之后,就对web application产生了相当大的兴趣,对web架构,web服务器,数据库以及众多的web开源框架与应用之类的都有莫名的冲动~希望能自己亲手实现一下。
在目前OJ的系统当中,只提供了基本的judging和contest等等服务,原生论坛太搓,所以准备自己搭一个论坛挂在主站上面,想试试Rable(基于Livid的PB2)。最近泡V2EX比较多,觉得论坛的话还是这种比较好~更重要是的想玩玩Ruby on Rails啊!(其实《python学习手册》我都借回来了,暂时还没时间看...但是ruby对我来说更有神秘感,嘛,可以都看看,到时再决定用python或者ruby或者PHP。
另外还需要一个关于ACM的文档和心得体会分享平台,用mediawiki搭一个wiki感觉上是个不错的方式。个人也很喜欢wiki的分享方式,只是不知道实际运营起来效果怎么样。

这样算下来,二级域名下面就有三个子站了,还是蛮不错的~有得折腾~

其实这些天一直在想另外一个很现实的问题,就是:OJ该由谁来负责长期运营和维护呢?在下是真心不想交给学院,事实证明无论什么东西,到了行政机关手里都会变成一堆渣渣 = =
在下希望这是一个有活力的project,以至于product。所以一个好的管理员或者管理团队是必须的,就好象Livid一个人给整个V2EX注入了灵魂,这个社区才能通过口碑吸引不少高质量的用户。这方面感觉其实SYSU做的挺不错的,他们的官方OJ是由ACMM协会负责维护的貌似,还有一个很萌的吉祥物sicily。POJ或者HDOJ都比较正式和官方的感觉,但毕竟是老牌,所以题库和用户积累是个很重要的因素。

综上所述,SCUTOJ要走的路还很远啊。。。希望不要半途夭折就好Orz

PS:近期准备学markdown,在github page上个octopress,因为blogspot实在太蛋疼了。。。希望在下次有需要写post之前能弄好吧。。。

2012年11月4日星期日

SCUTOJ 建站手记

鉴于某学院的说法:你们不做出点样子(UI)来,我怎么好给你服务器呢??。。。 = =
好吧,既然这么蛋疼就先在VPS上面搞好了。。。(一上来就吐槽学院好像不太好的样子??

主机的话,原来想选Linode的,心想咱们也好不容易可以做一回壕啊。最后考虑到毕竟是测试阶段,服务器没必要选的那么好,所以退而求其次,选了xehost(在V2EX看到的,刚好碰上搞活动的说)。XEN主机,美国机房,ChinaCache线路,电信ping值在150-200ms之间,勉强还可以接受。价格的话略贵吧,月付80大洋。

硬件配置:
Xeon E5606 @2.13GHz 双核
512M RAM
20G 空间
500G 流量
100Mbps 带宽 (实测有接近2M/s的速度
磁盘I/O 测试了一下,40M/s, 勉强吧
系统 Ubuntu 10.04

======================================

hustoj代码托管在google code,要用SVN checkout(其实我还是更喜欢github)

svn checkout http://hustoj.googlecode.com/svn/trunk/ hustoj-read-only

进入到hustoj-read-only/install 目录中,修改一下安装脚本,把yum系的去掉,注意下数据库的用户和密码就可以运行了。其实最好就是手动安装一次,这样对整个架构就有个大体的把握了。

还有web服务器关于php脚本的设置:
       sudo vim /etc/php5/apache2/php.ini 
       open_basedir =/home/judge/data:/var/www/JudgeOnline:/tmp  
       max_execution_time = 300     ; Maximum execution time of each script, in seconds
       max_input_time = 600 
       memory_limit = 256M      ; Maximum amount of memory a script may consume (16MB)
       post_max_size = 64M
       upload_tmp_dir =/tmp
       upload_max_filesize = 64M
设置完以后重启apache。

在浏览器输入IP/目录,应该可以看到页面了。如果出现网页一片空白的情况,说明php脚本有语法错误或者web文件目录权限设置不对。这时候可以打开php.ini的display_error 选项,可以方便排除错误。debug完之后建议还是关上。默认,php报错是不记录进日志文件,这很不便于排查问题。打开php的错误日志记录也很简单。编辑php.ini
log_errors = On
error_log = /usr/local/php/log/error.log

========================================

接下来就是折腾DNS了。
偶在dot.tk上面注册了scutoj.tk的域名,其实也只是实验阶段,免费东西不知道靠谱不,到时有条件还是转.me好了(其实很想注册个像中大的那种短域名啊soj.me )。其实原来想用DNS Pod的服务(据说对google DNS和open DNS有优化,不过按照最近斯巴达的网络状况,8.8.8.8都全挂了 = =),但是懒了一下,暂时没弄。

后台添加一个A record,指向VPS的IP地址,主机名就写www。但是这样的话只是指向/var/www目录,而OJ是放在其子目录下。以前没试过子目录绑定域名,又是google上一阵狂搜,折腾啊~

最后发现是需要设置apache。这里又涉及到各种linux distribution的apahce配置文件位置不同名字不同 = =!,最后还是在ubuntu wiki上面找到官方说明,是设置apahce virtualhost。具体可以看这个链接。还有就是NameVirtualHost *:80 ,这里在 /etc/apache2/port.conf 里面已经设置过了,再在default里面设的话可能会报warn。只需要注释掉其中一个即可。

我记得以前在SJTU-NIC的时候有看过下apache的配置文件,过了几个月竟然忘得七七八八了。。。哎,这记忆力,跪了。




2012年11月3日星期六

基于OpenStack的Online Judge实现构想

应该说吧,这个构想在po主接下老师项目的时候就有点思路了。当时刚好接触openstack不久,对云计算有点概念。感觉openstack和OJ是可以结合起来的,当然具体的想法是经过了解openstack以后渐渐的明朗起来。

先交代下目前的状况。某理工作为国内排得上号的211,985传统理工学校,还没有一个像样的OJ系统。所谓的不像样,就是该OJ即使是面对两个班(大概一百多号人)同时上机实验都会随时崩溃...对于校赛这种就更不用说了,我们学校的ACM集训队从来不敢用我们自己的OJ,都是到杭电上面去搞contest...

Online Judge某种程度上也算是SaaS,为用户提供在线判题服务。用户把代码提交上去,服务器经过计算将结果返还给用户,典型的B/S架构。这样说的话,其实是单节点服务器就足以应付的小型应用(对于我们大SCUT来说还真是= =!)。但是单纯从web架构方面考虑,这里面还有很多需要改进的地方。最简单直接而且立竿见影的方案是,将LAMP架构换成LNMP架构,也就是apache + mod_php 改用 nginx + fastCGI 以提高系统并发量,加快PHP解释速度。。。至于动态网页静态化,数据缓存之类的优化方案也是可以有的,而且肯定会实现。

po主的想法是,如果由openstack在其中作为IaaS层向上提供服务,可以在物理服务器有限的前提下方便的搭建分布式判题系统,对外由nginx作为web前端节点,并为后面的判题节点集群作负载均衡。由于云计算“按需分配”的特性,可以较好的实现系统资源弹性分配,避免单服务器节点在高负载下成为系统瓶颈,同时也增强了可扩展性。虽然我们的初始需求仅仅是满足教学日常用途,但是在一开始就设立架构上的大方向,考虑到以后的可扩展性的话,目光放远点还是很有必要的。

同时po主准备基于hustOJ的系统进行二次开发,添加一些个性化的模块,比如mediawiki用作管理OJ的技术记录与使用说明。看了该项目的源代码一段时间,觉得原作者真是牛逼闪闪啊。框架暂时没发现什么问题,后期管理员的优化也很不错,这不得不说是开源的一大好处。貌似我越来越喜欢open source了~(才不是什么拿来主义呢

2012年8月12日星期日

SJTU-NIC实习总结

机缘巧合之下,有幸来到SJTU-NIC实习。转眼已经过去一个多月了。回顾在SJTU这一个月,感触良多啊~

七月份来到交大,一整天的火车啊。来之前并不算顺利,家里人意见蛮大的,主要是担心安全问题,而且也不想我整个暑假都在上海。说起来,也算是我一意孤行吧。并不是我不想回家,只是在家里的学习效率真的不能让我满意。琐琐碎碎的事太多了,囧。一直都认为在学校,在图书馆,在实验室的时候,效率是最高的。事实也证明,交大没有让我失望。

在Omnilab的日子,跟随 @WeiJianwen 老师,与 @WangHaiyang @LiuYukun 共事,学到了很多。应该说,我还是蛮幸运的。同来的另外一个实习生被分到openstack组,负责dashboard的前端开发了。本人是真的对前端无爱啊....而我则被分到BigDate组,负责Ganglia分布式监控平台的部署配置。应该说,这和我预想中的工作差不多,也是我目前最愿意做的。主要是纯linux的工作环境让我期盼已久啊!大体上,这是偏向运维一类的工作。大部分时间是工作在SSH的remote host上(终端什么的总是很有爱的~)。

整个实验室架构大概是:openstack组负责提供IaaS层的VM,然后在上面部署Hadoop与HBase环境,由rsyslog daemon负责从远端数据源接受海量数据转发到Hadoop经过分析写入HBase。Hadoop Cluster状态则有Ganglia负责监控,包括CPU,disk-IO,network-IO,memory等。

应该说,最大的收获是对linux操作熟练程度有了很大提升。之前一直苦于没有一个合适的环境来实践书上的各种理论,对服务器的各种daemon理解都不深。在实验室的时候,案上必备一本鸟哥,随用随查,感觉甚好。另外,实验室采用wiki的资源经验分享方式,结合git项目管理,让我受益匪浅啊。只是可惜直到现在对git的使用还是处于初级阶段,汗一个。。。还有就是对云计算和海量数据处理的概念有了一定理解。目前实验室项目的研究水平在国内的高校甚至业界也算是领先的吧,接触到都是世界范围内的领先技术与概念,真心感受到云计算的发展前景相当大啊。而海量数据处理也是相当程度上依赖于云技术,目前这两个名词已经被炒得相当火了。。。

实习期间还好是住在交大里面,白天全身心投入到工作中,到晚上回到宿舍不用怎么折腾就可以睡了。交大的环境很好,黄昏的时候,还有闲情逸致漫步校园。周末或泡图书馆,或到外面逛下,时间过的真心充实。这才是我梦寐以求的校园生活啊!~~

上一张wiki的图以示纪念吧~半个月的成果~


2012年7月15日星期日

安装ubuntu前后的一系列启动&引导问题

来到纯linux系环境的实验室,原来的debian真心旧到用不了啊,与其upgrade一次,不如重新装过好了。
所以决定重装个ubuntu 12.04 LTS,没想到问题多多。。。就顺便记录下遇到的问题及解决办法吧。

首先,制作U盘的liveCD一直不成功,这个是半年前的旧问题了。。。
最后发现ubuntu中文论坛有个帖子解决了。。。以前怎么没发现?!Orz
http://forum.ubuntu.org.cn/viewtopic.php?f=77&t=355114&sid=c0086339a5480ea7bc31c7b18155facf

然后顺便装好ubuntu 12.04之后,reboot
竟然无法启动grub,出来的是grub rescue>    .....

好吧,直接用liveCD的U盘启动,然后终端:
sudo mount /dev/sda8 /mnt      //把linux根分区挂载到/mnt
sudo grub-install --root-directory=/mnt /dev/sda      //在根分区安装grub
sudo umount /mnt       //卸载分区
reboot
顺利出现grub菜单~
参考链接: http://os.51cto.com/art/201006/205349.htm

用了一天,想换回win7的时候发现,选到win7,只是闪了一下屏幕就回到grub。
一开始吓我一跳,别是弄坏了分区表吧?
进到ubuntu仔细看了下 /etc/grub/grub.cfg 发现没什么问题啊,应该不是grub2的问题,那就是说,MBR没有问题,是PBR的问题。也就是win loader异常了。
上网一阵狂搜,总算找到解决办法:
找一张win7系统盘,进去到安装界面,shift + F10 调出cmd,
bootrec /fixboot
重启

OK~win7娘回来了~
这次装ubuntu真是积累了好多经验。。。。。Orz

2012年6月6日星期三

host主机SSH登陆虚拟机配置

说来玩了linux 1年多还是第一次SSH登陆 = =汗
大概弄了半个晚上 + 半个早上
显示解决了互ping的问题,设好SSH,解决putty的中文乱码。。。
问题真是一个接一个啊 = =


先说说环境吧。
host:win7 ultra, 客户端用PuTTY登陆, Oracle Virtualbox
VM:GNU/Linux debian 6.0,openSSH


----------------------


物理机配置(host configuration):
virtualbox 设置-> 网络,启用网络连接1,选择NAT,网络连接2,选择host-only adapter
宿主机当前使用的网卡设置为 “允许共享” 给虚拟网卡

cmd下看看网络状态:
ipconfig /all
应该可以看到本机真实网卡信息和虚拟网卡信息,将host-only的IP记下(我这里是192.168.137.1)


虚拟机配置(VM configuration):
先看看网络情况
$/sbin/ifconfig -a
看到有eth0 和 eth1
由于我装debian的时候选的NAT和DHCP,所以eth0就是分配到的子网IP:10.0.2.5
eth1默认没有设置IP,负责和虚拟网卡通信

以下设置eth1

$sudo gedit /etc/network/interfaces
添加下面配置:
# 启动系统激活设备
# 网卡eth1设置为Static类型
auto eth1
iface eth1 inet static

# 指定IP地址、子网掩码、广播、网关
# IP和host-only虚拟网卡同一网段即可
# 网关地址为宿主机的虚拟网卡IP
address 192.168.137.2  
netmask 255.255.255.0
broadcast 192.168.137.255
gateway 192.168.137.1

保存之后

$sudo /etc/init.d/networking restart  //重启网络服务
$/sbin/ifconfig -a   //查看当前网络状况


看到eth1正常配置即可

然后VM和host互ping,ping通就说明可以进行SSH登录了

------------------------------optional
debian默认没有安装SSH服务端,so

$sudo apt-get install openssh-server
----------------------------------

2012年5月21日星期一

Gobang summary

电工实习两周,算是抽空把Java的大作业搞好了。感悟还是蛮多的,遂记录之。
原来看《thinking in Java》的时候是完全不懂GUI,不单如此,很多之前看过的知识由于没有应用到具体项目中,时间一长竟然忘了许多。以《thinking in Java》如此丰富高深的内容,涉及各种design pattern和 类机制,其实真正会用的真不多。。。现在觉得可以重新回头看看要点了。
老实说吧,刚开始的时候真是各种不适应。用惯了C的人,代码越简洁越好,但是面对Java这一坨坨的类。。。好吧,确实有点难以接受咯。如果不是有eclipse这种自动化程度这么高的IDE,而是用什么notepad ++,估计早就崩溃了 = =

敲代码过程中主要还是吃老本,Java的特性没用到多少,反倒是有点C++的OOP影子。但是基础方面我觉得两者差不多吧,都是OOP的话。

说回五子棋。其实核心的也就是AI算法。基本思路是用二维数组模拟棋盘状况,然后对每个可能下子的空位置进行评价,也就是在最有价值的位置下子。这个价值判定分两部分,对己方的有利程度和对敌方的有利程度。对一个位置的考虑是有主攻和主防两种方向。实现起来也不算难,就是根据相同的权值表对该位置进行两种角色的评价。但是这个算法其实还远远不够,顶多只能算考虑了一步半(比只考虑进攻的要好点)。考虑过A*寻路算法+启发式搜索,还有博弈树,但是无奈水准还不够啊,真要弄起来估计deadline之前完成不了,遂暂且作罢。但是这个思路我觉得还是不错的,就是实现起来可能会比较麻烦。
另外还有一点深有体会的就是各组件之间触发事件的相互响应。Java的事件机制感觉上比较混乱,而且功能不够齐全,有些还有自己实现。各部件之间基本上是通过父部件来进行通信。e.g. A component 的listener接受到触发信号,然后需要通过parent component来调用B component的函数。有时候直接用getparent方法还不行,要在构造的时候直接传入父部件的引用,这样貌似效果要好点。

类的设计也是很讲究技巧的。怎样才能体现程序的高内聚,低耦合呢,这里貌似有点类似递归的思想。把大任务分成很多的小任务,由对应的对象完成。也就是说,作为某一类对象,其自身拥有的特殊属性和操作应该封装起来。这个就好像DIY,父部件把任务分配给子部件,至于怎么完成就是子部件的事了,父部件关心的只是任务完成的结果。如果是大量重复的子部件,更应该仔细考虑这个问题,尽量提高代码复用性,同时注意节约内存空间。这些都体现在代码的细节上。

前期的话,基本上是变开发边重构的。因为本身就不熟悉Java,同时会参考另外的样例程序。通过比较代码,了解原作者的思路,同时思想为什么要这样写,有什么好处,是否有更好的实现方法。经过不断的对比debug,算是搞出一个相对精简的AI算法。效果上来说还过得去吧。还有就是蛋疼的UI布局管理器,这里就不多说。各种触发事件之间的协调变化也是要慢慢理清思路才好下手,反正都是细节问题。

要说开发这个程序,主要目的还是熟悉基本的UI设计与操作,事件机制和OOP思想。现在看来,预期目标算是基本达到了,良好的核心算法是需要扎实的算法基本功和建模能力的,这个在不断加强中。
Anyway,熟悉软件开发流程算是暂告一段落。貌似各种书和资料(PPT,pdf)什么的已经积压的很多了,还有得忙呢。期待暑假的锻炼~


源码已托管于Google Code:
code.google.com/p/gobang-scut-csne/
为开源社区贡献的第一份代码 T_T

2012年4月23日星期一

关于缓冲区溢出攻击的一次小测试

我们写C/C++程序的时候,用scanf,gets,strcpy什么的,编译总会有warning,这个函数是不安全的云云。到现在才明白这个所谓的不安全是怎么回事,这个关于C的历史遗留问题真的有够严重的。。。
不安全的代码,产生的bug就不是bug那么简单了,而是exploit。这个buffer overflow attack (缓冲区溢出攻击)在安全界的知名度是不言而喻的,基本上属于最经典的漏洞之一。各种利用工具和shellcode何其多哉!

抱着亲身了解下缓冲区溢出攻击的过程,顺便体验下linux下强大的gdb的心态,就拿gets()写了个小程序练下手。

//attack.c
#include<stdio.h>
int main()
{
char s[8];
gets(s);
printf(s);
return 0;
}


生成的attack可执行文件用objdump反汇编:

080483f4 <main>:
 80483f4: 55                    push   %ebp
 80483f5: 89 e5                 mov    %esp,%ebp
 80483f7: 83 e4 f0              and    $0xfffffff0,%esp
 80483fa: 83 ec 20              sub    $0x20,%esp
 80483fd: 8d 44 24 18           lea    0x18(%esp),%eax
 8048401: 89 04 24              mov    %eax,(%esp)
 8048404: e8 fb fe ff ff        call   8048304 <gets@plt>
 8048409: 8d 44 24 18           lea    0x18(%esp),%eax
 804840d: 89 04 24              mov    %eax,(%esp)
 8048410: e8 0f ff ff ff        call   8048324 <printf@plt>
 8048415: b8 00 00 00 00        mov    $0x0,%eax
 804841a: c9                    leave  
 804841b: c3                    ret    
 804841c: 90                    nop
 804841d: 90                    nop
 804841e: 90                    nop
 804841f: 90                    nop



2012年4月15日星期日

某个C程序的汇编代码解释

偶然看到Allan Ruin大大的某post,原意大概是:子函数内的局部变量没有初始化的话,其值应该是任意的,函数返回后会释放内存。但是为什么第二次调用的时候i的值会是777呢?之前没遇到过类似问题,毕竟是现实中不会出现的情况。但通过汇编代码大概可以研究一下的吧?
这段时间刚好在看CSAPP的GAS语法汇编,恰好拿来练手的说。


C代码如下: 版权属于Allan Ruin :)
#include <stdio.h>
void foo(void)
{
int i;
printf("%d\n", i);
i = 777;
}
int main(void)
{
foo();
foo();
return 0;
}


ouput:
3
777


gcc -s lg_test.c

汇编代码如下



.file "lg_test.c"
.section .rodata             ;read only data segment
.LC0:
.string "%d\n"               ;printf() function's first parameter
.text
.globl foo
.type foo,@function


foo:
1  pushl %ebp              ;save old  %ebp
2  movl %esp, %ebp         ;new %ebp point to old %ebp (i.e. frame pointer)
3  subl $40, %esp          ;allocate 40 bytes on stack
4  movl $.LC0, %eax        ;move the string"%d\n" to %eax
5  movl -12(%ebp), %edx    ;use -12(%ebp) as i's value and save in %edx
6  movl %edx, 4(%esp)      ;set -12(%ebp) as the second parameter,push in stack
7  movl %eax, (%esp)       ;set  %eax( i.e. "%d\n" ) as the first parameter
8  call printf             ;call printf function(you can assume that 
                           ;it doesn't affect the existing stack frame)
9  movl $777, -12(%ebp)    ;NOTE:  -12 (%ebp) has changed
10 leave                   ;i.e.  movl %ebp, %esp ;    pop %ebp ;      
11 ret                     ;return    i.e.  pop %eip ;

2012年4月2日星期一

merge sort & inversion

inversion 逆序数
definition: 
对数组a[].存在一对(i,j)有i < j 且 a[i] > a[j] 即为一个逆序数对
e.g.
{1,3,5,2,4,6} 逆序数为3
 i.e. (3,2) (5,2) (5,4)
Stanford open course 的第一章就是关于分而治之思想(divide and conquer)的归并排序(mergesort)。上学期去隔壁班蹭算法课的时候听了下内排序,其实理解的不够深刻。现在再看一次mergesort,确实将分治思想变现的淋漓尽致。将大问题划分成小问题,递归调用函数去解决。
mergesort的大致思路,就是将一个数组平均分成左右两个子数组,分别调用排序函数本身,返回的是两个已排序的数组,然后再将其merge起来。时间复杂度是O(n·log n)

在mergesort算法的基础上稍为改变一下就可以实现求一组数的逆序数。
单纯用for循环模拟的话,复杂度是O( n^2 ) 即n个数中取2个的组合数。
接上,一个array被分成left array[i] & right array[j],其逆序数的组成可分为3部分:
1.left inversion     (i,j)均在left array中,即 i,j <= n/2   
2.right inversion     (i,j)均在right array中,即 i,j > n/2
3.split inversion      i在left,j在right,即 i <= n/2 ; j > n/2

计算左数组和右数组的逆序数,再加上split inversion即可得到整个数组的inversion number。问题关键成了解决split inversion。假设左右数组均已排好序(sorted B[],C[]),按mergesort的思路将两个数组合并的时候,每次从B[]取数放到合并数组(D[]),
计算B中剩余的元素个数(因为B中元素本应全部小于C中元素,若不是则必然存在逆序)。

课程练习原题是从100000的样本测试数据(txt)中计算逆序数个数,这个mergesort的模板感觉是有点怪(参数列表的问题)。开始用int count,结果溢出了。。。目测一下结果,貌似溢出的不多,改unsigned int,过了~

上代码:
#include<cstdio>
#include<fstream>
using namespace std;
int tmp[100001],a[100001];
void mergesort(int a[],int tmp[],int left,int right,unsigned int& count){   //待排序数组地址a,缓存数组tmp(节省时间,避免每次递归调用都开辟新数组)
int mid = (left + right) / 2;
if(left == right)return;     //递归分割的最小子项
mergesort(a,tmp,left,mid,count);      
mergesort(a,tmp,mid + 1,right,count);   //分别对左右数组递归调用mergesort(invoke mergesort() recursively)
for(int i = left;i <= right;i ++)tmp[i] = a[i];
int i = left;
int j = mid + 1;
for(int k = left;k <= right;k ++){    //merge two sorted array
if(i > mid)a[k] = tmp[j ++];      //judge the index of array out of size 
else if(j > right)a[k] = tmp[i ++];
else if(tmp[i] > tmp[j]){
a[k] = tmp[j ++];
count += mid + 1 - i;         //add remain number of left array(inversions with tmp[j])
}
else a[k] = tmp[i ++];
}
}
int main()
{
fstream file("d:\\IntegerArray.txt",ios::in);
if(!file)printf("exception!");
int i = 0;
unsigned int count = 0;
char s[10];
while(file >> s)
a[i ++] = atoi(s);
mergesort(a,tmp,0,99999,count);
printf("%u\n",count);
return 0;
}


2012年3月18日星期日

引用(别名)是什么?

由一个简单的JAVA问题引发了一场热情洋溢的群众喜闻乐见的讨论,同时扯到C++上。。。
先上代码:


public class test {
public static void main(String[] args){
int a = 4;
int b = a;
String s1 = "abc";
String s2 = s1;
String s3 = "def";
String s4 = "def";
System.out.println(a == b);     // 1
System.out.println(s1 == s2);   // 2
System.out.println(s3 == s4);   // 3
s3 = "abc";
System.out.println(s1 == s3);   // 4
s2 = "abcdef".substring(3,6);
System.out.print(s2 + "\t" + s4 + "\t");  
System.out.println(s2 == s4);   // 5
System.out.println(s2.equals(s4));  // 6
s3 = args[0];
System.out.print(s1 + "\t" + s3 + "\t");
System.out.println(s1 == s3);  // 7
System.out.println(s1.equals(s3));   // 8
  a--;
  System.out.println(a + " " + b);     // 9
}
}



output example:

上面的结果能说明一些问题:
注释3处表示,s3,s4指向同一个内存地址,也就是说,“abc”这个字符串在编译时经过优化存放在全局数据区,并不会产生两个相同的string。

注释4处表示,s3 = "abc"这句是将s3指向"abc"这个字符串对象,而并不是修改s3原先指向的"def"处的内容。这证实了书上说的“string对象是不可变的”。

注释5、6处证明了 == 比较的是两个引用所指向对象的物理地址,而不是对象的值。用equals()比较值的结果是true,用 == 比较内存地址的结果是false,因为s2是从另一个字符串的返回的string子串,虽然内容和"abc"一样,但物理地址是不同的。
注释7、8处同理。从args传入参数。

(后来加上去的)注释9处,是验证b是否为a的引用。结果显示为 "3 4",说明a,b是独立的。同样的句式,用在string上和用在int上效果完全不一样,何解?因为int是基本类型,而String是一个类。
确实,很多时候我们潜意识里以为String和int都是基本类型,其实不然。

说到底,s2是s1的一个浅copy,不是深copy。
这里引用一段师兄的话
关于别名,其实就是编译器在编译时帮某个变相定义的另外一个名字而已,你就把引用当作在编译时编译器帮你默认写了个typedef。它其实不会产生额外内存开销(至少在C/C++里面是这样),只是编译的trick,按照我的理解,它应该仅存在于编译后产生的符号表里面,所以本身也没有地址。
 也就是说,一般情况下,引用(别名)本身是不占空间的,这和C++的定义是一致的。符号表是关键....

附一个stackoverflow上关于引用的解释: http://stackoverflow.com/questions/1179937/how-does-a-c-reference-look-memory-wise

再次清楚的意识到自己的基础知识该有多差。。。细节决定成败啊!
还是要潜心钻研学术,低调求发展。。。
“勿在浮沙筑高台”


2012年3月3日星期六

JAVA中的多态机制与类初始化

将一个方法调用同一个方法主体关联起来,称为绑定。
在运行时根据对象的类型进行绑定称为后期绑定(动态绑定),这是实现多态的前提。

由多态引申出一个对象初始化具体步骤的问题,自己想了一个模型:
class Shape {
  int a;
  double b;
  Shape(){f1();}
  void f1(){println("shape.f1");}
  private void f2(){println("shape.f2");}
}

public class Circle extends Shape {
  void f1(){println("circle.f1");}   //override
  void f2(){println("circle.f2");}
  public static void main(String[] args){
    Shape s = new Circle();
    s.f1();
    s.f2();
  }
}


output:
circle.f1
circle.f1
shape.f2


将派生类对象向上转型为基类,根据实际对象调用重载的方法,是多态的特性。开始我很疑惑,怎么可以在基类的构造器调用派生类的重载函数?在内存中,对象的具体实现是怎样的呢?就是以怎样的形式存在于内存空间中的呢?这就要涉及对象的初始化步骤:

1.访问public类的main()函数 【static 方法】
2.加载并找出该类的编译代码(.class文件中)
3.加载过程中若存在基类(由extends可知)则先加载基类编译代码
4.根基类的static初始化,接着是导出类的static块
5.创建对象:所有类成员变量初始化(或置0);从根基类开始按顺序调用构造函数
6.实例变量按顺序初始化


关于成员函数在类中的表示方式,和师兄讨论过之后恍如大悟。他是站在C++的角度解释这个问题,但是我觉得很有道理。
首先,要清楚,函数并无“实例”的概念。程序被载入后,函数是在内存中的代码区而不是在数据区。函数不会被实例化,类在初始化生成this指针的时候,并不将任何函数装入内存,装入内存的是函数入口的偏移指针,这个入口指针可以一早确定并赋值给代表virtual function的类成员变量。
也就是说,s对象初始化的时候,f1(),f2()作为类成员变量(实际上是“指针变量”),其实存储的是对应函数的入口地址,而非函数代码本身。override之后,f1()接口处存放的就是派生类的函数入口,而非基类的函数入口。f2()由于定义为final,则其内容无法被修改,故依然指向基类的函数入口。

从上面的例子来看,circle从shape类继承来的是一个int,一个double,一个"指针变量",和一个"常指针";对象初始化的时候覆盖了f1()指针变量地址,然后创建了另一个指针变量f2()(扩展接口),所以就可以通过基类的构造器调用派生类的函数了(步骤5)。

2012年2月21日星期二

JAVA中访问权限控制的问题

记得在C++中,private部分主要是数据成员,public部分主要是函数成员,也就是类接口。如果没有特别声明public或者protect,private,也不会强调包访问权限这个概念。《thinking in JAVA》中的一些例子总是让人有眼前一亮的感觉。
现在想想,当时学的C++真是皮毛都算不上。囧rz

正题:
通过将构造函数声明为private,控制类外程序无法直接创建新类,而需要通过类接口来创建。书上说是可以通过特定函数(类接口)来实现特殊功能,比如控制数量。细心一想确实如此,要统计生成的对象数目,用一个计数器就可以了,但构造函数本身无法控制不生成对象,因为调用构造函数本身的同时就生成了一个对象。但是用函数成员的话只需要一个if就可以解决。

里面还提到一个设计模式的例子。private构造函数,类接口本身只提供一个类内生成对象的引用。称之为singleton(单例)。这种想法之前还真没接触过。。

example code:


/* Following the form of the example Lunch.java, create a class called
* ConnectionManager that manages a fixed array of Connection objects. The client
* programmer must not be able to explicitly create Connection objects, but can
* only get them via a static method in ConnectionManager. When ConnectionManager
* runs out of objects, it returns a null reference. Test the classes in main(). */


class connection{
private static int count = 0;
private connection(){System.out.println("connection created!");}
public static connection makecon(){
count ++;
return new connection();
}
public int howmany(){return count;}

}


public class CM{
private int num = 3;
connection[] con = new connection[3];
CM(){
for(connection x : con){
x = connection.makecon();
System.out.println(x.howmany());
}
}
public connection getcon(){
if(num != 0){
System.out.println("get " + (num - 1) + "th connection");
return con[--num];
}
else {
System.out.println("no connection left!");
return null;
}
}

public static void main(String[] args)
{
CM cm1 = new CM();
connection c1 = cm1.getcon();
connection c2 = cm1.getcon();
connection c3 = cm1.getcon();
connection c4 = cm1.getcon();
}
}


原书答案中,生成固定数组的foreach语句是用一个大括号包起来,而我将其放在构造函数中。之前还没出现过
{
 for(...){}
}
这种用法,开始不明白,后来想起,类中只能存在数据成员和函数成员,不能出现这种函数语句的吧?。。。C++中反正我是没见过 = =

2012年2月19日星期日

HDOJ 2035 人见人爱A ^ B

突然想起还有一份杭电ACM的PPT没看,翻出来看了下~发觉蛮有意思的,就是内容少了点。。。基本上是提纲,该总结的都自己来吧。╮( ̄▽ ̄")╭

题目很简单,但也蛮经典的算术题。
输入两个数A,B。输出A ^ B的最右三位数。

核心思路:求 A的B次方 模1000,只需要求 A%1000 的 B次方。B通过降幂二分加速。
比如:(1123)^ 6 = (1000 + 123) ^ 6
多项式展开后,决定结果最后三位的是123 ^ 6
然后123 ^ 6 = (123 ^ 3) ^ 2

version 1.0  纯暴力

#include<cstdio>
int main()
{
int a,b,sum;
while(scanf("%d%d",&a,&b) && a){
sum = a;
for(int i = 1;i < b;i ++){
sum *= a;
if(sum >= 1000)sum %= 1000;
}
printf("%d\n",sum);
}
return 0;
}



优化之后,通过二分加速,int范围内的大数都可以接受。
version 1.1 递归

2012年2月18日星期六

关于import & package的应用与疑问

在《thinking in JAVA》第六章 访问控制权限 中,说到了package的用法。对于解决像System.out.print这种冗长的输出格式,也不失为一种好的解决办法。但是建立自己的类库,代码的可移植性也就要差点了。当然这个package也是鼓捣了好一阵才弄明白怎么用,囧

首先涉及到classpath的设置。安装JDK的时候会有设置classpath这一步。比如,classpath中存在“%java_home%\lib;"

import access.test.*
就会在classpath下寻找access]test 这个目录中的java源文件和class文件(也就是%java_home%\lib\access\test\ 这个目录)

个人感觉,import 和C++中的 using namespace 比较类似,反而不是属于include那一类。简单的说就是命名空间的划分引用。

也就是说,一般在类库中的文件,源代码开头(除注释)都是package 语句,用以将该java文件和class文件划分在指定的命名空间中。调用的时候就通过import语句导出。也就是说类库中java源文件中的package路径就是文件本身的路径?

其实一开始让我疑惑的是,一般我们会
import java.util.*
但是在我的classpath
.;%JAVA_HOME%\lib;%JAVA_HOME%\lib\dt.jar;%JAVA_HOME%\lib\tools.jar
搜寻路径中,没有java这个目录,而java\util\ 这个目录实际上存在于%JAVA_HOME%\src.zip 这个文件中打包保存。这个怎么解释呢?应该是JAVA路径支持压缩包

比如:
CLASSPATH:也指定一个路径列表,是用于搜索 Java 编译或者运行时需要用到的类。在 CLASSPATH 列表中除了可以包含路径外,还可以包含 .jar 文件。Java 查找类时会把这个 .jar 文件当作一个目录来进行查找。通常,我们需要把 JDK 安装路径下的 jre/lib/rt.jar (Linux: jre/lib/rt.jar) 包含在 CLASSPATH 中。

2012年2月10日星期五

POJ 2247 humble number (DP)


这题第一感觉就是筛数法,可能是受前几天刚做的那题影响了。。。其实思路也没有太大问题,小数据的话还是可以的(虽然没优化过 = =)结果没想到题目的数据太大,堆溢出了 = =!所以就只好换一种思路吧。。。。
这题和ugly number 那题想法是可以完全一样的,还算蛮清晰,就是输出那里比较变态,估计坑了不少人。。。
网上看到有链表的做法,感觉上比这个要繁琐了,其实就是经典动规题。
核心思路就是用2,3,5,7和humble list中的数相乘,得出的数依然在list之内。
假设humble number集合开始只有{1}
2,3,5,7分别从集合中由小到大取数相乘后,
即2 * 1,3 * 1,5 * 1,7 * 1,min = 2,入队列{1,2}。
然后比较2 * 2,3 * 1,5 * 1,7 * 1,min = 3,入队列{1,2,3}。
.....


#include<cstdio>
int humble[6000];
int main(){
int t2,t3,t5,t7,p2,p3,p5,p7,i,min;
p2 = p3 = p5 = p7 = 1;
humble[1] = 1;
for(i = 1;i < 5843;i ++){
t2 = humble[p2] * 2;
t3 = humble[p3] * 3;
t5 = humble[p5] * 5;
t7 = humble[p7] * 7;
min = t2 < t3 ? t2 : t3;
min = min < t5 ? min : t5;
min = min < t7 ? min : t7;
humble[i+1] = min;
if(min == t2)p2 ++;
if(min == t3)p3 ++;
if(min == t5)p5 ++;
if(min == t7)p7 ++;
}
while(scanf("%d",&i) && i){
if(i % 10 == 1){
if(i % 100 == 11)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %dst humble number is %d.\n",i,humble[i]);
continue;
}
if(i % 10 == 2){
if(i % 100 == 12)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %dnd humble number is %d.\n",i,humble[i]);
continue;
}
if(i % 10 == 3){
if(i % 100 == 13)printf("The %dth humble number is %d.\n",i,humble[i]);
else printf("The %drd humble number is %d.\n",i,humble[i]);
continue;
}
else printf("The %dth humble number is %d.\n",i,humble[i]);
}
return 0;
}



2012年2月4日星期六

POJ 2739 Sum of Consecutive Prime Numbers

打表,大水,RE 3次WA 1次。。。我原来堕落到这么水的程度了。。。囧~
虽然说在discuss里看到有10001的数据,但终究是数组开小了,而且循环条件没处理好。
开始想这么打表会不会太耗时效率太低?。。。结果0ms瞎了我的眼 = =
想个筛数法还回忆了好一阵,我勒个去!


#include<cstdio>
const int MAX = 10050;
int number[10050] = {1,1,0};
int prime_list[2000];
int ans[MAX];
int main()
{
int i,j,k,sum = 0;
for(i = 2;i < 105;i ++)
if(number[i] == 0)
for(j = i * i;j < 10030;j += i)number[j] = 1;
for(i = 2,k = 0;i < 10030;i ++)
if(number[i] == 0){prime_list[k] = i;k ++;}      //prime number list
for(i = 0;prime_list[i] < 10030 && prime_list[i] > 0;i ++){     //here forget the rest 0 are also below 10030 = =
for(j = i;sum < 10030;j ++){
ans[sum] ++;
sum += prime_list[j];
}
sum = 0;
}
while(scanf("%d",&i) && i)
printf("%d\n",ans[i]);
return 0;
}

2012年1月26日星期四

assembly language 实验九中的问题

在屏幕中间分别显示三种颜色的字符串“welcome to MASM”
80 * 25的彩色字符显示缓冲区

代码:


data segment
db 'welcome to MASM!'
db 02h,01h,04h
data ends


stack segment
dw 8 dup(0)
stack ends


code segment
    assume cs:code,ds:data,ss:stack
start:
mov ax,data
mov ds,ax
mov ax,stack
mov ss,ax
mov sp,10h
mov bx,[11*160]
mov di,0
mov ax,0b800h
    
mov cx,3    ;outer loop
   s1: push cx
push ax
push di
mov es,ax
mov si,0
mov di,0

mov cx,16
   s2: mov al,ds:[di]
mov es:[bx+si],al
inc di
add si,2
loop s2      ;set the even byte in display memory

mov si,1     ;odd byte
pop di       ;set color
mov al,ds:[16+di]    ;load color
mov cx,16
   s3: mov es:[bx+si],al
add si,2
loop s3

;ready for next turn
inc di        ;next color style
pop ax
add ax,0ah
;add bx,160    ;next row
pop cx
loop s1

mov ah,4ch
int 21h
code ends
end start




这个是显示正常的,通过修改ax来改段地址(绿色字体),已达到指向下一行的目的。但是,我原先的想法是通过改变bx的值来指向下一行(红色字体),不知何故没有显示正常。。。囧
但是理论上应该是一样的啊??bx自增160到下一行的行首,和ax自增16效果应该是一样的啊。。。这里面有什么玄机?debug了好久也没找出来,菜了。。。。囧


2012年1月24日星期二

POJ 1750 Dictionary 模拟水题

这题目最后说的blank line number着实让人摸不着头脑,也就不管了。。。算法也没什么太多可以说的,就是做完之后发现这runtime 700+ms... = =!
网上有影射的code,发觉效率真的高不少啊,其实就是将for输出的blank用影射实现了,确实节省一定的时间。。。细节问题呢~总是想不到这种取巧的方法,是coding太少,还没有这意识吧...囧



#include<cstdio>
const int N = 100001,M = 11;
char list[N][M];


int main()
{
int i = 0,j = 0,total = 0;
while(scanf("%s",list[total]) != EOF)
total ++;
int blank = 0,substr = 0;
printf("%s\n",list[0]);
for(i = 1;i < total;i ++){
j = substr = 0;
while(list[i][j] != '\0'){      //control the space number whitout "0",TLE for this T_T
if(list[i][j] != list [i - 1][j])break;
else substr ++;
j ++;
}
if(substr > blank)blank ++;      //main algorithm
else blank = substr;
for(int k = 0;k < blank;k ++)
printf(" ");
printf("%s\n",list[i]);
}
return 0;
}