选择二维列表中的所有非空子矩形

Question

任务：打印二维列表中所有非空子矩形，限时1秒

我在 python 试过。但是，我无法提高效率。执行时间超过一秒

import time
start_time = time.time()
a = [[1,2,3],[4,5,6],[7,8,9]]
x = 3
y = 3
for i in range(x):
    a.append(list(map(int,input().split())))
total = []
for h in range(1,x+1):
    for k in range(1,y+1):
        temp = []
        for p in range(x):
            for d in range(y):
                for i in range(p,h):
                    for j in range(d,k):
                        temp.append(a[i][j])
                if len(temp)==0:
                    pass
                else:
                    total.append(temp)
                    temp = []
 print(total)
 print("--- %s seconds ---" % (time.time() - start_time))

代码执行不应超过一秒。有没有其他方法可以减少循环来减少执行时间？

Answer 1

您正在请求用户输入，并且您正在为收集该输入计时。所以时间是没有意义的......用户可以花任意数量的时间来输入数据。你为什么要计时？您需要让用户在 1 秒内输入 3 个数字吗？

此外，输入的数据从未被使用过。它被附加到数组 'a' 上，但在计算中仅使用该数组中的前三个条目，它们在添加输入之前就存在。因此，您不妨将收集用户输入的两行代码从代码中取出。如果你这样做，你会得到：

import time
start_time = time.time()
a = [[1,2,3],[4,5,6],[7,8,9]]
x = 3
y = 3
total = []
for h in range(1,x+1):
    for k in range(1,y+1):
        temp = []
        for p in range(x):
            for d in range(y):
                for i in range(p,h):
                    for j in range(d,k):
                        temp.append(a[i][j])
                if len(temp)==0:
                    pass
                else:
                    total.append(temp)
                    temp = []
print(total)
print("--- %s seconds ---" % (time.time() - start_time))

我运行的结果是：

[[1], [1, 2], [2], [1, 2, 3], [2, 3], [3], [1, 4], [4], [1, 2, 4, 5], [2, 5], [4, 5], [5], [1, 2, 3, 4, 5, 6], [2, 3, 5, 6], [3, 6], [4, 5, 6], [5, 6], [6], [1, 4, 7], [4, 7], [7], [1, 2, 4, 5, 7, 8], [2, 5, 8], [4, 5, 7, 8], [5, 8], [7, 8], [8], [1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 3, 5, 6, 8, 9], [3, 6, 9], [4, 5, 6, 7, 8, 9], [5, 6, 8, 9], [6, 9], [7, 8, 9], [8, 9], [9]]
--- 0.00019288063049316406 seconds ---

大约 1/5 毫秒

也许你的电脑比我的慢？它必须慢 5000 倍以上才能花费 1 秒到运行。

如果你想从用户那里获取输入，即使你没有对它做任何事情，那么在用户输入数据后对你的开始时间进行采样。

选择二维列表中的所有非空子矩形

selecting all non-empty sub-rectangle in a 2D list

python

list

sublist