爲什麼同樣算法的運行時差異很大？

我做了採訪街頭問題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

爲什麼同樣算法的運行時差異很大？

回答

相關問題