Stooge与Python相比，Python在指数上速度较慢？

Question

我已经在Python和Java中实现了stooge排序，但随着输入大小的增加，Python中的运行时间似乎与Java实现相比呈指数级增长。我知道一种算法在Java中运行速度比在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) 

Answer 1

你的版本是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）。