我已经在 Python 和 Java 中实现了 stooge sort,但随着输入大小的增加,与 Java 实现相比,Python 中的运行时间似乎呈指数级增长。我知道算法在 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)
最佳答案
您的版本是 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)。
关于java - 与 Java 相比,Python 中的 Stooge Sort 指数慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22049927/