大距离矩阵的内存高效存储

Question

我必须创建一个数据结构来存储一个非常大的二维坐标数组中每个点到每个其他点的距离。对于小数组来说很容易实现，但超过大约 50,000 个点后，我开始遇到内存问题——这并不奇怪，因为我正在创建一个 n x n 矩阵。

这是一个工作正常的简单示例：

import numpy as np
from scipy.spatial import distance 
n = 2000
arr = np.random.rand(n,2)
d = distance.cdist(arr,arr)

cdist速度很快，但由于矩阵是对角线镜像的，因此存储效率低下(例如d[i][j] == d[j][i](。我可以使用np.triu(d)转换为上三角形，但生成的方阵仍然需要相同的内存。我也不需要超过某个截止点的距离，所以这可能会有所帮助。下一步是转换为稀疏矩阵以节省内存：

from scipy import sparse
max_dist = 5
dist = np.array([[0,1,3,6], [1,0,8,7], [3,8,0,4], [6,7,4,0]])
print dist
array([[0, 1, 3, 6],
[1, 0, 8, 7],
[3, 8, 0, 4],
[6, 7, 4, 0]])
dist[dist>=max_dist] = 0
dist = np.triu(dist)
print dist
array([[0, 1, 3, 0],
[0, 0, 0, 0],
[0, 0, 0, 4],
[0, 0, 0, 0]])
sdist = sparse.lil_matrix(dist)
print sdist
(0, 1)        1
(2, 3)        4
(0, 2)        3

问题在于对于一个非常大的数据集，快速到达稀疏矩阵。重申一下，用cdist制作方阵是我所知道的计算点之间距离的最快方法，但中间方阵会耗尽内存。我可以将其分解为更易于管理的行块，但这会减慢很多速度。我觉得我错过了一些明显的简单方法，可以直接从cdist进入稀疏矩阵。

Answer 1

以下是使用KDTree的方法：

>>> import numpy as np
>>> from scipy import sparse
>>> from scipy.spatial import cKDTree as KDTree
>>> 
# mock data
>>> a = np.random.random((50000, 2))
>>> 
# make tree
>>> A = KDTree(a)
>>> 
# list all pairs within 0.05 of each other in 2-norm
# format: (i, j, v) - i, j are indices, v is distance
>>> D = A.sparse_distance_matrix(A, 0.05, p=2.0, output_type='ndarray')
>>> 
# only keep upper triangle
>>> DU = D[D['i'] < D['j']]
>>> 
# make sparse matrix
>>> result = sparse.coo_matrix((DU['v'], (DU['i'], DU['j'])), (50000, 50000))
>>> result
<50000x50000 sparse matrix of type '<class 'numpy.float64'>'
with 9412560 stored elements in COOrdinate format>