1

我做了面试街头问题字符串相似性。最初我是在 python 中执行此操作的。这给了我最后 5 个测试用例的 Time Limit Exceeded 错误。然后我在java中尝试了相同的解决方案并被接受。最后 5 个测试用例的 java 和 python 版本之间的时间差非常高，但前 5 个测试用例的 python 优于 java。为什么呢？

字符串的长度可以达到 100000。

字符串sim.py

N=int(raw_input())
while N!=0:
    rootstr=[i for i in raw_input()]
    solution=0
    for i in xrange(len(rootstr)):
        for j in xrange(i,len(rootstr)):
            if(rootstr[j-i]==rootstr[j]):solution+=1
            else:break
    print solution
    N-=1

解决方案.java：

class Solution{
    public static void main(String[] args) {
    java.util.Scanner sc=new java.util.Scanner(System.in);
    int N=sc.nextInt(),sol;
    while(N--!=0){
        sol=0;
        char[] s=sc.next().toCharArray();
        for(int i=0;i<s.length;i++){
            for(int j=i;j<s.length;j++){
                if(s[j]==s[j-i]) sol++;
                else break;
            }
        }
        System.out.println(sol);
    }
    }
}

java的运行时间：
1 成功 0.172387
2 成功 0.172177
3 成功 0.172185
4 成功 0.172178
5 成功 0.263904
6 成功 2.82661
7 成功 4.66869
8 成功 4.83201
9 成功 1.36585
10 成功 1.02123

对于蟒蛇：
1 成功 0.081229
2 成功 0.081047
3 成功 0.081032
4 成功 0.081015
5 成功 0.910672
6 超出时间限制。16.1818
7 超出时间限制。16.2357
8 超出时间限制。16.2001
9 超出时间限制。16.2408
10 超出时间限制。16.1831
4

2 回答 2

1

尝试在 Java 中自己测量时间。我的意思是在 main 方法中计算毫秒数。在 Python 中做同样的事情。我猜你答案中的时间是在操作系统中测量的——java进程运行的时间。前 5 个示例的时间可能主要是启动 JVM 进程的开销。

于 2012-09-22T10:31:47.080 回答
1

我同意 iccthedral 的评论：Java JIT 可能是 Python 对于前几个小输入更快的一个可能原因。为了验证这一点，颠倒输入顺序（因此大输入首先出现），在同一过程中对所有输入运行它，然后再次测量每个单独输入的时间。如果 Python 在这种情况下对于最后几个（小）输入很慢，则该假设得到确认。

验证它的另一种方法是将小输入也添加到末尾（也将它们保留在开头），并查看 Java 执行所有内容需要多长时间。如果增量远大于仅小输入的执行时间，则确认该假设。

Java JIT 将 Java 字节码编译为机器码（CPU 可以直接且非常快速地执行）。但只有那些 Java 花费大量时间执行它们的 Java 方法才被转换。（这是因为将所有方法转换为机器代码会很慢，并且生成的机器代码需要太多内存。）所以当 Java 进程启动时，它开始以字节码的形式执行所有方法，它测量每个方法花费了多少时间方法，一旦达到某个方法的阈值，它就会使用 JIT 将该方法编译为机器代码。之后，该方法执行得更快。但是，在流程执行的开始，所有的方法都很慢，并且在很短的时间内，Java 进程变得更慢，因为它忙于运行 JIT。

您的情况很可能正在发生这种情况：当 Python 找到简单问题的答案时，Java 仍在运行字节码或运行 JIT 以将字节码编译为机器码。但最终 Java 会赶上来，因为机器码要快得多。

于 2012-09-22T10:03:15.507 回答