计算半对称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.]])

很容易......

但是,当Matrix更大且计算成本高时:嵌套for循环是最有效的解决方案吗？

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()

慢...由于我的功能,还是循环？

编辑

继续使用成对数据,所以我回去尝试使用@hpaulj解决方案.我不够了解为什么testUpper()更快？

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

    upper = np.triu_indices_from(BigMatrix)

    BigMatrix[upper] = ExpensiveFunction()

test针对numpy版本从下面对@unutbu 函数进行基准测试:

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需要小于1ms.但是,当func是ExpensiveFunction,填充BigMatrix接管5秒.

所以双人for-loop可能不是瓶颈; ExpensiveFunction是.您可以使用实际代码进行尝试以确保.如果事实证明这ExpensiveFunction是瓶颈,那么你就不需要打扰优化双循环,因为即使你有更快的方式来填充BigMatrix- 即使你可以把时间成本降低到零 - 你会(在上面的情况)只保存最多,890 us而整个程序仍然需要超过5秒.

Answer 2

我建议将“昂贵”的计算应用于矩阵的一半，而不是使用symmetrize()函数使 numpy 数组对称，该函数应该以最小的时间成本

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