4

Код ниже считает определитель матрицы 20х20 методом миноров и записывает время, которое ему понадобилось для расчета. Но такую большую матрицу он считает очень долго, несколько часов...

import time, random
from random import randint

Ic = [0 for i in range(10)]

def minor(array):
    return array[0][0] * array[1][1] - array[1][0] * array[0][1]

def division(array):
    if len(array[0]) > 2:
        result = 0
        for i in range(len(array[0])):
            new_arr = []
            for j in range(len(array[0])):
                if j != i:
                    new_arr.append([array[j][k] for k in range(1, len(array[0]))])
            result += division(new_arr) * array[i][0] * (-1 + 2 * ((i + 1) % 2))
        return result
    else:
        return minor(array)

N = 20
result = 0
print(f"\nN:\t{N}\n")
timer = time.time()
matrix = [[randint(0, 9) for row in range(N)] for row in range(N)]
print(f"result:\t{division(matrix)}")
for i in range(N):
    print(matrix[i])
print(f"Time:\t{time.time() - timer}")

Как это можно оптимизировать?

2 ответа 2

8

Как это можно оптимизировать?

воспользоваться модулем numpy:

In [32]: import numpy as np   #  pip install numpy

In [33]: a = np.random.rand(20, 20)

In [34]: res = np.linalg.det(a)

In [35]: res
Out[35]: 0.09252260373277807

время работы для матрицы 20x20:

In [36]: %timeit np.linalg.det(a)
27.6 µs ± 37 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
7
  • ну вы прямо серпом по яйцам, взяли и применили готовое решение :( а где элемент творчества?!!! :)
    – Zhihar
    21 окт 2020 в 17:55
  • @Zhihar, дайте пожалуйста знать если в результате применения "элемента творчества" вы найдете решение, которое работает быстрее ;) 21 окт 2020 в 17:56
  • попробовал - приведение определителя к треугольному виду для 20 даёт где-то время 0.0029 :)
    – Zhihar
    21 окт 2020 в 18:12
  • @Zhihar, сравните свое решение с %timeit np.linalg.det(a) на своем железе ;) 21 окт 2020 в 18:16
  • @MaxU, я вас, наверное, где-то не понял, но 36 строка вызывает invalid syntax
    – Listopad02
    21 окт 2020 в 18:19
4

Вычисление определителя через миноры имеет факториальную сложность и непригодно для n>10.

Вместо этого стоит реализовать LU разложение матрицы (кубическая сложность) и затем вычислить определитель как произведение диагональных элементов L и U матриц.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.