如何在不耗尽内存的情况下存储称重图的信息？

Question

所以我有一个城市和道路的任务。城市之间的每条路都有它的价格。有很多城市，其中一些城市与价格不同的道路相连。我该如何存储这些信息？信息从文件中读取，然后放入二维数组中.数字{0}和数字{1}包含两个连接城市的数目，而数字{2}是道路的价格。这个数组的指数是城市的数量，指数下面的数字是价格。

int[,] graph = new int[cities, cities];
for (int i = 0; i < roads; i++)
        {
            numbers = ReadFromFile(input);
            graph[numbers[0] - 1, numbers[1] - 1] = numbers[2];
            graph[numbers[1] - 1, numbers[0] - 1] = numbers[2];
        }

它很有效，但是它必须通过的测试中有很大一部分是失败的。原因是，在某一时刻，它必须为5000个城市存储5000 * 5000的值，而且内存不足。我该怎么做才能避免这一切？我考虑了其他的选择，但没有什么比这个更好的了。快照

Answer 1

在做任何其他事情之前，尝试将项目转换为在x64体系结构中工作，而不是“任何CPU”或"Win32“。这可能会使一些内存问题简单地消失。

理想情况下，您应该使用“稀疏数组”或“稀疏矩阵”。网络上有一些项目，但它们可能很难处理。其次，最好是使用字典和二维数组来模拟稀疏数组，而不是大矩阵。

字典以Tuple<int, int>作为键(两个it是一个单元格的坐标)和道路价格作为值(如果只有一条道路可以连接两个城市，那么值就是int，对于两个城市之间的多条道路，它是List<int>)。

使用二维数组在字典中查找非空单元格。每个坐标都有一个数组，大小都是5000，它们包含一个List<int>列表，在另一个轴上有非空单元格。根据搜索算法的不同，您可能只需要一个这样的数组，例如x轴(另一个不需要y轴)。

Answer 2

假设每个城市通过3条或更少的不同道路连接到每一座城市。对于每条道路，您需要存储3个项(源、目的地和成本)，假设一个项需要4个字节的存储。

5000 * 5000 *3*4=3* 10^8

这是300兆字节的存储空间。

任何现代计算机都应该没有问题来存储这个内存--现在的内存通常是以千兆字节来测量的。

你的电脑出问题了！