Skip to main content
 首页 » 编程设计

python之将一个非常大的矩阵从 n^2 x 3 并行化到 n x n

2024年11月24日12Renyi-Fan

我有一个非常大 (100 GB+) 的距离矩阵,其中包含起点、终点和距离列。结构是 n2x3,如下所示:

origin destination distance 
1      2           0.5 
2      3           0.7 
3      4           0.8 
4      5           0.5 
1      3           1.1 

我需要将这个矩阵转换为具有以下形式的 nxn 矩阵:

destination 2    3    4    5 
origin 
1           0.5  1.1  NA   NA 
2           NA   0.7  NA   NA 
3           NA   NA   0.8  NA 
4           NA   NA   NA   0.5 

这里的问题是矩阵的大小。基本上不可能将整个 100 GB 矩阵读入内存以对其进行旋转,因此我一直在寻找对这个过程进行分块和并行化的方法。使用 python,我认为这样的事情可能有效:

chunksize = 10 ** 7 
dtypes = {"origin":np.int, "destination":np.int, "agg_cost":np.float32} 
col_names = ["origin", "destination", "distance"] 
 
def get_chunk(chunk): 
    return chunk.pivot(index='origin', columns='destination', values='agg_cost') 
 
results = pool.map(get_chunk, pd.read_csv("matrix.csv", usecols=col_names, dtype=dtypes, chunksize=chunksize)) 
 
pd.concat(results).to_csv("finished_matrix.csv") 

但这仍然需要大量读入内存。此外,由于 chunksize 没有考虑重复源 ID 的部分开始和停止的位置,因此最终连接结果中存在重复的行索引。

有没有办法有效地并行化此操作,使其可以在正常 (16 GB) 的内存量下运行?

请您参考如下方法:

由于输入文件对于内存来说太大,转换后的输出也将太大。所以我假设目标是生成一个新的输出文件,而不是找出一种方法将所有信息一次保存在内存中(后一个问题可能涉及稀疏矩阵或其他一些技术)。

例如,假设我们从这些数据开始。

1   2   0.5 
3   4   0.8 
5   6   2.7 
2   3   0.7 
1   3   1.1 
3   6   3.1 
4   5   0.5 
1   6   4.6 

首先将输入文件拆分为一堆中间输入文件,每个 ORIGIN 一个。在我们的示例中,我们最终得到 5 个文件。

1   2   0.5 
1   3   1.1 
1   6   4.6 
 
2   3   0.7 
 
3   4   0.8 
3   6   3.1 
 
4   5   0.5 
 
5   6   2.7 

然后使用多个进程将中间输入文件转换为中间输出文件,每个文件都具有新的矩阵结构。以下是基于示例生成的文件。

1   .   0.5   1.1   .     .     4.6 
 
2   .   .     0.7   .     .     . 
 
3   .   .     .     0.8   .     3.1 
 
4   .   .     .     .     0.5   . 
 
5   .   .     .     .     .     2.7 

然后连接中间输出文件以产生最终输出。

上面描述的一般策略可以通过跳过一些中间文件以各种方式优化速度。例如,您可能可以通过执行以下操作来避免拥有一堆中间文件:(A) 创建单个中间输入文件,按 ORIGIN 合并排序; (B) 在这样做的同时,还要跟踪每个 ORIGIN 的文件搜索(开始、结束)位置;然后 (C) 基于合并排序的文件和搜索元数据,使用多个进程来生成最终输出。这种方法可能更快(也可能不会),但它需要更多的簿记工作。我的第一直觉是从简单开始,然后从那里发展。