Матрица против функции для матричных операций

Question

Поскольку я не мог найти что-либо об этом предмете, я решил задать этот вопрос здесь. Я совершенно новичок, и этот вопрос может быть смешным.

Предположим, у нас есть A(NxN) матрица и вектор столбца (B(Nx1)). У нас также есть функция f(i,j), которая возвращает элемент матрицы A в строке i и столбце j.

Если мы хотим выполнить некоторую матричную операцию, скажем, матричный продукт из A и B, который мы можем использовать: следующее (ниже, C является результатом матричного произведения):

1. с использованием функции f(i,j):

N = 100000


def f(i, j):
    return i + j


for i in range(N):
    for j in range(N):
        s = 0
        for k in range(N):
            s += f(i, k) * B[k]
        C[i] = s

2. Использование матрицы A (NxN) (предположим, что A уже определено и содержит те же элементы, которые возвращает функция f)

N = 100000
for i in range(N):
     for j in range(N):
        s = 0
        for k in range(N):
            s += A[i,k]*B[k]
        C[i] = s

На мой взгляд, преимущество функции в том, что она позволяет избежать сохранения всех значений матрицы, тем самым экономя память.

Мои квестрионы:

• В этом случае, какой самый эффективный способ умножения матриц (с использованием функции или самой матрицы)?

• Есть ли разница в производительности между двумя подходами?

РЕДАКТИРОВАТЬ: Мой вопрос не относится к Python или любой другой конкретный язык.

Answer 1

Честно говоря, нет правильного ответа, поскольку это зависит от того, чем вы готовы пожертвовать, а также от используемого языка. В любом случае, основным отличием будет то, что метод функции займет больше времени, чем матричный метод, а матричный метод займет больше места (очевидно?).

Использование времени для экономии памяти, как правило, не очень хорошая идея, поскольку у нас много памяти и гораздо меньше времени.

Я запустил их в Python с N = 10 и получил Function 0.015623331069946289, Matrix 0.0

N = 100 и получил Function 1.0839078426361084, Matrix 0.8769278526306152

~ В настоящее время работает N = 1000 ~

Что-нибудь большее, и мне придется переключиться на Numpy.

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

import time
n = 1000
def f(i, j):
  return i+j

A = [[i+j  for j in range(n)] for i in range(n)]
B = [i for i in range(n)]
C = [0 for _ in range(n)]

start1 = time.time()
for i in range(n):
  for j in range(n):
    s = 0
    for k in range(n):
      s += f(i, k) * B[k]
    C[i] = s
end1 = time.time()

start2 = time.time()
for i in range(n):
  for j in range(n):
    s = 0
    for k in range(n):
      s += A[i][k]*B[k]
    C[i] = s
end2 = time.time()


print("Function-", end1-start1, ", Matrix-", end2-start2)

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

РЕДАКТИРОВАТЬ: Ран для N = 1000, получил Function 620.2477366924286, Matrix 478.4342918395996

Как видите, чем больше, тем лучше время, которое вы получите с помощью матричного метода

Answer 2

1. Вам не следует беспокоиться о вопросах производительности, пока у вас не возникнут проблемы с производительностью.В 99,99% случаев - любой подход будет работать для вас.Код должен быть сначала читаемым, а затем исполнителем О преждевременной оптимизации

2. В вашем конкретном примере - код с функцией должен быть медленнее (только из-за дополнительного вызова функции)или может иметь одинаковую производительность (если компилятор его встроит).Кстати - см. # 1 - вам не нужно сначала писать и читать читаемый код

3. Если вам действительно нужен исполняющий код - для этого есть несколько библиотек (например, NumPy).Библиотеки обычно работают быстрее.Некоторые подходы могут даже делегировать вычисления на GPU

Также см. производительность умножения матриц