выделение всех непустых под прямоугольников в 2D списке - PullRequest
Новая
       16

выделение всех непустых под прямоугольников в 2D списке

0 голосов
/ 29 марта 2019

Задача: Распечатать все непустые под прямоугольники в 2D-списке, ограничение по времени составляет 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))

не должно занимать более одной секунды.Есть ли другой способ сокращения циклов, которые сокращают время выполнения?

1 Ответ

0 голосов
/ 29 марта 2019

Вы запрашиваете ввод у пользователя, и вы рассчитываете время сбора этого ввода.Так что время бессмысленно ... пользователю может потребоваться произвольное количество времени для ввода данных.Зачем вам это время?Вам нужно заставить пользователя ввести 3 цифры менее чем за 1 секунду?

Кроме того, введенные данные никогда не используются.Он добавляется в массив '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 секунду для запуска.

Если вы хотите получить ввод от пользователя, даже если вы ничего с ним не делаете, тогда выберите время запускапосле того, как пользователь ввел данные.

...