Stooge 파이썬에서 Java에 비해 기하 급수적으로 더 빠르게 정렬합니까?

Question

나는 Python과 Java 모두에서 stooge sort를 구현했지만, 입력 크기가 늘어남에 따라 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); 
     } 
    } 
} 

과 동등한 파이썬 버전 :

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는 재귀를 좋아한다.

저는 15m 이후에 cpython (2 & 3)을 포기했습니다.