时间戳

首页 > 解决方案 > 实施 bogosort 的问题

python - 实施 bogosort 的问题

问题描述

出于某种原因，我决定在 python 中实现全能的 bogosort，并编写了以下代码：

import numpy as np

def checkSorted(x):
  if x == sorted(x[:]):
    return True
  else:
    return False

def bogosort(x):
  np.random.shuffle(x)
  if checkSorted(x):
    return
  else:
    bogosort(x)

arr = [1,3,2]
bogosort(arr)
print(arr)

当数组大小超过 4 时，我会收到以下错误：

RecursionError：调用 Python 对象时超出了最大递归深度

哎呀！我找到了解决方法：

import sys
sys.setrecursionlimit(50000)

这对于 8 的数组大小应该没问题，因为 8！是40320，但是这次却遇到了segmentation fault！

repl 进程意外死亡：信号：分段错误（核心转储）

又来了！我认为这一次它的内存不足并崩溃了。有没有办法增加允许的内存使用量来防止这种情况？

我真的希望这个算法至少可以使用 10 的数组大小，这样我就可以绘制一个与其他算法进行比较的图表，因为像快速排序这样的东西甚至不能用小于 10 的输入来计时。

标签： pythonsortingmemory

解决方案

由于随着数组大小的增加， bogosort 可能需要非常非常长的时间来运行，因此使用迭代而不是递归可能会更好。这是因为较大的数组很容易超过递归深度。

在这里，我编辑了您的代码以使用循环。我还使您的一些代码更简洁。

import random

def checkSorted(x):
    # A more concise way is to just return the comparison,
    # which will evaluate to either True or False.
    return x == sorted(x)

def bogosort(x):
    # Instead of using recursion, you could use iteration.
    # List x will continue to be shuffled until it is sorted.
    while not checkSorted(x):
        random.shuffle(x)
    # Once x is sorted, return it.
    return x

# Here, I just initialized arr as a list of integers from 0 to 5, excluding 5
arr = list(range(5))
# To test bogosort, let's shuffle the list beforehand
random.shuffle(arr)
# Run bogosort, then print the sorted array
bogosort(arr)
print(arr)

我还使用了 Python 的内置random模块。虽然如果需要，您可以自由使用numpy。

推荐阅读