在 Python 中改进矩阵计算的执行时间

Question

我处理大量数据，这段代码的执行时间非常非常重要。每次迭代的结果都是相互依赖的，所以很难做到并行。如果有更快的方法来实现这段代码的某些部分，那就太棒了，比如：

查找矩阵中的最大元素及其索引
将 row/column 中的值更改为另一个 row/column
删除特定的行和列

填充 weights 矩阵非常快。

代码执行以下操作：

它包含一个单词列表列表 word_list，其中包含 count 个元素。在开始时，每个单词都是一个单独的列表。
它包含浮点值 weights 的二维列表 (count x count)（下三角矩阵，i>=j 的值为零）
在每次迭代中，它执行以下操作：
- 它找到具有最相似值的两个单词（矩阵中的最大元素及其索引）
- 它合并它们的行和列，在每个单元格中保存两者中较大的值
- 它合并了word_list中相应的单词列表。它将两个列表保存在具有较小索引 (max_j) 的列表中，并删除具有较大索引 (max_i) 的列表。
如果最大值小于给定的 THRESHOLD

我可能会想到一个不同的算法来完成这个任务，但我现在还没有想法，如果至少有一个小的性能改进那就太好了。

我尝试使用 NumPy，但它的性能更差。

weights = fill_matrix(count, N, word_list)
while 1:
    # find the max element in the matrix and its indices 
    max_element = 0
    for i in range(count):
        max_e = max(weights[i])
        if max_e > max_element:
            max_element = max_e
            max_i = i
            max_j = weights[i].index(max_e)

    if max_element < THRESHOLD:
        break

    # reset the value of the max element
    weights[max_i][max_j] = 0

    # here it is important that always max_j is less than max i (since it's a lower triangular matrix)
    for j in range(count):
        weights[max_j][j] = max(weights[max_i][j], weights[max_j][j])

    for i in range(count):
        weights[i][max_j] = max(weights[i][max_j], weights[i][max_i])

    # compare the symmetrical elements, set the ones above to 0
    for i in range(count):
        for j in range(count):
            if i <= j:
                if weights[i][j] > weights[j][i]:
                    weights[j][i] = weights[i][j]
                weights[i][j] = 0

    # remove the max_i-th column
    for i in range(len(weights)):
        weights[i].pop(max_i)

    # remove the max_j-th row
    weights.pop(max_i)

    new_list = word_list[max_j]
    new_list += word_list[max_i]
    word_list[max_j] = new_list

    # remove the element that was recently merged into a cluster
    word_list.pop(max_i)
    count -= 1

Answer 1

这取决于你想投入多少工作，但如果你真的关心速度，你应该看看 Cython. The quick start tutorial 给出了一些例子，从 35% 的加速到惊人的 150 倍加速（您需要付出一些额外的努力）。

Answer 2

这可能有帮助：

def max_ij(A):
    t1 = [max(list(enumerate(row)), key=lambda r: r[1]) for row in A]
    t2 = max(list(enumerate(t1)), key=lambda r:r[1][1])
    i, (j, max_) = t2
    return max_, i, j

在 Python 中改进矩阵计算的执行时间

Improving the execution time of matrix calculations in Python

python

optimization

numpy

python-3.x