我的脚本似乎有一次卡住了

Question

编辑：

所以我让代码运行了70个小时，它没有返回。因此，我坚持我的观点，它确实卡住了什么东西，默默地失败了，让重击挂起来。与N1和N2之间相对较小的跳跃相比，时间的增加不是ao（N）->；O（N²）可以解释的。你知道吗

（从N到2N的输入意味着从N²到4N²的执行时间，因此只需多花费4次。2小时后不返回，而15分钟内完成，最多N意味着失败）

公认的解决方案在达到（立即）非常干净的内存溢出之前工作得非常好。你知道吗

$ py so_mysan.py 400000000 Traceback (most recent call last): File "so_mysan.py", line 36, in sys.exit(main(sys.argv[1:])) File "so_mysan.py", line 8, in main ordering = list(range(N)) MemoryError

谢谢你抽出时间。你知道吗

/编辑

import sys
import numpy as np 
from random import randint

def main(arguments):
    N = int(sys.argv[1])
    # definissons notre ligne de maison : 
    houses = [0]*N
    emptySlot = list(range(0,N)) 
    # counter = 1 
    while (len(emptySlot)>0):
        # on prend une maison vide possiblement habitable par un mysanthrope, au hasard. 
        empt = randint(0, len(emptySlot)-1)
        houses[emptySlot[empt]] = 1
        # on enlève cette maison de notre liste de possibilité 
        # et éventuellement les maisons adjacentes si elles y étaient
        temp = emptySlot[empt]
        del emptySlot[empt]
        # on essaye d'enlever les autres si existes plus efficacement : 
        if (0<=empt and empt<len(emptySlot) and emptySlot[empt] == temp+1):
            del emptySlot[empt] # comme on a viré l'index empt, ça décale.
        if (empt-1 >= 0 and emptySlot[empt-1] == temp-1):
            del emptySlot[empt-1] # pour l'inférieur, cela ne change rien

    occupancyRate = sum(houses) / N
    print(occupancyRate)

if __name__ == '__main__':
    sys.exit(main(sys.argv[1:]))

我想这和数组大小有关，但是我的资源监控并没有显示CPU或RAM的开销。N=4.10^6时运行良好

我不认为多线程是可能的或值得的，因为它只是一个数组被操纵。你知道吗

我能做些什么来优化它？你知道吗

如何调试这样的脚本？我需要知道它是被卡住了，还是花了太多时间。你知道吗

谢谢

Answer 1

这可能需要在代码评审中进行，因为这是一个复杂的问题，但是同样地，所编写的算法不适用于大型的N：所以我将提出一种替代方法。你知道吗

删除列表中间的元素可能会导致非常多（而且代价高昂）的内存操作。最好先准备一个（随机的）元素列表，然后以线性方式访问它们，从而将它们保持在最小值。有一个非常漂亮的函数叫做random.shuffle，可以用来生成一个随机列表：

import random

N = 10000000

ordering = list(range(N))
random.shuffle(ordering)

houses = [0]*N

for elem in ordering:
    if (elem == 0 or houses[elem-1] == 0) and (elem == N-1 or houses[elem+1] == 0):
        houses[elem] = 1

occupancyRate = sum(houses) / N
print(occupancyRate)

在这段代码中，首先生成一个随机元素顺序（使用random.shuffle），然后线性地访问这个随机列表。我也不会在遍历列表时删除任何元素，因为这样做几乎没有什么好处，因为最大内存消耗仍然是相同的。你知道吗

这可能会为您提供更好的运行时间，并允许您处理更大的列表。但是，该算法在时间和内存消耗上仍然是线性的，因此您也会对这个算法感到满意。你知道吗