【JAVA】深深跪了，OJ题目JAVA与C运行效率对比（附带清华北大OJ内存计算的对比）

看了园友的评论之后，我也好奇清橙OJ是怎么计算内存占用的。重新测试的情况附在原文后边。

-------------------------------------- 这是切割线 --------------------------------------------

最近自学Java，试着用Java刷几道OJ的题来熟悉基本语法。

起初几道简单题，没太留意程序的执行效率。今天做了一道简单的递归题，竟然运行超时了！由于本人算法方面功底太差，不懂的如何优化，想了个投机的办法应付了过去。但又觉得不可思议，照以前用C语言刷OJ的经验，不可能这种规模的数据就运行超时。于是我将代码从eclipse复制黏贴到VC中，改成C程序，重新测试，结果惊人。

以下是详细情况：

一、题目

题目位于：http://oj.tsinsen.com/ViewGProblem.page?gpid=A1069

问题描述

　　幻方(magic square)是一个非常有趣的矩阵，n阶的幻方表示一个n阶矩阵，它的元素恰好是1~N^2，它的各行，各列，以及对角线之和都相等。下面是一个非常经典的3阶幻方：
　　2 7 6
　　9 5 1
　　4 3 8
　　你的任务是找出字典序第K小的4阶幻方。
　　这里的幻方的字典序定义为：把幻方按行优先排成一条N^2的序列后的字典序(如上面这个幻方，排成这样一条序列：2 7 6 9 5 1 4 3 8)。
　　其中K<=100。
　　字典序的定义为：在某一系列字符串中，首先按照第一个字符明确其先后顺序，如果第一个字符相同，则根据第二个字符的大小关系明确其先后关系。以此类推 。例如：
　　1 2 3 4 5 6 7 8 9 10 11在2 1 3 4 5 6 7 8 9 10 11之前
　　1 2 3 4 5 6 7 8 9 10 11在1 3 2 4 5 6 7 8 9 10 11之前
输入格式
　　输入仅包含一行K。
输出格式
　　4行4列的幻方，数之间用一个空格隔开，行末不要有多余的空格。
样例输入
1
样例输出
1 2 15 16
12 14 3 5
13 7 10 4
8 11 6 9
 
 
二、Java解答结果
这是我的java解（算法比较渣，风格比较丑，请多指教=。=）
 Java代码

import java.util.Scanner;

public class Main {

    static boolean[] used = new boolean[17];

    static int k;

    static int[][] ary = new int[4][4];

    static boolean found = false;

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        k = input.nextInt();

        for (int i = 1; i <= 16; i++)

            used[i] = false;

        if (k < 70) {

            recursion(0);

        }

        else {

            k -= 69;

            ary[0][0] = 1;

            ary[0][1] = 7;

            used[1] = true;

            used[7] = true;

            recursion(2);

        }

    }

    public static void recursion(int n) {

        int x = n / 4, y = n % 4;

        if (found) return;

        if (n == 16) {

            k--;

            if (k == 0) {

                printMagicSquare();

                found = true;

            }

            return;

        }

        for (int i = 1; i <= 16; i++) {

            if (!used[i]) {

                if (x == 3 && (ary[0][y] + ary[1][y] + ary[2][y] + i) != 34)

                    continue;

                if (y == 3 && (ary[x][0] + ary[x][1] + ary[x][2] + i) != 34)

                    continue;

                if (x == 3 && y == 0 && (ary[0][3] + ary[1][2] + ary[2][1] + i) != 34)

                    continue;

                if (x == 3 && y == 3 && (ary[0][0] + ary[1][1] + ary[2][2] + i) != 34)

                    continue;

                used[i] = true;

                ary[x][y] = i;

                recursion(n + 1);

                used[i] = false;

            }

        }

    }

    public static void printMagicSquare() {

        for (int i = 0; i < 4; i++) {

            for (int j = 0; j < 3; j++) {

                System.out.print(ary[i][j] + " ");

            }

            System.out.println(ary[i][3]);

        }

    }

}

Java代码

main中原本是直接调用recursion(0)，一运行，尼玛运行超时！评测结果如下：

遂加入了那个if(k<70)的判断语句，把上边两个较大的节点也通过了。

但这很不靠谱，因为这题简单，k限制在100以内。再大一些的话，用条件判断是解决不了问题的（除非有超强毅力写一大堆if，全体遍历一遍自动生成if语句倒是个办法）。

三、C解答

于是我把代码复制到VC中，删掉class，把boolean类型改成int类型，去掉了那个if(k<70)的判断语句，代码如下：

 C代码

#include <stdio.h>

int used[17]; //0-false 1-true

int k;

int ary[4][4];

int found = 0;

void recursion(int n);

void printMagicSquare();

int main() {

    int i;

    scanf("%d", &k);

    for (i = 1; i <= 16; i++)

        used[i] = 0;

//    if (k < 70) {

    recursion(0);

/*    }

    else {

        k -= 69;

        ary[0][0] = 1;

        ary[0][1] = 7;

        used[1] = 1;

        used[7] = 1;

        recursion(2);

    }*/

    return 0;

}

void recursion(int n) {

    int x = n / 4, y = n % 4;

    int i;

    if (found) return;

    if (n == 16) {

        k--;

        if (k == 0) {

            printMagicSquare();

            found = 1;

        }

        return;

    }

    for (i = 1; i <= 16; i++) {

        if (!used[i]) {

            if (x == 3 && (ary[0][y] + ary[1][y] + ary[2][y] + i) != 34)

                continue;

            if (y == 3 && (ary[x][0] + ary[x][1] + ary[x][2] + i) != 34)

                continue;

            if (x == 3 && y == 0 && (ary[0][3] + ary[1][2] + ary[2][1] + i) != 34)

                continue;

            if (x == 3 && y == 3 && (ary[0][0] + ary[1][1] + ary[2][2] + i) != 34)

                continue;

            used[i] = 1;

            ary[x][y] = i;

            recursion(n + 1);

            used[i] = 0;

        }

    }

}

void printMagicSquare() {

    int i, j;

    for (i = 0; i < 4; i++) {

        for (j = 0; j < 3; j++) {

            printf("%d ", ary[i][j]);

        }

        printf("%d\n", ary[i][3]);

    }

}

C代码

这次的评测结果如下：

亮瞎狗眼有木有！！！

之前在看斯坦福《编程方法学》公开课视频时，老师有说，Java的运行效率比普通语言慢3倍左右。从上面的运行时间看的确差不多。但是在同一数量级上的。

但本题中，最深17层的递归，Java用了34MB内存，C语言只用了808KB，差距非常大。

以我目前所学的，有以下猜测：

1、Java运行于Java虚拟机上，装载字节文件等本身需要消耗内存空间。

2、Java中的数组都是类，封装了很多数据域和方法，占用一定内存空间；C中数组就是一段连续的内存空间，相对小巧。

3、Java中的栈中，递归时压栈的信息丰富很多，除了跟C一样的返回地址、参数信息，Java中还会保存异常处理链等地址、参数，所以每次递归会占用不少内存。

也不知上述猜测是否是主要原因，还请Java方面的前辈指教~

---------------------------------------------------这也是切割线--------------------------------------------------

鉴于想知道清橙OJ到底有没有把虚拟机的内存也算进程序运行内存，我去提交了A+B Problem.

清华的清橙网：http://oj.tsinsen.com

北大的POJ：http://poj.org

A+B Problem是绝大多数在线评测网站的第一题，内容为：

问题描述

　　输入A,B。
　　输出A+B。
输入格式
　　输入包含两个整数A,B，用一个空格分隔。
输出格式
　　输出一个整数，表示A+B的值。
样例输入
5 8
样例输出
13
数据规模和约定
　　-1,000,000,000<=A,B<=1,000,000,000。

我分别写了Java和C的代码，如下：

 C Code

#include <stdio.h>

int main() {

    int a, b;

    scanf("%d %d", &a, &b);

    printf("%d\n", a+b);

    return 0;

}

C Code

 Java Code

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int a = input.nextInt(), b = input.nextInt();

        System.out.println(a+b);

    }

}

Java Code

一、清华-清橙

清橙上JAVA的评测结果为：

评测点编号 评测结果 得分 运行时间 内存使用
1
正确
10.00
109ms
34.21MB
2
正确
10.00
93ms
34.23MB
3
正确
10.00
109ms
34.24MB
4
正确
10.00
125ms
34.20MB
5
正确
10.00
109ms
34.24MB
6
正确
10.00
125ms
34.24MB
7
正确
10.00
93ms
34.24MB
8
正确
10.00
109ms
34.24MB
9
正确
10.00
109ms
34.21MB
10
正确
10.00
93ms
34.21MB

C的评测结果为：

评测点编号 评测结果 得分 运行时间 内存使用
1
正确
10.00
0ms
784.0KB
2
正确
10.00
0ms
784.0KB
3
正确
10.00
0ms
784.0KB
4
正确
10.00
0ms
784.0KB
5
正确
10.00
0ms
784.0KB
6
正确
10.00
0ms
784.0KB
7
正确
10.00
0ms
784.0KB
8
正确
10.00
0ms
784.0KB
9
正确
10.00
0ms
784.0KB
10
正确
10.00
0ms
784.0KB

跟上边的递归题目比较，发现，java的内存占用始终在34MB左右，C的内存占用从808K降低至784K。

结论：清橙不靠谱。。。把java虚拟机也算进去了。。。

以前上程设导论课有些题目规定占用内存不许超过1MB，用java妥妥死翘。。。Otz。。。

二、北大-POJ

既然清华不靠谱，我就打开北大的也试试，程序还是上面两个，结果如下：

Java：　　3024K　　735MS

C：　　　　164K　　16MS

我表示凌乱了。。。不知道这个是怎么计算的。。。

求问怎么自己测试。。。

 
 

最新文章

  1. [LintCode] Longest Common Prefix 最长共同前缀
  2. 集合覆盖 顶点覆盖： set cover和vertex cover
  3. php 读取文件
  4. 再次认识 vertical-align
  5. 配置新系统（Win7 x64）
  6. WW多线程和锁
  7. iOS开发——UI篇Swift篇&amp;玩转UItableView（二）高级功能
  8. django作models的UPDATE时，注意有过滤外键的情况
  9. new、delete与malloc、free的详解
  10. 好的 vim编辑博客
  11. wemall app中基于Java获取和保存图片的代码
  12. 如何在Oracle官网下载历史版本JDK
  13. 应用wavesurfer.js绘制音频波形图小白极速上手总结
  14. javascript中 for-in和 for-of的区别
  15. 安装VS2017后打开项目提示 asp.net 4.0尚未web服务器注册
  16. 阿里云ECS提示RHSA-2017:3263: curl security update
  17. 移动网络应用开发中，使用 HTTP 协议比起使用 socket 实现基于 TCP 的自定义协议有哪些优势？
  18. js 中的console.log有什么作用
  19. axios上传图片(及vue上传图片到七牛)）
  20. Wireshark 分析捕获的数据记录

热门文章

  1. Oracle\MS SQL Server Update多表关联更新
  2. Struts2 整合jQuery实现Ajax功能(2)
  3. nginx跳转
  4. JQuery日记6.5 Javascript异步模式（一）
  5. ResultSet取结果集多少条记录方法及分页概要
  6. 【android】WebView缓存数据收集
  7. 快速构建Windows 8风格应用10-设备方向
  8. 用css样式围剿等高列问题（转载）
  9. oracle 表导入到powerDesigner 中
  10. SpringMVC表单标签