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

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

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

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

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

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