Stooge與Python相比，Python在指數上速度較慢？

我已經在Python和Java中實現了stooge排序，但隨着輸入大小的增加，Python中的運行時間似乎與Java實現相比呈指數級增長。我知道一種算法在Java中運行速度比在Python中運行速度並不少見，但肯定不會太慢。Stooge與Python相比，Python在指數上速度較慢？

這裏的Java代碼：

import java.util.Arrays; 

public class Stooge { 
    public static void main(String[] args) { 
     int[] nums = new int[10000]; 
     for (int i = 10000; i > 0; i--) { 
     nums[10000-i] = i; 
     } 
     stoogeSort(nums); 
     System.out.println(Arrays.toString(nums)); 
    } 

    public static void stoogeSort(int[] L) { 
     stoogeSort(L, 0, L.length); 
    } 

    public static void stoogeSort(int[] L, int i, int j) { 
     if (L[j-1] < L[i]) { 
     int tmp = L[i]; 
     L[i] = L[j-1]; 
     L[j-1] = tmp; 
     } 
     if (j - i >= 3) { 
      int t = (j - i)/3; 
      stoogeSort(L, i, j-t); 
      stoogeSort(L, i+t, j); 
      stoogeSort(L, i, j-t); 
     } 
    } 
}

和等效Python版本：

def main(): 
    nums = [i for i in range(10000, 0, -1)] 
    stoogeSort(nums) 
    print(nums) 

def stoogeSort(L): 
    stoogeSortRec(L, 0, len(L)) 

def stoogeSortRec(L, i, j): 
    if L[j-1] < L[i]: 
     tmp = L[i] 
     L[i] = L[j-1] 
     L[j-1] = tmp 
    if j-i >= 3: 
     t = (j-i) // 3 
     stoogeSortRec(L, i, j-t) 
     stoogeSortRec(L, i+t, j) 
     stoogeSortRec(L, i, j-t)

來源

2014-02-26 funge

在Python中交換變量時不需要臨時變量：'L [i]，L [j-1] = L [j-1]，L [i]' –

我真的很困惑， '重複調用同一個函數兩次。（你在第一個和最後一個叫同樣的stoogeSortRec。）另外，這個問題並不真正相關，但是你不需要在python中使用tmp進行交換。 'L [i]，L [j-1] = L [j-1]，L [i]' – James

@Imagine：重複排序是[Stooge Sort]的一部分（http://en.wikipedia.org/wiki/Stooge_sort）算法，以Three Stooges命名。請注意，該算法甚至比Bubble Sort慢。 –

你的版本是a.py.

它使用列表作爲堆棧以避免遞歸（b.py）修改後的版本：

def main(): 
    nums = [i for i in range(5000, 0, -1)] 
    stoogeSort(nums) 
    print(nums) 

def stoogeSort(L): 
    stack = [(0, len(L))] 
    while stack: 
     i, j = stack.pop() 

     if L[j - 1] < L[i]: 
      L[i], L[j - 1] = L[j - 1], L[i] 
     if j - i >= 3: 
      t = (j - i) // 3 
      stack.append((i, j - t)) 
      stack.append((i + t, j)) 
      stack.append((i, j - t))

時報：

$ time pypy a.py >/dev/null 
real 2m1.855s 
user 2m1.300s 
sys  0m0.453s 


$ time pypy b.py >/dev/null 
real 1m33.410s 
user 1m32.810s 
sys  0m0.413s

沒有甚至Pypy喜歡遞歸。

15米後我放棄了cpython（2 & 3）。

來源

2014-02-26 20:04:25 Javier

這非常有用，謝謝！我仍然想知道爲什麼遞歸版本比Java慢很多。 – funge

沒有解釋器/ jit技巧來加速非尾遞歸調用，所以我不知道。也許Java對於小操作（+， - //）和函數調用來說更快。 – Javier

Stooge與Python相比，Python在指數上速度較慢？

回答

相關問題