numpy 如何快速填充100,000 x 100,000矩阵?

pwuypxnk  于 2023-10-19  发布在  其他
关注(0)|答案(1)|浏览(124)

在一个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)。我想尝试一下PyTables,但不知道怎么做。

syqv5f0l

syqv5f0l1#

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

使用fromfunction

Numpy有一个内置函数,用于从一个获取坐标的函数填充矩阵:numpy.fromfunction。这可能会更快,因为它在C中而不是Python中完成所有的迭代和赋值。
你必须提供一个score-by-coordinates函数,例如:

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
我没有一种方法来衡量这些方法中哪一种效果最好,但是你可以实验并找出答案。祝你好运!

相关问题