python - 如何使用 NumPy 在 Python 中快速填充 100000x100000 矩阵？

Question

我真的很喜欢数据结构和算法。

我正在使用 80000 X 80000 矩阵插入数据。我正在使用 NumPy 。而且，我的代码如下所示:

n = 80000
similarity = np.zeros((n, n), dtype='int8')
for i, photo_i in enumerate(photos):
    for j, photo_j in enumerate(photos[i:]):
       similarity[i, j] = score(photo_i, photo_j)
    if i % 100 == 0:
        print(i)

这段代码花费了太多时间。 score 函数是 O(1)。我想知道是否有更好的方法来做到这一点。我想在可能的“短时间内”绘制这个矩阵的数据。但是，我这样做的方式具有 O(n^2) 的复杂性。

是否有“任何东西”可以“优化”或可能通过使用不同的数据结构？

我已经阅读过关于 SO 的类似问题，他们提到了 pytables。我一定会尝试，但还不知道如何。欢迎提出任何建议。

提前致谢。

Answer 1

您可以做很多不同的事情，所有这些都围绕着避免显式 for 循环，这在 Python 中很慢，并委托(delegate)给 C 级代码(使用 Python 的底层 C 运行时或 numpy 的内置数组创建方法).

使用fromfunction

Numpy 有一个内置函数，用于从采用坐标的函数填充矩阵:numpy.fromfunction .这可能会更快，因为它在 C 而不是 Python 中完成所有迭代和赋值。

您必须为其提供一个按坐标计分的函数，例如:

def similarity_value(i, j, photos=photos):
  return score(photos[i], photos[j])

similarity = numpy.fromfunction(similarity_value, (n, n), dtype='int8')

函数定义中的 photos=photos 使 photos 数组成为函数的局部变量，从而节省了每次调用时访问它的时间；这是一种常见的 Python 微优化技术。

请注意，这会计算整个矩阵的相似度，而不仅仅是一个三角形。要解决此问题，您可以这样做:

def similarity_value(i, j, photos=photos):
  return score(photos[i], photos[j]) if i < j else 0

similarity = numpy.fromfunction(similarity_value, (n, n), dtype='int8')
similarity += similarity.T  # fill in other triangle from transposed matrix

使用理解

您还可以尝试从生成器推导(甚至列表推导)创建相似度矩阵，再次避免显式 for 循环以支持更快的推导，但牺牲三角形优化:

similarity = numpy.fromiter((score(photo_i, photo_j) 
                             for photo_i in photos 
                             for photo_j in photos),
                            shape=(n,n), dtype='int8')

# or:
similarity = numpy.array([score(photo_i, photo_j) 
                          for photo_i in photos 
                          for photo_j in photos],
                         shape=(n,n), dtype='int8')

要重新引入三角形优化，您可以这样做:

similarity = numpy.array([score(photo_i, photo_j) if i < j else 0
                          for i, photo_i in enumerate(photos)
                          for j, photo_j in enumerate(photos)],
                         shape=(n,n), dtype='int8')
similarity += similarity.T

使用triu_indices直接填充三角形

最后，您可以使用 numpy.triu_indices 直接赋值给矩阵的上三角(然后是下三角):

similarity_values = (score(photo_i, photo_j
                     for photo_i in photos
                     for photo_j in photos[:i])  # only computing values for the triangle
similarity = np.zeroes((n,n), dtype='int8')
xs, ys = np.triu_indices(n, 1)
similarity[xs, ys] = similarity_values
similarity[ys, xs] = similarity_values
similarity[np.diag_indices(n)] = 1  # assuming score(x, x) == 1

这种方法的灵感来自于这个相关问题:https://codereview.stackexchange.com/questions/107094/create-symmetrical-matrix-from-list-of-values

我没有办法对这些方法中哪一种最有效进行基准测试，但您可以进行试验并找出答案。祝你好运!