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

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

Новые блоги и статьи Все статьи Все блоги /
Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .
Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .

@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