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

@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_()

Новые блоги и статьи Все статьи Все блоги /
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .

@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