ОБЪЯСНЕНИЕ ЧЕМ ДЕЛАЕТ СЦЕНАРИЙ
Я сделал скрипт на Python, цель которого - сбалансировать шарики на круглой доске. Мрамор 1 весит 1 единицу, 2 весит 2 единицы и так далее. Цель состоит в том, чтобы найти наилучший порядок, чтобы он был максимально сбалансированным.
ПРОБЛЕМА
Я также сделал метод, который пробует все возможности с перестановками. Я получаю ошибку памяти, если пытаюсь использовать более 10 шариков (возможно 3628800).
Есть ли способ оптимизировать код с помощью многопоточности / многопроцессорности, может быть, лучше, чем перестановки?
КОД # balance_game.py # Программа, используемая для ваших навыков балансировки шариков на доске
from itertools import permutations
from math import cos, radians, pow, sin, sqrt
from time import time
# Checks if marbles will balance on a circular board
# Marble 1 weighs 1 unit, 2 weighs 2 units, and so on
def test_your_might(NUMBER_OF_MARBLES, marbles):
angle = 360 / NUMBER_OF_MARBLES
angles = [angle * n for n in range(1, NUMBER_OF_MARBLES + 1)]
X = []
Y = []
Fx = []
Fy = []
i = 0
for n in range(0, NUMBER_OF_MARBLES):
angle = radians(angles[i])
X.append(cos(angle))
Y.append(sin(angle))
i += 1
for n in range(0, NUMBER_OF_MARBLES):
Fx.append(X[n] * marbles[n])
for n in range(0, NUMBER_OF_MARBLES):
Fy.append(Y[n] * marbles[n])
return sqrt(pow(sum(Fx), 2) + pow(sum(Fy), 2))
def brute_force_solution(NUMBER_OF_MARBLES):
possibilities = permutations([x for x in range(1, NUMBER_OF_MARBLES + 1)])
solutions = {}
for possibility in possibilities:
possibility = list(possibility)
solution = test_your_might(NUMBER_OF_MARBLES, possibility)
solutions[str(possibility)] = solution
return solutions
# print(test_your_might(5, [5, 1, 4, 3, 2]))
t0 = time()
solutions = brute_force_solution(10)
t1 = time()
best_order = min(solutions, key=solutions.get)
lowest_score = solutions[best_order]
print(f"Lowest score: {lowest_score}\nOrder: {best_order}")
print(f"It took {t1-t0} seconds to find the best possibility")
print(f"There were {len(solutions)} possibilities")
К вашему сведению Метод - brute_force_solution
Поскольку узким местом является загрузка ЦП, многопоточность здесь не очень поможет, но многопроцессорность должна. Не эксперт, но недавно экспериментировал с параллелизмом, поэтому поиграю и обновлю этот ответ, если я где-нибудь доберусь. (Обновлено: я пробовал несколько попыток использовать многопроцессорность, но мне удалось только увеличить время выполнения!)
Возможно, вам нужно сохранить все решения, но если нет, одна небольшая оптимизация с точки зрения времени, но огромная с точки зрения памяти, будет заключаться в том, чтобы не хранить все возможные результаты, а просто сохранить лучший результат, поэтому вы без необходимости создавать еще один очень длинный массив. В идеале вы можете рассчитать количество решений напрямую, поскольку оно зависит только от NUMBER_OF_MARBLES
, но включило его в функцию для согласованности.
def brute_force_solution(NUMBER_OF_MARBLES):
possibilities = permutations([x for x in range(1, NUMBER_OF_MARBLES + 1)])
# count the number of solutions
number_of_solutions = 0
best_solution_so_far = None
for possibility in possibilities:
number_of_solutions += 1
possibility = list(possibility)
solution = test_your_might(NUMBER_OF_MARBLES, possibility)
# If this solution is the best so far, record the score and configuration of marbles.
if (best_solution_so_far is None) or (solution < best_solution_so_far[1]):
best_solution_so_far = (str(possibility), solution)
# Return the best solution and total number of solutions tested.
return (best_solution_so_far, number_of_solutions)
t0 = time()
one_solution = brute_force_solution(11)
t1 = time()
best_order = one_solution[0][0]
best_score = one_solution[0][1]
number_of_solutions = one_solution[1]
На это потребовалось время, но он работал с 11 шариками:
>>>Lowest score: 0.00021084993450850984
>>>Order: [10, 7, 3, 4, 11, 1, 8, 9, 5, 2, 6]
>>>It took 445.57227993011475 seconds to find the best possibility
>>>There were 39916800 possibilities
и был немного быстрее при запуске для 10 (и обратите внимание, что вы не включаете сортировку ваших результатов в свое время, которое не требуется с этим новым методом, и добавляет почти еще одну секунду к вашему времени, чтобы получить лучшее решение):
Старый
Lowest score: 1.608181078507726e-17
Order: [1, 7, 3, 10, 4, 6, 2, 8, 5, 9]
It took 43.81806421279907 seconds to find the best possibility
There were 3628800 possibilities
Новый
Lowest score: 1.608181078507726e-17
Order: [1, 7, 3, 10, 4, 6, 2, 8, 5, 9]
It took 37.06034016609192 seconds to find the best possibility
There were 3628800 possibilities
Можно ли для этого использовать GPU?