Ускорить выполнение кода
Задачка: https://www.codewars.com/kata/57deba2e8a8b8db0a4000ad6/train/python
Вот мой код:
import itertools as it
import numpy as np
def biggest_triang_int(point_list, center, radius):
def distance(arr1, arr2):
# find the distance between 2 points
return np.linalg.norm(np.array(arr1) - np.array(arr2))
def square(triangle):
# find square of triangles with help numpy.cross
a_point = np.array(triangle[0])
b_point = np.array(triangle[1])
c_point = np.array(triangle[2])
vect_1 = (b_point - a_point)
vect_2 = (c_point - a_point)
return np.linalg.norm(np.cross(vect_1, vect_2)) * 0.5
def main():
# main function
# sorting points
p_index = 0
while p_index < len(point_list):
dist = distance(center, point_list[p_index])
if dist < radius: # and abs((dist - radius)/radius) > 10**-10:
p_index += 1
else:
point_list.pop(p_index)
# create list of possible triangles
list_of_triangles = list(it.combinations(point_list, 3))
# find square of triangles and formed the answer
max_square = -float("inf")
for triangle in list_of_triangles:
square_of_triangle = square(triangle)
if square_of_triangle >= max_square:
if square_of_triangle > max_square:
max_square = square_of_triangle
list_of_biggest_triangles = [list(triangle)]
else:
list_of_biggest_triangles.append(list(triangle))
if max_square > 0:
if len(list_of_biggest_triangles) > 1:
return [len(list_of_triangles), max_square, sorted(list_of_biggest_triangles)]
else:
return [len(list_of_triangles), max_square, list_of_biggest_triangles[0]]
else:
return []
return main()
Брут-форсный брут-форс одним словом. Сперва определяет расстояние от каждой точки до центра с помощью numpy и сравнивает с радиусом. Потом создаёт список всевозможных треугольников с помощью itertools. Затем рассчитывает для каждого из треугольников площадь снова с помощью numpy.
Работает слишком медленно. Как можно ускорить?