为什么同样算法的运行时差异很大？

我做了采访街头问题string similarity。最初我在python中做了这个。这给了我最后5个测试用例的Time Limit Exceeded错误。然后我在java中尝试了相同的方法，并且解决方案得到了接受。前5个测试用例的java和python版本之间的时间差异非常高，但对于前5个测试用例，python比较了java。为什么？为什么同样算法的运行时差异很大？

字符串的长度可以去高达100000

stringsim.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

Solution.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); 
    } 
    } 
}

 
Run time for java: 
1    Success 0.172387 
2  Success 0.172177 
3  Success 0.172185 
4  Success 0.172178 
5  Success 0.263904 
6  Success 2.82661 
7  Success 4.66869 
8  Success 4.83201 
9  Success 1.36585 
10  Success 1.02123 

For python: 
1  Success     0.081229 
2  Success    0.081047 
3  Success    0.081032 
4  Success    0.081015 
5  Success     0.910672 
6  Time limit exceeded. 16.1818 
7  Time limit exceeded. 16.2357 
8  Time limit exceeded. 16.2001 
9  Time limit exceeded. 16.2408 
10  Time limit exceeded. 16.1831

来源

2012-09-22 Sudhagar

而且错误 - 这段代码提供的“解决方案”的**含义究竟是什么？ –

可能是JIT – nullpotent

为了提高您获得深刻见解的答案的机会，请发布一个链接到输入文件，并将您的数字时间度量值作为表格发布，突出显示哪些单元格令人惊讶。没有这些数据，你的具体问题很难回答。 – pts

我同意iccthedral的评论：在Java JIT可能是为什么Python在前几个小输入中速度更快的一个可能原因。要验证这一点，请调整输入顺序（以便首先输入大量输入），在同一过程中为所有输入运行，然后再为每个输入测量时间。如果Python在这种情况下对于最后几个（小）输入较慢，则推定被证实。

验证它的另一种方法是将小输入添加到最后（也将它们保存在开始处），并查看Java执行所有操作需要多长时间。如果三角洲只比小投入的执行时间大得多，则推定被确认。

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

这种情况很可能发生在您的案例中：到Python找到答案的时候，Java仍在运行字节码或运行JIT以将字节码编译为机器码。但是最终Java会迎头赶上，因为机器代码要快得多。

来源

2012-09-22 10:03:15 pts

尝试使用Java测量自己的时间。我的意思是在主方法内计算毫秒数。在Python中执行相同的操作。我想你的答案中的时间是在OS中测量的 - java进程运行的时间。前5个示例的时间可能主要是启动JVM进程的开销。

来源

2012-09-22 10:31:47

为什么同样算法的运行时差异很大？

回答

相关问题