V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xpol
V2EX  ›  程序员

为什么 leetcode 上面 Java 跑得比 C/C++ 快?

  •  
  •   xpol · 2016-07-07 15:05:55 +08:00 · 9605 次点击
    这是一个创建于 3061 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如下图:

    Imgur

    最快的居然是 Java ?为什么呢?

    我猜想可能是这几个方面:

    1. 由于 GC 机制, Java 没有内存释放的时间消耗
    2. 或者 leetcode 跑 Java 代码的虚拟机一直运行着的,没有启动开销
    第 1 条附言  ·  2016-07-07 16:49:55 +08:00

    补充一下,我说的是 第二题,这是我的C++代码:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            auto carry = 0;
    
            ListNode* p1 = l1;
            ListNode* p2 = l2;
            ListNode* last = l1;
            while (p1 != nullptr && p2 != nullptr) {
                auto v = p1->val + p2->val + carry;
                carry = v/10;
                p1->val = v%10;
                last = p1;
                p1 = p1->next;
                p2 = p2->next;
            }
            ListNode* left = p1 != nullptr ? p1 : p2;
            last->next = left;
    
            while (left != nullptr) {
                auto v = left->val + carry;
                carry = v/10;
                left->val = v%10;
                last = left;
                left = left->next;
            }
            if (carry > 0) {
                last->next = l2;
                l2->val = carry;
                l2->next = nullptr;
            }
            
            return l1;
        }
    };
    

    为了跑快一点,我还重用了输入参数的内存,用来生产输出的链表。 我这在C++提交里面算是快的了。

    不是我对Java的运行速度有偏见,我只是想弄清楚,为什么大多数 Java 提交都几乎比所有的 C/C++ 快。

    到底快的原因是什么?

    26 条回复    2016-07-08 07:00:50 +08:00
    dangbiao1991
        1
    dangbiao1991  
       2016-07-07 15:22:25 +08:00
    你这只能表明本题提交的解法里, Java 代码性能大体比 C/C++ 好。
    我见到的其它题目并不是这样的。
    domty
        2
    domty  
       2016-07-07 15:23:03 +08:00
    你是怎么比较的。
    以我的经验,其实和代码的质量还是有关系的。

    同一个问题,我用 c 写的和 python 写的,运行时间 python 大概是 c 的 10 分之一。
    大概是我写的 c 太烂了 /手动 doge
    3dwelcome
        3
    3dwelcome  
       2016-07-07 15:29:53 +08:00 via Android
    Java 又不差的、都是 jit,cpp 没大优势。
    hard2reg
        4
    hard2reg  
       2016-07-07 15:35:40 +08:00
    为什么总有人喜欢比较语言之间的速度
    felixzhu
        5
    felixzhu  
       2016-07-07 15:39:47 +08:00
    发现讨论这个的还挺多的,估计是 leetcode 没太在意这个
    https://discuss.leetcode.com/topic/14927/why-are-c-java-so-slow-different-test-cases/2
    skydiver
        6
    skydiver  
       2016-07-07 15:42:53 +08:00
    不同语言的统计口径都不一样,没法比较
    shyling
        7
    shyling  
       2016-07-07 15:44:07 +08:00
    java 就是启动慢点内存占用多点,速度还行啊。。而且不容易写太差的代码。。不过 2L python 比 c 快 10 倍让我吃了一惊
    Marfal
        8
    Marfal  
       2016-07-07 15:45:26 +08:00
    @hard2reg 为什么不?
    BlueMeow
        9
    BlueMeow  
       2016-07-07 15:47:25 +08:00
    现在的 Java 本来就很快,而且有各种高度优化的库可以用
    YORYOR
        10
    YORYOR  
       2016-07-07 15:55:56 +08:00
    @BlueMeow leetcode 上只能用一些基本的库吧
    Sorrow
        11
    Sorrow  
       2016-07-07 16:04:31 +08:00
    这和 leetcode 的测试方法有关。
    你可以在本地测试同样的算法, Java 几乎不可能体现出图中这么明显的差距,特别是在 C++ 开了优化的情况下。
    wd85318
        12
    wd85318  
       2016-07-07 16:06:11 +08:00
    Java 是香港记者?
    hpeng
        13
    hpeng  
       2016-07-07 16:08:02 +08:00
    你需要控制变量法.
    BlueMeow
        14
    BlueMeow  
       2016-07-07 16:19:52 +08:00
    @YORYOR Java 基本类库已经是多年针对 JVM 高度优化的,速度快很正常
    dynastysea
        15
    dynastysea  
       2016-07-07 16:20:04 +08:00
    测试代码是啥都不知道,你要写个求 1+1=多少的代码,任何语言都有可能比 C/C++快啊
    wzxjohn
        16
    wzxjohn  
       2016-07-07 16:31:54 +08:00
    吐槽算法的来看看这题:
    https://leetcode.com/problems/add-digits/
    wzxjohn
        17
    wzxjohn  
       2016-07-07 16:33:15 +08:00
    @dynastysea 真的假的, JVM 启动时间不算?
    2225377fjs
        18
    2225377fjs  
       2016-07-07 16:48:56 +08:00
    如果去掉 JVM 启动时间,而且纯做运算,不涉及大量的系统调用,带 JIT 的语言运行速度跟本地编译语言并不会多大差距,反而类似于 Java 这些,因为本身有质量非常高的类库,在实现一些算法,数据结构的时候可能还会有优势。
    hpeng
        19
    hpeng  
       2016-07-07 16:55:56 +08:00
    你可以省下一个 while 哦
    Sorrow
        20
    Sorrow  
       2016-07-07 17:02:19 +08:00   ❤️ 2
    作了一个简单的测试,你的代码在 leetcode 上运行时间大概是 40ms 左右,一份普通的 Java 代码运行时间大概是 4ms, 相差一个数量级。我在本地写了一些测试样例,用你的代码和 Java 比较, C++ 运行时间大概 20ms(不开优化), Java 大概在 35ms 左右, 是 Java 和 C++ 的正常差距。

    楼上的人完全没有意识到在这个问题下其实任何测试样例都不可能让 C++ 和 Java 产生数量级的差距(如图中分布的那样, Java 和 C++ 大概相差一个数量级),所以这必然是 Leetcode 测试方法的问题。
    Sorrow
        21
    Sorrow  
       2016-07-07 17:11:32 +08:00
    至于 Java 为什么是最快的,和楼上几位说的 JVM 优化好之类的是没什么关系的。主要还是因为 Leetcode 对各种语言测试里, Java 最接近真实的速度。不太了解 Leetcode 具体测试方法,我猜测应该是其他语言的测试时间计算存在某些缺陷,而只有 Java 是纯粹的运行时间。
    wph95
        22
    wph95  
       2016-07-07 17:36:57 +08:00
    作为一个天天写 sandbox 维护 oj 的蒟蒻
    支持楼上 sorrow 的猜测。
    因为 java 在多数 online judge 是特殊对待的。
    因为 JVM 启动时间相对来说太慢了。 所以有个补时。

    也有可能是 jvm 虚拟机一直运行。
    BlueMeow
        23
    BlueMeow  
       2016-07-07 17:58:59 +08:00
    @Sorrow Java 是后来调整过的,本来(一年前多吧)就数它最慢了(当时好像还没有 JS )。既然经过调整,也许就是因为之前的统计方式不太合理。
    chiu
        24
    chiu  
       2016-07-07 18:10:25 +08:00
    我目前写过的基本是 C 最快
    testlc
        25
    testlc  
       2016-07-07 18:57:59 +08:00
    这个问题在知乎上面有吧
    billwsy
        26
    billwsy  
       2016-07-08 07:00:50 +08:00 via iPhone
    看到除和取余…
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1107 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 18:44 · PVG 02:44 · LAX 10:44 · JFK 13:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.