Xavier's Blog

Chrome Plugin: 网页浏览时间统计

| Comments

前几天刚经过实习闹剧,回到学校,导师暂时还没布置什么任务,比较无聊,于是突发奇想,准备搞个chrome插件玩玩。做个什么功能的插件呢?平时发现许多人(当然也包括我)总会把大把的时间花在一些网站上,做事情的效率变低下不说,还白白浪费了时间、浪费了生命,这样多不好啊!那就做个统计某些网页浏览时间的插件吧。用了三天的晚上空余时间,做了一个雏形。

在option页面中,可以添加你想要监控的网站URL,如下图:

image

然后,你就可以向平时一样正常的浏览网页了。当想要查看浏览时间统计的时候,只需点击插件按钮即可。效果如下图:

image

统计信息通过饼图和柱状图展示,显示的是自使用该插件以来,你所花(或者称浪费)在你已监控网站上的时间,以及这些时间占你一生时间(假设你能活100年吧)的比例。

Chrome插件开发起来倒还容易,就是javascript+HTML+CSS,熟悉web开发尤其是前端开发的人应该可以很快上手。我是好久没搞web前端开发了,开发时还花了不少时间复习。开发过程中,还用到了jQueryHighcharts,节省了不少开发时间啊。

其实,我觉得这个插件并没什么技术含量。那为啥要做呢?原因有以下几点:

  • 我感觉这个点子不错

  • 培养自己的执行力

  • 作为“学术”之外的调剂 反正,别让自己闲下来,至少别让自己把大把时间花在没有太多意义的事情上!有些事情,不管你喜欢不喜欢,都是要做的。不过,当你能有自己可以控制的时间,还是多做些更有意义的事情吧!(哎呀,貌似扯远了,最近比较火大 :))

实习“闹剧”

| Comments

这学期开始的时候,导师让我们写论文发表,自己试着写了一部分,但感觉很垃圾。三月底的时候,听说一家我十分想去的公司在招实习生,于是投了简历,经过电话面试,自己得到了实习的机会!好了,下一关,征求导师的同意。写邮件给导师,第二天导师回复了我。从他回复我的邮件可以看出,他是不太愿意我去,但没有明确说不能去,只是说“随便我”。我自认为搞定了,收拾了下行李,过了两天就出发了。

虽然实习的公司在外地,也因为算是我第一次出远门,各种情况都需要适应,各种问题需要自己独立解决,但自打进了公司开始实习,我就感觉自己来对地方了,这就是我向往的地方!公司的氛围十分轻松,也十分单纯,重视技术,尊重有技术的工程师,公司里面的许多技术框架也都是自己研发的。在那里交流十分平等,没什么等级的概念,组织结构相对扁平化。不管是刚进来的实习生,还是某个团队的leader,大家都可以当面或者通过IM、邮件对某一问题进行讨论。看到几个看上去30多岁的员工对于某行代码进行讨论,那是常有的事。对于培训,公司做的也十分出色。公司会不定期通过邮件告知课程信息,你可以根据自己的兴趣或者所在团队的业务,选择是否参加。我们团队每隔1~2周也会让其中的一个成员给我们分享一下某个方面的技术问题。公司内网也有各种文档资源,你可以自由搜索、查阅。另外,公司的工作时间也十分宽松。不用打卡,一般早上9点到就可以了,晚上吃过晚饭,待一会儿就可以走了。(但我们这些新人一般会选择晚上10点钟以后走,没有人强迫我们,只是愿意待在公司再学点东西)

经过一周左右的适应,打算正式开工了!不料,好景不长,导师打电话给我,把我训了一顿,说我未经同意擅自出去实习,还说如果不能按期毕业的话后果自负。我说,“当时您不是随便我吗?”他说,“你应该能听得出我这句话背后的意思。”我跟导师说尽量缩短实习时间,尽快回学校。但他的态度很强硬,甚至说可以去实习,不过每周都要给他汇报学术进展,两周不汇报的话就采取相应行动,而且还有在规定日期前发表一篇论文。身在屋檐下,哪能不低头啊,想想还是毕业要紧,只好跟公司说明了情况。公司这边没有为难我,很顺利的办理了离职,然后收拾收拾行李就回去了,一场闹剧就这样(暂时)结束了。

虽然有可能就此跟导师的关系不会那么融洽了,虽然这次去实习还没拿到offer,但我一点没有因为当初选择去实习的决定而有丝毫的后悔,甚至感觉挺好玩的,因为至少我去了自己向往的地方,哪怕只待了短短十几天的时间而已。如果在生命中,发现了你向往的东西,是应该去追随的,哪怕可能因此付出巨大的代价。这就好像如果遇到一个你喜欢的女孩,就算之后自己会被拒绝,就算会把自己搞得很痛苦,那也还是要追求的啊!否则人生就没什么意思了。

事情虽然暂时告一段落了,但是这场“闹剧”还是给了我一些思考和教训的:

  • 沟通很重要
    如果当初跟导师好好沟通,了解了他真正的意思,或者他明确告诉我不可以去,那我也就不会去了,也就不会有这档子事了。另外,还要多想想对方的难处。其实,导师对我们还是不错的,和我们的关系其实很近,这次去实习做得的确有些不太“地道”。

  • 学生是弱势群体(尤其是研究生)
    除了得到应有的学分以及完成毕业设计论文,导师对你的评价也是你是否可以毕业的重要因素。如果跟导师关系没处好,到时候导师给你个延期毕业,自己的很多事情就都会被耽误。即使导师整天让你研究你认为没什么用的科研,即使导师整天让你写XXX策划书,你所能做的只能是忍着,并且尽量把这些事情做好。

  • 找工作和搞科研是对立的
    这其实是我们教研室的一个同学说的,对于那些以后不会读博或者不会去研究所的同学来说,事情就是这样的,因为你研究生阶段搞的所谓“研究”和你以后的工作是没什么关系的(除了“研究”给你带来的文凭和一份更好的工作之间的关系),而时间大家都是差不多的。所以,怎样在两者间把握一个平衡,就看个人的本事了。

回学校大概还要跟导师再聊一两次,希望我们之间不要产生无法弥补的裂痕,理解万岁啊!

Decorator模式初探

| Comments

Decorator模式,又称装饰模式。在实际编程中,如果希望能在原有基础上动态的添加新的功能或者扩展已有功能,那么Decorator模式提供了一种很好的解决方案。Decorator模式如下图所示:

image

具体的实现类ConcreteComponent和装饰类Decorator均实现了Component接口,装饰类含有一个Component类作为其成员。这样,当需要在ConcreteComponent基础上添加新的功能时,只需扩展Decorator形成具有某一特定功能的Decorator即可。由于不同的Decorator都是遵循Component接口,当需要扩展新功能时,在原有的Decorator上再套一层Decorator就可以啦。

来用一个简单的例子解释一下吧。比如现在有个手机类SimplePhone,实现了Phone接口:

public interface Phone {
    String getDescription();
    int getCost();
}

package org.quxiao.phone;

public class SimplePhone implements Phone {

    @Override
    public String getDescription() {
        return "simple phone";
    }

    @Override
    public int getCost() {
        return 100;
    }

}

为了能动态增加功能,做一个抽象的Decorator:

public abstract class AbstractPhoneDecorator implements Phone {
    protected Phone phone;

    public AbstractPhoneDecorator(Phone phone)
    {
        this.phone = phone;
    }
}

现在需要给手机添加GPS模块,扩展抽象的Decorator:

public class GPSPhoneDecorator extends AbstractPhoneDecorator {

    public GPSPhoneDecorator(Phone phone) {
        super(phone);
    }

    @Override
    public String getDescription() {
        // TODO Auto-generated method stub
        return phone.getDescription() + " and GPS";
    }

    @Override
    public int getCost() {
        // TODO Auto-generated method stub
        return phone.getCost() + 100;
    }

}

同理,再添加蓝牙的模块:

public class BlueToothPhoneDecorator extends AbstractPhoneDecorator {

    public BlueToothPhoneDecorator(Phone phone) {
        super(phone);
    }

    @Override
    public String getDescription() {
        return phone.getDescription() + " and blue tooth";
    }

    @Override
    public int getCost() {
        return phone.getCost() + 200;
    }

}

这样,我们就可以给SimplePhone类动态的添加模块了

public class Main {

    public static void main(String[] args) {
        Phone simplePhone = new SimplePhone();
        Phone GPSPhone = new GPSPhoneDecorator(simplePhone);
        Phone myPhone = new GPSPhoneDecorator(new BlueToothPhoneDecorator(new SimplePhone()));

        System.out.println("simplePhone description : " + simplePhone.getDescription());
        System.out.println("simplePhone cost : " + simplePhone.getCost());
        System.out.println("GPSPhone description : " + GPSPhone.getDescription());
        System.out.println("GPSPhone cost : " + GPSPhone.getCost());
        System.out.println("myPhone description : " + myPhone.getDescription());
        System.out.println("myPhone cost : " + myPhone.getCost());
    }
}

simplePhone description : simple phone simplePhone cost : 100 GPSPhone description : simple phone and GPS GPSPhone cost : 200 myPhone description : simple phone and blue tooth and GPS myPhone cost : 400

其实,Java I/O库中就是用了Decorator模式。

在基于Stream的输入中,所有数据都抽象成InputStream类,其子类FilterInputStream就相当于InputStream的装饰类。BufferedInputStream, CheckedInputStream, CipherInputStream, DataInputStream, DeflaterInputStream, DigestInputStream,InflaterInputStream, LineNumberInputStream, ProgressMonitorInputStream, PushbackInputStream都扩展自FilterInputStream,每个都对应于一个特定的功能。比如哦BufferedInputStream具有缓存功能,DataInputStream可将读出基本(primitive)类型的数据。因此,当我们使用Java I/O库进行输入输出时,总会生成一堆的类,就像这样:

DataInputStream dis = new DataInputStream( new BufferedInputStream( new FileInputStream(FILE_LOC)));

之前一直不明白为什么Java的输入输出会这么麻烦,原来是因为用到了Decorator模式。现在明白了其中的原理,也觉得不那么复杂了。

CGLib动态代理模式

| Comments

CGLib,即code generation library,原理是通过动态生成类以实现代理的功能。上一篇文章中,我们提到了AOP(面向切片编程)以及AOP的一种实现方法——Java Dynamic Proxy。需要注意的是,Java动态代理是面向接口的,即被代理的类必须实现某个接口,代理类以该接口的形式出现,而使用CGLib,则没有这方面的限制,任意一个类都是可以的。

简单的说,使用CGLib代理某个类,需要在Enhancer对象中设置好基类(也就是被代理类),以及一系列回调函数Callback。Callback是一个接口,CGLib提供了6个它的子接口:

Callback子接口

用途(有待确认)

Dispatcher

分发给其他Callback

FixedValue

仅仅返回被代理类方法的返回值,对于限定某一些特定方法很有用(因为返回值必须和被代理类方法的返回值类型相匹配)

InvocationHandler

主要用于Proxy(替代Java动态代理),也可以用户Enhancer

LazyLoader

与Dispatcher类似,当代理类的第一个lazily-load方法调用时才会被调用

MethodInterceptor

普通用途的回调方法,在处理逻辑(advice)前后进行处理

NoOp

直接调用基类(被代理类)的方法调用

好,那我们来假设一个场景吧。

有这样一个类RealObject,它可以查询、保存资源,比如是这样:

public class RealObject {
    public void queryA ()
    {
        System.out.println("queryA");
    }
    public void queryB ()
    {
        System.out.println("queryB");
    }
    public void saveA ()
    {
        System.out.println("saveA");
    }
    public void saveB ()
    {
        System.out.println("saveB");
    }
}

我们有这样的需求:保存资源时,需要加入事务功能。那么可以实现自己的MethodInterceptor,实现其中的intercept方法:

public class MyMethodInterceptor implements MethodInterceptor {

    @Override
    public Object intercept(Object obj, Method method, Object[] args,
            MethodProxy proxy) throws Throwable {
        // TODO Auto-generated method stub
        System.out.println(obj.getClass());
        //模拟事务功能
        if ( method.getName().startsWith("save") )
        {
            System.out.println("begin transaction");
        }
        Object result = proxy.invokeSuper(obj, args);
        if ( method.getName().startsWith("save") )
        {
            System.out.println("end transaction");
        }
        System.out.println("************************\n");
        return result;
    }
}

再来写主入口:

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Enhancer enhancer = new Enhancer();
        //将需要代理的类作为基类
        enhancer.setSuperclass(RealObject.class);
        //设置回调功能,这里使用的是拦截器,
        //当被代理类调用方法时,会执行拦截器的intercept方法
        enhancer.setCallback(new MyMethodInterceptor());
        RealObject realObj = (RealObject) enhancer.create();
        consume(realObj);
    }

    private static void consume(RealObject realObj)
    {
        realObj.queryA();
        realObj.queryB();
        realObj.saveA();
        realObj.saveB();
    }
}

运行一下,看看效果吧!

class org.quxiao.RealObject$$EnhancerByCGLIB$$91eddf0b
queryA
************************

class org.quxiao.RealObject$$EnhancerByCGLIB$$91eddf0b
queryB
************************

class org.quxiao.RealObject$$EnhancerByCGLIB$$91eddf0b
begin transaction
saveA
end transaction
************************

class org.quxiao.RealObject$$EnhancerByCGLIB$$91eddf0b
begin transaction
saveB
end transaction
************************

我们可以看到,CGLib动态生成了一个叫RealObject$$EnhancerByCGLIB$$91eddf0b的类,这个类就是RealObject的代理类。以后有时间来反编译一下,研究研究CGLib动态生成类的原理。

AOP以及动态代理模式

| Comments

AOP,即面向方面的编程(面向“切片”的编程应该更合适)。按我的理解,就是对业务逻辑中的某一阶段进行抽取,以达到逻辑模块之前低耦合的编程方法。举个例子,一个系统有许多资源,只有当用户登录系统之后才能访问。那么,验证用户登录就可以抽象成一个“切片”,插在了用户和系统资源之间,编写各个业务模块的人就不用去关心验证用户登录的工作了,验证登录的工作会进行统一配置。

Spring采用的是动态AOP,即通过动态代理模式,在目标对象调用方法前后进行相应处理。

Spring中的动态AOP是基于以下两种方式实现的:

  • Java Dynamic Proxy

  • CGLIB(code generation library)

Java Dynamic Proxy是面向接口的,而CGLIB是面向类的。两者的关系可以参考这张图: image

UserDAOImp是我们需要代理的类,Java动态代理类需要实现了UserDAOImp所实现的接口,(这也要求UserDAOImp必须实现某个接口),而CGLIB则是扩展了UserDAOImp类。

我们先来利用Java Dynamic Proxy实现代理功能。比如目前有一个类RealObject,它实现了接口Interface

Interface

public interface Interface {
    void funcA ();
    void funcB (String str);
    void saveXXX ();
}

RealObject

public class RealObject implements Interface {

    @Override
    public void funcA() {
        // TODO Auto-generated method stub
        System.out.println("funcA() in RealObject");
    }

    @Override
    public void funcB(String str) {
        // TODO Auto-generated method stub
        System.out.println("funcB() in RealObject : " + str);
    }

    @Override
    public void saveXXX() {
        // TODO Auto-generated method stub
        System.out.println("saveXXX() in RealObject");
    }
}

假设我们需要代理RealObject,在调用方法前后进行相应处理(输出信息),那么我们就需要一个实现了InvacationHandler接口的类,比如说是ProxyInvacationHandler

ProxyInvacationHandler

public class ProxyInvocationHandler implements InvocationHandler {

    private Object proxied;

    public ProxyInvocationHandler (Object proxied)
    {
        this.proxied = proxied;
    }

    @Override
    public Object invoke(Object proxy, Method method, Object[] args)
            throws Throwable {
        // TODO Auto-generated method stub
        Object result = null;

        System.out.print("n*******************n");
        System.out.println(proxy.getClass());   //invoke中第一个参数proxy意义何在?
        //模拟增加事务处理功能
        if ( method.getName().startsWith("save") )
        {
            System.out.println("transaction begins");
        }
        System.out.println("before " + method);
        //被代理的类调用实际的方法
        result = method.invoke(proxied, args);

        System.out.println("after " + method);
        if ( method.getName().startsWith("save") )
        {
            System.out.println("transaction ends");
        }
        System.out.print("*******************n");
        return result;
    }

}

其中的invoke方法就表示当被代理的类调用方法的前后,我们可以做的操作。甚至可以根据方法的不同,选择不同的操作。

最后,再通过Proxy的newProxyInstance静态方法动态生成代理类,因为代理类也是实现Interface接口的,所以操作代理类就像操作被代理类一样。

以下是运行结果:

funcA() in RealObject
funcB() in RealObject : 123
saveXXX() in RealObject

*******************
class $Proxy0
before public abstract void org.quxiao.Interface.funcA()
funcA() in RealObject
after public abstract void org.quxiao.Interface.funcA()
*******************

*******************
class $Proxy0
before public abstract void org.quxiao.Interface.funcB(java.lang.String)
funcB() in RealObject : 123
after public abstract void org.quxiao.Interface.funcB(java.lang.String)
*******************

*******************
class $Proxy0
transaction begins
before public abstract void org.quxiao.Interface.saveXXX()
saveXXX() in RealObject
after public abstract void org.quxiao.Interface.saveXXX()
transaction ends
*******************

Webx3样例工程login-webx3-tutorial学习笔记(一)

| Comments

在eclipse中部署好工程,然后再通过jetty启动server,工程的功能相当简单,就是将表单中的字符串提交后显示。通过运行和调试,初步了解了webx的运行流程。

首先看一下WEB-INF中的配置文件

image

web.xml是J2EE工程必须的配置文件,webx.xml以及common中的xml都是webx框架公用的配置文件,而app1文件夹以及webx-app1.xml就是名为”app1”的模块配置文件。

配置文件的详细设置我们稍后再谈,我们直接通过运行实例来讲解流程吧。

打开首页,内容是通过Velocity生成的:

index.vm

image

提交表单之后,即会运行com.alibaba.webx.tutorial.app1.module.action.SimpleAction中的doGreeting方法。那为什么会跳转到这边呢?其实都是写在配置文件中的。

来看看webx-app1.xml

image

它指定了app1模块所在的包。再看index.vm,“simple_action”表示查找SimpleAction类,“event_submit_do_greeting”表示执行SimlieAction类中的doGreeting方法。(name是否一定设为“action”我还不确定)

试着修改一下,我们将index.vm中的simple_action修改为my_action、event_submit_do_greeting改为event_submit_do_my_greeting,再在com.alibaba.webx.tutorial.app1.module.action包中加入MyAction类,并添加doMyGreeting方法。重启服务器,就可看到效果。输入111,结果就会变成my111。

image

好,基本知道了解流程了,但理解得还是很凌乱,尤其是配置文件加载以及动态定位到某个类的原理。

Java中Stream和Memory-mapped File的I/O性能对比

| Comments

建立和使用I/O系统,不管对于哪一种语言都是困难的(在Java中使用I/O库尤其困难)。在Java中,会有多种方式对于文件或者设备进行I/O操作。方法不同,性能很有差异。今天我们来对比一下通过Stream以及Memory-mapped File这两种方式的I/O性能对比。

Stream

“流”是I/O系统中通常使用的抽象概念,表示可以发出或者接受数据的点(source / sink)。“流”的概念也屏蔽掉了不同设备间的细节差异。
Input stream通常可以为:

  • 字节数组

  • String对象

  • 文件

  • 管道(pipe)

  • 其他流(将多个流组成一个流)

  • 网络设备等

Output stream通常可以为:

  • 字节数组

  • 文件

  • 管道

Memory-mapped File

对于那些很大的文件,将整个文件全部读进内存,将会极大地影响性能。通过Memory-mapped File可以只将文件的一部分读入内存,其他部分被换出(swap out),这样就能效率很高的读写大文件。

在Java的nio包中,用到了两种更接近于操作系统具体实现的数据结构:channel和buffer,memory-mapped file中就用到了channel。这种I/O方式,用户不需要跟数据源打交道,而只需把数据放到channel和buffer中,然后再调相应函数就可以了,通过这种“底层”的操作,已得到最大的I/O性能。(这种方式其实就跟C中的read和write一样了)

通过测试程序,我们可以看到两种方式性能的对比:

(注:表格中的文件大小N表示文件中含有N个char,而读写时间为ms)

读写方式 文件大小

10

100

210

220

221

222

Stream Write

1.874

1.974

1.828

161.258

368.252

656.428

Memory-mapped File Write

2.5

6.648

1.265

11.774

20.23

46.262

Stream Read

0.122

0.174

0.58

158.352

313.37

627.531

Memory-mapped File Read

0.428

0.463

0.382

10.797

19.381

39.749

image

可以看到,文件很小时,Memory-mapped方式是没有优势的,而当读写大文件时,优势就十分明显了。

关键代码如下:

public class IOPerComp {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] intSizes = {10, 100, 1<<10, 1<<20, 1<<21, 1<<22};
        for (int i = 0; i < intSizes.length; i ++)
        {
            INT_SIZE = intSizes[i];
            System.out.println("file size : " + INT_SIZE);
            for (Tester tester : tests)
            {
                tester.runTest();
            }
            System.gc();
            System.out.println("**********************");
        }
    }

    private static final String FILE_LOC = "D:/tmpFile.txt";
    private static int INT_SIZE = 1024 * 1024;
    private abstract static class Tester {
        private String name;
        public Tester () {}
        public Tester (String name)
        {
            this.name = name;
        }
        public void runTest ()
        {
            System.out.println("name : " + name);
            long start = System.nanoTime();
            try
            {
                test();
            }
            catch (IOException ioe)
            {
                ioe.printStackTrace();
            }
            start = System.nanoTime() - start;
            System.out.format("time : %.3fn", start/1.0e6);
        }
        public abstract void test() throws IOException;
    }

    private static Tester[] tests= {
        new Tester("Stream Write")
        {
            public void test() throws IOException
            {
                File f = new File (FILE_LOC);
                if ( f.exists() )
                    f.delete();
                DataOutputStream dos = new DataOutputStream(
                        new BufferedOutputStream(
                                new FileOutputStream(FILE_LOC)));
                for (int i = 0; i < INT_SIZE; i ++)
                    dos.writeInt(i);
                dos.close();
            }
        },
        new Tester("Mapped Write")
        {
            public void test() throws IOException
            {
                FileChannel fc = new RandomAccessFile(FILE_LOC, "rw").getChannel();
                IntBuffer ib = fc.map(FileChannel.MapMode.READ_WRITE, 0, fc.size()).asIntBuffer();
                for (int i = 0; i < INT_SIZE; i ++)
                    ib.put(i);
                fc.close();
            }
        },
        new Tester("Stream Read")
        {
            public void test() throws IOException
            {
                DataInputStream dis = new DataInputStream(
                        new BufferedInputStream(
                                new FileInputStream(FILE_LOC)));
                for (int i = 0; i < INT_SIZE; i ++)
                {
                    dis.readInt();
                }
                dis.close();
            }
        },
        new Tester("Mapped Read")
        {
            public void test() throws IOException
            {
                FileChannel fc = new FileInputStream(FILE_LOC).getChannel();
                IntBuffer ib = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size()).asIntBuffer();
                while ( ib.hasRemaining() )
                {
                    ib.get();
                }
                fc.close();
            }
        }
    };
}

Linux API实践:信号的发出、等待以及到达

| Comments

信号是Linux中的重要概念,其表示着某种事件的发生(或者结束)。

信号可以用三种状态:产生(generated)、等待(pending)以及到达(delivered)。这三种状态是按时间顺序出现的,我们尤其要注意pending状态,因为并不是信号一旦产生,就会立即到达目标进程,信号在产生和到达中间的状态就为等待。

进程可以对到达的信号进行阻止(block),如果被阻止的信号到达进程,该信号的状态就会一直保持等待,直到

  • 进程解除对该信号的阻止,或者
  • 进程忽略(ignore)到该信号

如果被阻止的信号在解除阻止之前产生了多次,多个相同种信号会进行队列处理(queued)吗?答案是大部分的UNIX系统都不会将多个同种信号进行队列处理,而是只算一次。(貌似在POSIX.1上增加实时扩展功能才能支持多个同种pending信号的队列化处理。)话不多说,实践一下吧!

程序1简单的向自身发出了多次SIGUSR1信号,并且在信号处理函数中记录了发生的次数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <signal.h>
#include <stdlib.h>

static void sigusr1_handler(int signo);

int main ()
{
  sigset_t oldmask, newmask, pendmask;

  if ( signal(SIGUSR1, sigusr1_handler) == SIG_ERR )
  {
      printf("signal error\n");
      exit(1);
  }

  int i;
  for (i = 0; i < 5; i ++)
  {
      raise(SIGUSR1);
      printf("send SIGUSR1\n");
  }

  printf("sleep started\n");
  sleep(5);
  printf("sleep finished\n");

  exit(0);
}

static void sigusr1_handler(int signo)
{
  static int n = 1;
  printf("receive user1 signal %d times\n", n ++);
  if ( signal(SIGUSR1, sigusr1_handler) == SIG_ERR )
  {
      printf("can't reset SIGUSR1");
      exit(1);
  }
}

程序的结果应该很明显:

receive user1 signal 1 times
send SIGUSR1
receive user1 signal 2 times
send SIGUSR1
receive user1 signal 3 times
send SIGUSR1
receive user1 signal 4 times
send SIGUSR1
receive user1 signal 5 times
send SIGUSR1
sleep started
sleep finished

程序2在程序1的基础上,增加了发出信号之前阻止了该信号,以及之后再解除阻止的操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <signal.h>
#include <stdlib.h>

static void sigusr1_handler(int signo);

int main ()
{
  sigset_t oldmask, newmask, pendmask;

  //加入SIGUSR1信号处理函数
  if ( signal(SIGUSR1, sigusr1_handler) == SIG_ERR )
  {
      printf("signal error\n");
      exit(1);
  }

  //阻止SIGUSR1信号
  sigemptyset(&newmask);
  sigaddset(&newmask, SIGUSR1);
  if ( sigprocmask(SIG_BLOCK, &newmask, &oldmask) < 0 )
  {
      printf("sigprocmask block error\n");
      exit(1);
  }
  printf("SIGUSR1 is blocked\n");

  //发出信号
  int i;
  for (i = 0; i < 5; i ++)
  {
      raise(SIGUSR1);
      printf("send SIGUSR1\n");
  }

  printf("sleep started\n");
  sleep(5);
  printf("sleep finished\n");

  if ( sigpending(&pendmask) < 0 )
  {
      printf("sigpending error\n");
      exit(1);
  }
  if ( sigismember(&pendmask, SIGUSR1) )
  {
      printf("SIGUSR1 was pending\n");
  }

  //恢复之前的信号掩码
  if ( sigprocmask(SIG_SETMASK, &oldmask, NULL) < 0 )
  {
      printf("sigprocmask setmask error\n");
      exit(1);
  }
  printf("restore old signal mask\n");

  exit(0);
}

static void sigusr1_handler(int signo)
{
  static int n = 1;
  printf("receive user1 signal %d times\n", n ++);
  if ( signal(SIGUSR1, sigusr1_handler) == SIG_ERR )
  {
      printf("can't reset SIGUSR1");
      exit(1);
  }
}

再来看运行的结果:

SIGUSR1 is blocked
send SIGUSR1
send SIGUSR1
send SIGUSR1
send SIGUSR1
send SIGUSR1
sleep started
sleep finished
SIGUSR1 was pending
receive user1 signal 1 times
restore old signal mask

虽然发出了多次信号,但由于之前的阻止设置使其发出后处于等待状态,多个同种信号pending,信号处理函数果然只接受到了1次,跟书中讲的是一致的。

USACO Section 3.3 a Game

| Comments

题目大意:有一串长度为N(2<=N<=100)的正整数,两个人按顺序选取最左边或最右边的一个数,将这个数字从数列中去掉,求在双方都进行最优化的选择时,双方选择数字的和分别为多少?

一开始题目的状态为(0,n-1),我们来考虑某个中间状态(i,j)。当前玩家有两种选择:i或者j。选择i,状态就变成(i+1,j);选择j,状态就变为(i,j-1);当i==j时,玩家没得选,只能选择i,然后游戏结束。

我们可以用f[i][j]表示在(i, j)情况下,当前玩家的最优解,即从(i, j)到游戏结束所选择的最大数字和。因为双方都是进行最优化选择,所以根据当前玩家选择i,则另一玩家之后的最优解为f[i+1][j],那么这个情况下当前玩家拿到的数字和是多少呢?应该是sum[i][j] – f[i+1][j]。(sum[i][j]表示i到j的和)。同理,当前玩家选择j时,情况也是类似的。最后我们得到如下递推式:

f[i][j] = max { sum[i][j] – f[i+1][j], sum[i][j] – f[i][j-1] } ( i < j )

f[i][j] = v[i] ( i == j )

实现时,用递归加记忆化就可以解决了,算法复杂度为O(N2)。

关键代码如下:

int CalF(int i, int j)
{
     if ( f[i][j] != -1 )
          return f[i][j];
     if ( i == j )
          return f[i][j] = v[i];
     return ( f[i][j] = sum[i][j] - min(CalF(i+1, j), CalF(i, j-1)) );
}

USACO Section 3.3 Home on the Range

| Comments

题目大意:给定包含0和1的边长为N(2<=N<=250)的正方形,统计其中边长>=2并且全部由1组成的子正方形,子正方形可相互覆盖。

我的理解是,建立三个数组rightEx[][], downEx[][]和squareSize[][],分别表示每一点最右和最下能扩展的距离以及可向右下扩展的(目前)最大正方形的边长,然后枚举组成的正方形边长K(2~N),再枚举每一个点(i, j),若满足以下三个条件:

  • rightEx[i][j] >= k

  • downEx[i][j] >= k

  • squareSize[i+1][j+1] >= k – 1

则squareSzie[i][j] = k,并且更新答案。

算法复杂度为O(N3),还是可以接受的。