[자바] Stooge Sort는 자바에 비해 Python에서 기하 급수적으로 느리게?

귀하의 버전은 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)을 포기했습니다.

출처
https://stackoverflow.com/questions/22049927