一些无聊的效率问题

放牛娃1988 发布于 2012/01/10 19:51
阅读 893
收藏 0

首先,这里谈到的效率是非常细微的部分,所以这个效率问题没有任何实际的应用价值,只为爱好者研究之用,所以标题中添加“无聊”二字,以防阅者纠结于“效率不在细节”云云。

起因是我在解决一个算法问题,测试了一下效率,得出以下结论,不做深追,仅以结果示之:

1)计算1到1亿的和,java费时120毫秒,php费时23秒,两者相差近200倍。

2)在java中,将整数i转换成字符串,可以i+""也可以Integer.toString(i),前者耗时是后者的2.5倍。

3)在java中,遍历字符串中各个字符并进行比较,可以将字符串拆解成字符数组进行遍历,也可以用String.charAt()方法进行遍历,遍历时后者耗时是前者的1.5倍。但是前者需将字符串拆解成字符数组也需要时间,加上这部分时间,前者反而是后者的1.7倍。

加载中
0
袁世超
袁世超
直观感觉,这些现象应该是编译优化的结果。
0
redraiment
redraiment

我想你说的是之前那个统计1的题目。也许你用字符串来操作,但是如果直接操作整数,效率也会高很多,比如下面这段朴素算法的代码,在我的电脑上运行是3.7秒:

public class Sum {
    public static void main(String[] args) {
        int sum = 0;
        for (int i = 1; i <= 100000000; i++) {
            for (int n = i; n > 0; n /= 10) {
                if (n % 10 == 1) {
                    sum++;
                }
            }
        }
        System.out.println(sum);
    }
}

0
放牛娃1988
放牛娃1988

引用来自“redraiment”的答案

我想你说的是之前那个统计1的题目。也许你用字符串来操作,但是如果直接操作整数,效率也会高很多,比如下面这段朴素算法的代码,在我的电脑上运行是3.7秒:

public class Sum {
    public static void main(String[] args) {
        int sum = 0;
        for (int i = 1; i <= 100000000; i++) {
            for (int n = i; n > 0; n /= 10) {
                if (n % 10 == 1) {
                    sum++;
                }
            }
        }
        System.out.println(sum);
    }
}

很好的尝试,不过在我的机器上却需要11.381秒,还是要慢于我直接操作字符串的9.59秒啊,看来兄台的机器比我的强大不少,我的代码如下,你可以拿去测试一下:

		int total = 0;
		for(int i = 1; i <= 100000000; i++){
			String number = Integer.toString(i);
			int length = number.length();
			for (int j = 0; j < length; j++) {
				if (number.charAt(j) == '1') {
					total++;
				}
			}
		}

0
放牛娃1988
放牛娃1988

我的测试结果居然是:
1)先除(除数为变数)后求模,效率最高,为8.611秒
2)直接操作字符串,其次,为9.861秒
3)先除(除数为定数)后求模,最小最低,为11.544秒。

代码放在分享里了:http://www.oschina.net/code/snippet_127301_8149

0
redraiment
redraiment

引用来自“唐明星”的答案

我的测试结果居然是:
1)先除(除数为变数)后求模,效率最高,为8.611秒
2)直接操作字符串,其次,为9.861秒
3)先除(除数为定数)后求模,最小最低,为11.544秒。

代码放在分享里了:http://www.oschina.net/code/snippet_127301_8149

不晓得你用的Java虚拟机是什么版本。我用的是 Oracle Java 7.0,结果是:

80000001,费时:11441
80000001,费时:4536
80000001,费时:10942

放牛娃1988
放牛娃1988
我特地下载了1.7做测试,结果还是没变,估计是硬件的关系
放牛娃1988
放牛娃1988
我用的是1.6
0
xyz555
xyz555

楼主应该明白以下几点:

1、php是解释性语言,而Java说是说是解释性的,但其实它是半编译型的,Java编译器会把源码编译成一种介于机器码和源码的class文件,这样的处理让Java很多特性接近于c语言,有人研究甚至有些特性超过c

2、对于web工程来说,应该是IO密集型而不是CPU密集型的,如果你的工程是CPU密集型的话,你就应该好好审查一下你的工程设计在那里有问题了。

xyz555
xyz555
@唐明星 : 另外我举web工程的意思是指一个实际的应用。什么算法,效率都是要根据实际应用来的,没有实际应用价值的东西讨论没有什么意义。
xyz555
xyz555
楼主在那里看到php会编译成中间代码了?呵呵,php是纯解释的语言,加密php不是编译。你见过所谓的php中间代码吗?讨论问题是需要有前提的,不是一个数量级上的东西说得没有意义,不是某种语言的长处,实际不会出现或很少很少出现的情况也没什么意义。
放牛娃1988
放牛娃1988
1.php也是先编译成中间代码,然后解释执行的,只是java的叫字节码,php的叫操作码,名字不同,实质一样。你所看到的是假象,只知java有bytecode,而不知道php有opcode,前者是面向程序员,后者php有意隐藏了而已(php代码缓存器,比如APC,就是缓存的opcode,防止重复解释)。 2.不是web工程,一个普通算法而已。况且我说过了,这些细节不影响程序,只是作为研究而言罢了。
0
Jeky
Jeky

楼主测试一下这两个:

    public static int computeBit4() {
        int total = 0;
        final int BIT_MAP_SIZE = 10000;
        int[] bitMap = new int[BIT_MAP_SIZE];
        for (int i = 1; i <= 100000000; i++) {
            if (i < BIT_MAP_SIZE) {
                int count = 0;
                for (int j = 1; j <= i; j *= 10) {
                    if (i / j % 10 == 1) {
                        count++;
                    }
                }
                bitMap[i] = count;
                total += count;
            } else {
                int num = i;
                while (num > 0) {
                    total += bitMap[num % BIT_MAP_SIZE];
                    num /= BIT_MAP_SIZE;
                }
            }
        }
        return total;
    }

    public static int computeBit5() {
        int total = 0;
        final int BIT_MAP_SIZE = 10000;
        int[] bitMap = new int[BIT_MAP_SIZE];
        for (int i = 1; i <= 100000000; i++) {
            if (i < BIT_MAP_SIZE) {
                int count = 0;
                for (int j = 1; j <= i; j *= 10) {
                    if (i / j % 10 == 1) {
                        count++;
                    }
                }
                bitMap[i] = count;
                total += count;
            } else if (i != 100000000) {
                total += bitMap[i % BIT_MAP_SIZE] + bitMap[i / BIT_MAP_SIZE];
            } else {
                total += 1;
            }
        }
        return total;
    }

另外,对于程序运行时间应使用System.nanoTime()而不是使用System.currentTimeMillis(),这样可能导致毫秒级别不够准确,看看API的说法:

http://static.oschina.net/uploads/doc/javase-6-doc-api-zh_CN/java/lang/System.html#currentTimeMillis()

http://static.oschina.net/uploads/doc/javase-6-doc-api-zh_CN/java/lang/System.html#nanoTime()

Jeky
Jeky
@canghailan : 空间换时间嘛...时间复杂度确定了以后就只能这样了...
canghailan
canghailan
这种计算没有特殊算法,查表的确是王道。
放牛娃1988
放牛娃1988
分别是2.4秒和0.97秒,确实厉害,当属冠军!
0
BossKiller
BossKiller
做web应用,我首先是选择PHP(当然我也不会java),不是因为它运行得快,而是开发得快,就这么简单。
0
放牛娃1988
放牛娃1988

引用来自“xyz555”的答案

楼主应该明白以下几点:

1、php是解释性语言,而Java说是说是解释性的,但其实它是半编译型的,Java编译器会把源码编译成一种介于机器码和源码的class文件,这样的处理让Java很多特性接近于c语言,有人研究甚至有些特性超过c

2、对于web工程来说,应该是IO密集型而不是CPU密集型的,如果你的工程是CPU密集型的话,你就应该好好审查一下你的工程设计在那里有问题了。

对于第一个问题, 我不打算说服您赞同我的意见, 但是我建议您百度一下"php opcode",我相信您一定会有自己的认识。

对于第二个问题,请参见主楼的开头一段,谢谢。

0
Monkey
Monkey
我提醒楼主,你所写的测试代码本身就是有错误的,所以这个结果必然是不正确的。如果你是在要坚持这样测试,最少你要把次数减少,控制在不启动垃圾回收的范围内,另外在启动后面两个方法测试之前必须手动启动垃圾回收,否则你的测试数据就是完全的把你自己给误导了。
返回顶部
顶部