При большом значении переменной цикла программа зависает

@SergeyKorotun · Регистрация: 10.05.2013

Студворк — интернет-сервис помощи студентам

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from graph import *
 
windowSize(1919, 1079)
canvasSize(1919, 1079)
 
#рисует поточечно
#viewCoords(1919, 0, 1079, 0)
 
penColor("red")
penSize(1) 
a=[[0,1000],[950,0],[1900,1000],[950,1000]]
#a=[[0,1079],[959,0],[1919,1079],[959,1079]]
point(a[0][0], a[0][1])
point(a[1][0], a[1][1])
point(a[2][0], a[2][1])
 
import random
random.seed()
i=0
while i<100000:
   rnd=(random.randint(1,3))
   if rnd==1:
      a[3][0]=(a[0][0]+a[3][0])/2
      a[3][1]=(a[0][1]+a[3][1])/2
   elif rnd==2:
      a[3][0]=(a[1][0]+a[3][0])/2
      a[3][1]=(a[1][1]+a[3][1])/2
   elif rnd==3:
      a[3][0]=(a[2][0]+a[3][0])/2
      a[3][1]=(a[2][1]+a[3][1])/2
   point(a[3][0], a[3][1])
   i+=1
run()

Когда в 20 строке while i<100000: вместо 100 000 устанавливаю 1 000 000, программа как правило зависает, но иногда и выполняется успешно.

Если треугольник заменить на шестиугольник, то уже при 200 000 зависает.
Время работы программы должно быть пропорциональным количеству итераций, и что 1 млн будет выполняться больше 100к в 10 раз, понимаю. Но при 100к время вывода измеряется в секундах, то для 1 млн ждал больше часа и ничего не получил.

Мощности ПК достаточно (i3 8100, ОЗУ 16Gb)

Как верхний левый угол окна совместить с соответствующим углом монитора?

@SergeyKorotun · 09.10.2020, 11:34 **[ТС]**

Сообщение от dondublon

Сообщение от SergeyKorotun
Где же взять их координаты? Чтобы рассчитать следующую, нужно знать координаты предыдущей.
Вы берёте одну точку (x4, y4)? Строите одну, соответствующую ей? А можете взять несколько. Это также ответ на вопрос

Даже если закрыть глаза на то, что это совсем другой алгоритм, выиграш то в чем?
запустите это:

Python
1
2
3
4
for i in range(0, 100000, 1):
    pass
print('end')
input()

Измените 100 000 на 1 000 000
Визуально разницу во времени выполнения заметили? Это и есть преимущество того, что вы предлагаете.

Сообщение от dondublon

Рекурсия - поскольку алгоритм повторяется для каждой тройки вершин.

Повторение - это цикл, рекурсия - это вызов фунции F из тела этой же функции F, которого в этой программе нет и быть не может. У нас наверно разное представление о рекурсии.

Сообщение от dondublon

Ну так округляйте до целого, вроде должно быть понятно, по вашей квалификации.

лишняя операция, пайтон и без округления строит точку.

Сообщение от dondublon

рисовать точку вместо линии

Я только начинаю осваивать пайтон, не нашел в пайтоне, как построить точку размером в 1 пиксель, строю точку в виде отрезка длиной в 2 пикселя. Если знаете команду для построения точки в 1 пиксель, напишите.

Сообщение от dondublon

Тогда вы обречены

Возвращаться на паскаль?

@dondublon · 09.10.2020, 12:40

Сообщение от SergeyKorotun

Повторение - это цикл, рекурсия - это вызов фунции F из тела этой же функции F, которого в этой программе нет и быть не может. У нас наверно разное представление о рекурсии.

Наверное.
Вы слышали такие выражения - "развётка рекурсии в цикл" (обычно используется в динамическом проограммировании), "оптимизация хвостовой рекурсии"? Это схоластика.
Рекурсия - это вызов функции из самой себя. То есть - повторение этой функции, просто с другими параметрами, функция-то та же самая. Теоретически, обычный цикл можно записать в виде рекурсии.

Сообщение от SergeyKorotun

Даже если закрыть глаза на то, что это совсем другой алгоритм, выиграш то в чем?
запустите это:

Как минимум, в читаемости. Рекурсию становится видно. Алгоритм тот же.
Теоретически, несколько запусков можно распараллелить. Рекуррентный алгоритм, когда одно следующее значение получаем из предыдущего - нет.

Сообщение от SergeyKorotun

лишняя операция, пайтон и без округления строит точку.

Строить-то он строит, но я вам дал рецепт ускорения.

Сообщение от SergeyKorotun

Я только начинаю осваивать пайтон, не нашел в пайтоне, как построить точку размером в 1 пиксель, строю точку в виде отрезка длиной в 2 пикселя. Если знаете команду для построения точки в 1 пиксель, напишите.

Зависит от фреймворка. Я не знаю, в чём вы рисуете. В любом случае - фреймворк, который умеет рисовать линию, может и точку поставить

Сообщение от SergeyKorotun

Возвращаться на паскаль?

Возможно. Нативный код всегда быстрее.

Вы хотите чтобы и медитировать на процесс рисования, и чтобы быстро. Сложно удовлетворить все требования.

@SergeyKorotun · 09.10.2020, 13:23 **[ТС]**

Сообщение от dondublon

Вы хотите чтобы и медитировать на процесс рисования, и чтобы быстро.

Я нигде не жаловался на скорость выполнения, только на зависание.

@SergeyKorotun · 12.10.2020, 11:09 **[ТС]**

Переделал на tkinter.
Вставил счетчик. Доходит 140 000 и виснет.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from tkinter import *
 
windowSizeWidth = 1919
windowSizeHeight = 1079
root = Tk()
c=Canvas(root, width=windowSizeWidth, height=windowSizeHeight)
c.pack()
 
text = c.create_text(100, 100, text=0, justify=CENTER, font="Verdana 20")
 
a = [[0, 1000], [950, 0], [1900, 1000], [950, 1000]]
#c.create_line(a[0][0], a[0][1], a[0][0]+1, a[0][1])
#c.create_line(a[1][0], a[1][1],a[1][0]+1, a[1][1])
#c.create_line(a[2][0], a[2][1],a[2][0]+1, a[2][1])
 
import random
random.seed()
i = 0
while i < 1000000:
   rnd = (random.randint(1, 3))
   if rnd == 1:
      a[3][0] = (a[0][0] + a[3][0])/2
      a[3][1] = (a[0][1] + a[3][1])/2
   elif rnd == 2:
      a[3][0]=(a[1][0] + a[3][0])/2
      a[3][1]=(a[1][1] + a[3][1])/2
   elif rnd == 3:
      a[3][0] = (a[2][0] + a[3][0])/2
      a[3][1] = (a[2][1] + a[3][1])/2
   c.create_line(a[3][0], a[3][1], a[3][0]+1, a[3][1])
   i += 1
   if i % 10000 == 0:
       c.delete(text)
       text = c.create_text(100, 100, text=i, justify=CENTER, font="Verdana 20")
       root.update()
root.mainloop()

Добавлено через 11 минут
Дождался еще 10 000 итераций.
Если первые 10 000 итераций выполнялись пару секунд, то от 140 000 до 150 000 выполнялись минут 10.

@dondublon · 12.10.2020, 11:14

Джентльмены, я пас. Я уже посоветовал всё, что мог.

@SergeyKorotun · 12.10.2020, 11:35 **[ТС]**

dondublon, специльно перевел на tkinter, чтобы вы могли запустить у себя. У вас также виснет? И если да, то после скольких итераций.

Сообщение от dondublon

Я уже посоветовал всё, что мог.

Вы советовали изменить алгоритм, а разве он некорректный?

Сообщение от dondublon

Джентльмены, я пас.

Рано пасовать, причина зависания/замедления не установлена.

@dondublon · 12.10.2020, 11:40

SergeyKorotun, я посоветовал сделать прямоугольный буфер, куда ставить точки с целыми координатами.
Можно применить это решение частично, чтобы видеть почти realtime, общий принцип тот же.
+ разделить на несколько потоков, чтобы распараллелить, но тут будет нетривиально.

Ну а разбираться дальше с вашей задачей у меня времени нет, простите.

@dondublon · 13.10.2020, 16:12

Если очень-очень хочется рисовать поточечно и медитировать, то можно пойти следующим путём.
Имеем две операции - вычисление и рисование.
Вычиститель вычисляет точки. Быстро, до хрена и много, и останавливаться не собирается.
Рисовалка рисует. Медленно, но зато! сначала получает много точек, потом всё меньше и меньше.

Делим на 2 потока. Один - вычислялка. Кладёт вычисленные точки в очередь. Второй - рисовалка. Выгребает точки из очереди и рисует их. Сначала рисовалка будет запаздывать, но зато рисовать будет постепенно, как требуется по заданию. Постепенно нагонит.

@Garry Galler · 14.10.2020, 00:03

Сообщение от SergeyKorotun

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

У меня стабильно за 35 сек.

Code
1
2
3
4
Итераций:
  10000  -> 0.36402082443237305
 100000 -> 3.4972000122070312
1000000 -> 35.37902331352234

Хотя памяти жрет, конечно, несуразно много. На 1 млн. итераций почти гиг. Далее - пропорционально. Да ну в пень такую либу...

P.S. Вообще tkinter для таких задач, мягко говоря, не оно...

vic5710 · 14.10.2020, 00:45

Сообщение от Garry Galler

Да ну в пень такую либу...

так зто обертка над tkinter Canvas
тут надо рисовать на пиксельном уровне
у меня 4.4 сек при 1000000 (арифметику не проверял)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from PyQt5 import Qt
import random
from time import time
    
class View(Qt.QWidget):
    
    
    def __init__(self):
        super().__init__()
        self.label = Qt.QLabel()
        self.pix = Qt.QPixmap(1200,800)
        self.pix.fill(Qt.Qt.black)
        self.label.setPixmap(self.pix)
        self.line = Qt.QLineEdit()
        self.line.setText('10000')
        self.line.returnPressed.connect(self.draw)
        grid = Qt.QGridLayout(self)
        grid.setContentsMargins(0,0,0,0)
        grid.addWidget(self.label,0,0,10,10)
        grid.addWidget(self.line,10,0,1,2)
    
                
    def draw(self):
        t0 = time()
        p = Qt.QPainter(self.pix)
        p.setRenderHints(Qt.QPainter.Antialiasing)
        pen = Qt.QPen()
        pen.setWidth(1)
        pen.setColor(Qt.QColor(255,255,0))
        p.setPen(pen)
        
        for point in self.get_points(): 
            p.drawPoint(point[0],point[1])
        self.label.setPixmap(self.pix)
        self.repaint()
        print(time() - t0)
        
    def get_points(self):
        depth = int(self.line.text())
        out = []
        a=[[0,1200],[800,0],[1200,800],[800,1200]]
        while depth:
            rnd = random.randint(1,3)
            if rnd==1:
                a[3][0]=(a[0][0]+a[3][0])/2
                a[3][1]=(a[0][1]+a[3][1])/2
            elif rnd==2:
                a[3][0]=(a[1][0]+a[3][0])/2
                a[3][1]=(a[1][1]+a[3][1])/2
            elif rnd==3:
                a[3][0]=(a[2][0]+a[3][0])/2
                a[3][1]=(a[2][1]+a[3][1])/2
            out.append([a[3][0], a[3][1]])
            depth -= 1
        return out
 
if __name__=="__main__":
    app = Qt.QApplication([])
    w = View()
    w.show()
    app.exec_()

Добавлено через 6 минут
да и алгоритм не айс. реально рисовать можно до пикселя, сначала вычисляется float, потом рисовальщик округляет

Добавлено через 4 минуты
кстати наибольшее время идет на вычисление массива точек

Python
1
2
3
        t0 = time()
        points = self.get_points()
        print(time() - t0)

Bash
1
3.468186140060425

vic5710 · 15.10.2020, 12:17

SergeyKorotun, улучшил вашу рисовалку как я это вижу. но при более 50000 точек интерактив уже виден с трудом

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from PyQt5 import Qt
import random
 
class W(Qt.QWidget):
    def __init__(self):
        super().__init__()
        self.count = 0
        self.a = [[10,590],[400,10],[590,500],[10,590]]
        self.pix = Qt.QPixmap(600,600)
        self.pix.fill(Qt.Qt.black)
        self.btn = Qt.QPushButton('Start',self)
        self.tmr0 = Qt.QTimer()
        self.btn.clicked.connect(self.on_click)
        self.tmr0.timeout.connect(self.on_timer)
        
    def resizeEvent(self,e):
        w,h = self.width(),self.height()
        self.btn.move(w-70,h-30)
        
    def on_click(self):
        txt = self.btn.text()
        if txt == 'Start': 
            self.btn.setText('Stop')
            self.tmr0.start(10)
        elif txt == 'Stop':
            self.btn.setText('Start')
            self.tmr0.stop()
            self.pix.fill(Qt.Qt.black)
            self.count = 0
            #self.update()
            
    def on_timer(self):
        p = Qt.QPainter(self.pix)
        p.setPen(Qt.QPen(Qt.Qt.cyan,1))
        depth = 10
        self.count += depth
        while depth:
            rnd = random.randint(0,2)
            if rnd==0:
                self.a[3][0]=(self.a[0][0]+self.a[3][0])//2
                self.a[3][1]=(self.a[0][1]+self.a[3][1])//2
            elif rnd==1:
                self.a[3][0]=(self.a[1][0]+self.a[3][0])//2
                self.a[3][1]=(self.a[1][1]+self.a[3][1])//2
            elif rnd==2:
                self.a[3][0]=(self.a[2][0]+self.a[3][0])//2
                self.a[3][1]=(self.a[2][1]+self.a[3][1])//2
            p.drawPoint(self.a[3][0], self.a[3][1])
            depth -= 1
        self.update()
        
    def paintEvent(self,e):
        p = Qt.QPainter(self)
        p.drawPixmap(0,0,self.pix)
        p.setPen(Qt.QPen(Qt.Qt.green))
        p.setFont(Qt.QFont('Arial',14))
        p.drawText(5,22,repr(self.count)+' : '+repr(self.a[3]))
        
if __name__=="__main__":
    app = Qt.QApplication([])
    w = W()
    w.resize(600,660)
    w.move(0,0)
    w.show()
    app.exec_()

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@dondublon 4663 / 2082 / 367 Регистрация: 17.03.2012 Сообщений: 10,203 Записей в блоге: 6
	12.10.2020, 11:14
	Джентльмены, я пас. Я уже посоветовал всё, что мог. 1

@dondublon 4663 / 2082 / 367 Регистрация: 17.03.2012 Сообщений: 10,203 Записей в блоге: 6
	12.10.2020, 11:40
	SergeyKorotun, я посоветовал сделать прямоугольный буфер, куда ставить точки с целыми координатами. Можно применить это решение частично, чтобы видеть почти realtime, общий принцип тот же. + разделить на несколько потоков, чтобы распараллелить, но тут будет нетривиально. Ну а разбираться дальше с вашей задачей у меня времени нет, простите. 1

@dondublon 4663 / 2082 / 367 Регистрация: 17.03.2012 Сообщений: 10,203 Записей в блоге: 6
	13.10.2020, 16:12
	Если очень-очень хочется рисовать поточечно и медитировать, то можно пойти следующим путём. Имеем две операции - вычисление и рисование. Вычиститель вычисляет точки. Быстро, до хрена и много, и останавливаться не собирается. Рисовалка рисует. Медленно, но зато! сначала получает много точек, потом всё меньше и меньше. Делим на 2 потока. Один - вычислялка. Кладёт вычисленные точки в очередь. Второй - рисовалка. Выгребает точки из очереди и рисует их. Сначала рисовалка будет запаздывать, но зато рисовать будет постепенно, как требуется по заданию. Постепенно нагонит. 1