Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
0 / 0 / 0
Регистрация: 03.06.2015
Сообщений: 34

Распараллеливание в python, имеет ли смысл?

09.04.2020, 20:32. Показов 2689. Ответов 11

Студворк — интернет-сервис помощи студентам
Добрый день, имеется программа написанная на python, которая выполняет построение кривой Госпера и на большом количестве итераций - 7, 8, программа работает заметно долго. Необходимо предоставить параллельный вариант, чтобы удовлетворить условию - ускорить скорость построения фрактала при случаях с n итераций = 7, 8, хотя бы в 2 раза. Подскажите, в какую сторону смотреть и есть ли смысл пытаться реализовать это на python?

Собственно, сам код:
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
66
67
68
69
70
71
72
73
74
75
import matplotlib.pyplot as plt
import numpy as np
import math
from PIL import Image
from math import sin, cos, atan2, radians
 
class turtle:
    def __init__(self):
        self._direction = np.array([1, 0]) # 2D direction vector
        self._position = np.array([0, 0]) # 2D position vector
    def forward(self):
        pos = self._position
        dirn = self._direction
        self._position = np.add(pos, dirn)
    def rotate(self, theta):
        (x, y) = self._direction
        current_angle = atan2(y, x)
        new_angle = current_angle + radians(theta)
        self._direction = [cos(new_angle), sin(new_angle)]
 
def L_system(commands, axiom, production_rules, theta, n_iterations):
    command_string = axiom # Begin commands with only the axiom
    for iteration in range(n_iterations):
        new_command_string = str()
        for char in command_string:
            if char in production_rules:
                new_command_string += production_rules[char]
            else:
                new_command_string += char
        command_string = new_command_string
 
    n_commands = len(command_string) # Total number of commands for the turtle
 
    t = turtle() # Initialize a turtle at position [0, 0]
 
    positions = np.zeros((n_commands, 2))
 
    for i, command in enumerate(command_string):
        if command in commands:
            exec(commands[command]) # Perform command on turtle
        positions[i, :] = t._position
 
    return positions
 
# Alghoritm for Gosper curve (commands, axiom, rules, number of iterations and angle)
commands = {
    'A': 't.forward()',
    'B': 't.forward()',
    '+': 't.rotate(theta)',
    '-': 't.rotate(-theta)',
    }
axiom = 'A'
production_rules = {
    'A': '+-A-B--B+A++AA+B-',
    'B': '+A-BB--B-A++A+B'
    }
theta = 60
 
n_iterations = int(input("Введите Количество итераций: "));
angle = int(input("Введите угол наклона: "));
positions = L_system(commands, axiom, production_rules, theta, n_iterations)
pointX = int(input("Введите точку по оси Х: "));
pointY = int(input("Введите точку по оси Y: "));
 
def rotate_origin_only(positions, pointX, pointY, angle):
    x = positions[:, 0] + pointX
    y = positions[:, 1] + pointY
    xx = x * math.cos(angle) + y * math.sin(angle)
    yy = -x * math.sin(angle) + y * math.cos(angle)
    return xx, yy
 
xx, yy = rotate_origin_only (positions, pointX, pointY, angle)
plt.plot(xx, yy)
plt.savefig('out.jpg')
plt.show()
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
09.04.2020, 20:32
Ответы с готовыми решениями:

Имеет ли смысл перехода с python на golang?
Что выбрать для backend? Большая ли разница в скорости на backend? Есть ли у языка своя ниша? Каковы перспективы и трудоустройство...

Имеет ли смысл?
Есть комп, проц core 2 duo е6300 2.6 ГГц, разогнан до 3.12 ГГц с кулером от zalman мать asrock G31M-S жд wd 500гб + no name 180гб ...

Имеет ли смысл
Для привлечения дополнительных посетителей в интернет-магазин запчастей подумал о создании отдельного сайта, который будет полностью...

11
Заклинатель змей
 Аватар для DobroAlex
705 / 560 / 219
Регистрация: 30.04.2016
Сообщений: 2,605
09.04.2020, 21:03
Defrezz, параллелить можно любые вычисления, использующие не связанные данные. Рекомендую смотреть в сторону ThreadPoolExecutor или ProcessPoolExecutor. В Вашем случае скорее последнее
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
09.04.2020, 21:08
Да скорее всего ProcessPoolExecutor
0
5516 / 2869 / 571
Регистрация: 07.11.2019
Сообщений: 4,760
09.04.2020, 23:14
DobroAlex,
Цитата Сообщение от DobroAlex Посмотреть сообщение
параллелить можно любые вычисления, использующие не связанные данные.
Вы сам алгоритм смотрели?
Фракталы, соответственно, рекурсия. Как это распараллелить?
0
Заклинатель змей
 Аватар для DobroAlex
705 / 560 / 219
Регистрация: 30.04.2016
Сообщений: 2,605
09.04.2020, 23:51
u235, я и не говорю, что именно это можно параллелить, я указываю ТС общий принцип когда можно параллелить
0
5516 / 2869 / 571
Регистрация: 07.11.2019
Сообщений: 4,760
10.04.2020, 08:58
Лучший ответ Сообщение было отмечено Defrezz как решение

Решение

Defrezz,
1. 54 строка, уберите +-
2. Хорошо бы пропарсить command_string перед расчетом координат и удалять +- (-+), т.к. это тождественные операции.
3. в positions попадает много дублей, из-за того что +и- не меняют координаты.

Добавлено через 6 минут
Возможно, на больших n можно использовать то, что операции поворота принадлежат циклической группе С6.
+++++==-
+++==---
и т.д.



Добавлено через 48 минут
п1-2 позволяют ускорить программу примерно на 13%
п.3 ускорит программу, думаю, ~ в 2 раза.

Добавлено через 43 минуты
Вот с костылями:
Кликните здесь для просмотра всего текста
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import matplotlib.pyplot as plt
import numpy as np
import math
from PIL import Image
from math import sin, cos, atan2, radians
 
class turtle:
    def __init__(self):
        self._direction = np.array([1, 0]) # 2D direction vector
        self._position = np.array([0, 0]) # 2D position vector
    def forward(self):
        pos = self._position
        dirn = self._direction
        self._position = np.add(pos, dirn)
    def rotate(self, theta):
        (x, y) = self._direction
        current_angle = atan2(y, x)
        new_angle = current_angle + radians(theta)
        self._direction = [cos(new_angle), sin(new_angle)]
 
def L_system(commands, axiom, production_rules, theta, n_iterations):
    command_string = axiom # Begin commands with only the axiom
    for iteration in range(n_iterations):
        new_command_string = str()
        for char in command_string:
            if char in production_rules:
                new_command_string += production_rules[char]
            else:
                new_command_string += char
        command_string = new_command_string
 
    # удаляем +- и -+
    command_string=command_string.replace('+-','')
    command_string=command_string.replace('-+','')
    n_commands = len(command_string)
 
    t = turtle() # Initialize a turtle at position [0, 0]
 
    positions = np.zeros((n_commands, 2))
 
    for i, command in enumerate(command_string):
        if command in commands:
            exec(commands[command]) # Perform command on turtle
        positions[i, :] = t._position
 
    return positions
 
# Alghoritm for Gosper curve (commands, axiom, rules, number of iterations and angle)
commands = {
    'A': 't.forward()',
    'B': 't.forward()',
    '+': 't.rotate(theta)',
    '-': 't.rotate(-theta)',
    }
axiom = 'A'
production_rules = {
    'A': 'A-B--B+A++AA+B-',
    'B': '+A-BB--B-A++A+B'
    }
theta = 60
 
n_iterations = int(input("Введите Количество итераций: "));
angle = 60#int(input("Введите угол наклона: "));
positions = L_system(commands, axiom, production_rules, theta, n_iterations)
pointX = 100#int(input("Введите точку по оси Х: "));
pointY =100# int(input("Введите точку по оси Y: "));
 
# удаляем повторяющиеся координаты
i, = np.where(np.diff(positions[:,0]) == 0)
positions=np.delete(positions,i, axis=0) 
 
def rotate_origin_only(positions, pointX, pointY, angle):
    x = positions[:, 0] + pointX
    y = positions[:, 1] + pointY
    xx = x * math.cos(angle) + y * math.sin(angle)
    yy = -x * math.sin(angle) + y * math.cos(angle)
    return xx, yy
 
xx, yy = rotate_origin_only (positions, pointX, pointY, angle)
plt.plot(xx, yy)
plt.savefig('out.jpg')
plt.show()
1
0 / 0 / 0
Регистрация: 03.06.2015
Сообщений: 34
10.04.2020, 09:11  [ТС]
Цитата Сообщение от u235 Посмотреть сообщение
Defrezz,
1. 54 строка, уберите +-
2. Хорошо бы пропарсить command_string перед расчетом координат и удалять +- (-+), т.к. это тождественные операции.
3. в positions попадает много дублей, из-за того что +и- не меняют координаты.

Добавлено через 6 минут
Возможно, на больших n можно использовать то, что операции поворота принадлежат циклической группе С6.
+++++==-
+++==---
и т.д.



Добавлено через 48 минут
п1-2 позволяют ускорить программу примерно на 13%
п.3 ускорит программу, думаю, ~ в 2 раза.

Добавлено через 43 минуты
Вот с костылями:
Кликните здесь для просмотра всего текста
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import matplotlib.pyplot as plt
import numpy as np
import math
from PIL import Image
from math import sin, cos, atan2, radians
 
class turtle:
    def __init__(self):
        self._direction = np.array([1, 0]) # 2D direction vector
        self._position = np.array([0, 0]) # 2D position vector
    def forward(self):
        pos = self._position
        dirn = self._direction
        self._position = np.add(pos, dirn)
    def rotate(self, theta):
        (x, y) = self._direction
        current_angle = atan2(y, x)
        new_angle = current_angle + radians(theta)
        self._direction = [cos(new_angle), sin(new_angle)]
 
def L_system(commands, axiom, production_rules, theta, n_iterations):
    command_string = axiom # Begin commands with only the axiom
    for iteration in range(n_iterations):
        new_command_string = str()
        for char in command_string:
            if char in production_rules:
                new_command_string += production_rules[char]
            else:
                new_command_string += char
        command_string = new_command_string
 
    # удаляем +- и -+
    command_string=command_string.replace('+-','')
    command_string=command_string.replace('-+','')
    n_commands = len(command_string)
 
    t = turtle() # Initialize a turtle at position [0, 0]
 
    positions = np.zeros((n_commands, 2))
 
    for i, command in enumerate(command_string):
        if command in commands:
            exec(commands[command]) # Perform command on turtle
        positions[i, :] = t._position
 
    return positions
 
# Alghoritm for Gosper curve (commands, axiom, rules, number of iterations and angle)
commands = {
    'A': 't.forward()',
    'B': 't.forward()',
    '+': 't.rotate(theta)',
    '-': 't.rotate(-theta)',
    }
axiom = 'A'
production_rules = {
    'A': 'A-B--B+A++AA+B-',
    'B': '+A-BB--B-A++A+B'
    }
theta = 60
 
n_iterations = int(input("Введите Количество итераций: "));
angle = 60#int(input("Введите угол наклона: "));
positions = L_system(commands, axiom, production_rules, theta, n_iterations)
pointX = 100#int(input("Введите точку по оси Х: "));
pointY =100# int(input("Введите точку по оси Y: "));
 
# удаляем повторяющиеся координаты
i, = np.where(np.diff(positions[:,0]) == 0)
positions=np.delete(positions,i, axis=0) 
 
def rotate_origin_only(positions, pointX, pointY, angle):
    x = positions[:, 0] + pointX
    y = positions[:, 1] + pointY
    xx = x * math.cos(angle) + y * math.sin(angle)
    yy = -x * math.sin(angle) + y * math.cos(angle)
    return xx, yy
 
xx, yy = rotate_origin_only (positions, pointX, pointY, angle)
plt.plot(xx, yy)
plt.savefig('out.jpg')
plt.show()
Спасибо за подробный ответ, 1 пункт был в качестве 'костыля', поскольку прямая на первом этапе не рисовалась без наличия знака '+' или '-', а так как мне нужна была именно прямая, сделал такую комбинацию, в угоду производительности можно ее удалить. по 2 пункту получается, что больше нет схожих случаев. 3 пункт действительно интересный, спасибо. А у Вас был какой-то прирост на тестовой версии?
0
5516 / 2869 / 571
Регистрация: 07.11.2019
Сообщений: 4,760
10.04.2020, 10:07
У меня где-то на 15% прирост n=7, но тут понятное дело, костыль: сначала добавляются в positions элементы, потом дублинаты удаляются. Исправьте код, чтобы не добавлялись дубликаты и все.
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
10.04.2020, 13:02
Цитата Сообщение от u235 Посмотреть сообщение
Вы сам алгоритм смотрели?
Фракталы, соответственно, рекурсия. Как это распараллелить?
Почему нет? По направлениям/веткам. Но да алгоритм нужно смотреть и возможно переписывать.
0
5516 / 2869 / 571
Регистрация: 07.11.2019
Сообщений: 4,760
10.04.2020, 13:18
Avazart, у задачи экспоненциальная сложность от n. (по крайней мере в том виде, в каком она решена)
Насколько я понимаю распараллелить эту задачу это приблизительно тоже самое, что и распараллелить нахождение n-го члена последовательности Фибоначчи.
0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
10.04.2020, 13:24
Сложность тут не при чем.Как она влияет на распараллеливание?
У нас необходимо вычислить координаты точек. Просто распараллелить их по направлениям разростания фрактала.
Тут другой нюанс - как нужно рисовать. Ибо рисовать можно только в одном потоке - основном.
0
0 / 0 / 0
Регистрация: 03.06.2015
Сообщений: 34
10.04.2020, 15:35  [ТС]
Цитата Сообщение от Avazart Посмотреть сообщение
Сложность тут не при чем.Как она влияет на распараллеливание?
У нас необходимо вычислить координаты точек. Просто распараллелить их по направлениям разростания фрактала.
Тут другой нюанс - как нужно рисовать. Ибо рисовать можно только в одном потоке - основном.
При запуске ячеек в jupyter notebook, я выяснил, что основное время при построении фрактала в слукчаях n = 7, 8 уходит на вычисление координат.
Python
1
positions = L_system(commands, axiom, production_rules, theta, n_iterations)
Добавлено через 34 минуты
Но если отрисовка идет в одном потоке, то действительно нет смысла в распараллеливании.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
10.04.2020, 15:35
Помогаю со студенческими работами здесь

Имеет ли смысл
Имеет ли смысл, не закончив изучение С, перейти к Object-C? Или те же Указатели/Ссылки/Дин. Массивы изучить в С и после переходить к...

Имеет ли смысл менять?
Доброго времени суток. Вот задался вопросом. Нужно ли менять видеокарту, так как, например, в БФ4 на ультрах уже не могу побегать, но...

Имеет ли смысл обновлять?
Тип ЦП--------------DualCore Intel Core i5-650, 3200 MHz (24 x 133) Системная плата---ECS IC55H-A (2 PCI, 3 PCI-E x1, 1 PCI-E x16, 4...

Имеет ли финансовый смысл?
Имеет ли смысл создание нескольких, ориентированных на адсенс, относительно белых тематических каталогов с аналогичным контентом?

Апгрейд, имеет ли смысл?
Всем привет. У меня довольно старая система на мат плате m68mt-s2 rev 3.1, проц amd athlon II x2, 4гб озу и видео nvidia gt430. Ввиду...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Оттенки серого
Argus19 18.03.2026
Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++
8Observer8 17.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru