Лучший способ вычисления половины симметричной матрицы numpy?

Question

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

num_cases = len(case_dictionary.keys()) # num_cases = 10 
SmallMatrix = np.zeros((num_cases,num_cases)) 

for CasesX in range(0,num_cases): 
    for CasesY in range(CasesX,num_cases): 
     SmallMatrix[CasesX,CasesY] = 1 

возвращается:

array([[ 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.], 
     [ 0., 1., 1., 1., 1., 1., 1., 1., 1., 1.], 
     [ 0., 0., 1., 1., 1., 1., 1., 1., 1., 1.], 
     [ 0., 0., 0., 1., 1., 1., 1., 1., 1., 1.], 
     [ 0., 0., 0., 0., 1., 1., 1., 1., 1., 1.], 
     [ 0., 0., 0., 0., 0., 1., 1., 1., 1., 1.], 
     [ 0., 0., 0., 0., 0., 0., 1., 1., 1., 1.], 
     [ 0., 0., 0., 0., 0., 0., 0., 1., 1., 1.], 
     [ 0., 0., 0., 0., 0., 0., 0., 0., 1., 1.], 
     [ 0., 0., 0., 0., 0., 0., 0., 0., 0., 1.]]) 

достаточно легко ...

Однако, когда матрица больше и вычисление дорого: ли вложенная цикл наиболее эффективным решением?

num_cases = len(case_dictionary.keys()) # 100000 
BigMatrix = np.zeros((num_cases,num_cases)) 

for CasesX in range(0,num_cases): 
    for CasesY in range(CasesX,num_cases): 
     BigMatrix[CasesX,CasesY] = ExpensiveFunction() 

медленный ... из-за моей функции или цикла?

EDIT

Непрерывно работает с парными данными, поэтому я вернулся и пытался работать с @hpaulj раствором. Я недостаточно осведомлен, чтобы понять, почему testUpper() быстрее?

def testUpper(func): 
    num_cases = 100 
    BigMatrix = np.zeros((num_cases,num_cases)) 

    upper = np.triu_indices_from(BigMatrix) 

    BigMatrix[upper] = ExpensiveFunction() 

протестированные @unutbu test функции снизу, против Numpy версии:

In [8]: %timeit test(ExpensiveFunction) 
     1 loops, best of 3: 11.1 s per loop 

In [9]: %timeit testUpper(ExpensiveFunction) 
     1000 loops, best of 3: 2.03 ms per loop 

Answer 1

Вот простой эксперимент, который показывает, что горлышко бутылки, скорее всего, будет ExpensiveFunction:

import time 

def SimpleFunction(): 
    return 1 

def ExpensiveFunction(): 
    time.sleep(0.001) 
    return 1 

def test(func): 
    num_cases = 100 
    BigMatrix = np.zeros((num_cases,num_cases)) 

    for CasesX in range(0,num_cases): 
     for CasesY in range(CasesX,num_cases): 
      BigMatrix[CasesX,CasesY] = func() 

---

In [84]: %timeit test(ExpensiveFunction) 
1 loops, best of 3: 5.48 s per loop 

In [85]: %timeit test(SimpleFunction) 
1000 loops, best of 3: 890 µs per loop 

Два цикла timeit одинаковы, за исключением вызываемой функции. Когда func является SimpleFunction, заполняется BigMatrix занимает менее 1 мс. Но когда func является ExpensiveFunction, заселение BigMatrix занимает 5 секунд.

Таким образом, двойной for-loop, вероятно, не является горлом бутылки; ExpensiveFunction есть. Вы можете попробовать его с помощью своего фактического кода, чтобы убедиться. Если окажется, что ExpensiveFunction является узким местом, вам не нужно беспокоиться о оптимизации двойной петли, так как даже если есть более быстрый способ заполнить BigMatrix - даже если вы можете сократить стоимость времени до нуля - вы бы (в приведенном выше случае) сохранить только самое большее 890 us, в то время как общая программа все равно займет 5 секунд.

Answer 2

Я хотел бы предложить, чтобы применить «дорогой» вычисления на половину вашей матрицы и чем сделать свой NumPy массив симметричным, используя symmetrize() функцию, которая должна быть с минимальным временем цене

def symmetrize(a): 
    return a + a.T - numpy.diag(a.diagonal())