3

我目前正在为处理城市和桥梁的任务编写代码。我必须在他们受人尊敬的地区打印城市和桥梁，例如：

//unorganized inputs from user given the # of "paths" we need
4       // the # of paths
1 2 5  // 1 = city , 2 = city, 5 = bridge length
6 7 5  // 6 = city , 7 = city, 5 = bridge length
2 3 7  // 2 = city , 3 = city, 7 = bridge length
6 9 7  // 6 = city , 9 = city, 7 = bridge length

运行程序后，排序为：

first district
1 2 5
2 3 7

2nd district
6 7 5
6 9 7

现在，我将通过 cin 读取这些输入。我想将所有可能的路径（例如 1 2 5）存储到一个数组中，然后通过程序对其进行排序和组织。问题是我可能有超过 500,000 条来自用户的路径。我想创建 500k 动态数组。这会导致内存方面的严重问题吗？

我已经研究了解决这个问题的其他可能方法，例如 kruskal 算法和不相交集（我认为是最有用的）。我很难理解不相交集的编码，我想我尝试一种我更熟悉的方式。

任何关于在哪里存储值以及比较和组织它们的帮助都会很棒。链接到我阅读这方面信息的地方会有所帮助。在过去的几天里，我读了很多书。没有多大帮助。

总结一下，我的问题是：

  • 500k 的动态数组会不会在内存方面造成严重的问题？
  • 在给定路径的情况下，在哪里存储值并比较和组织它们？
4

3 回答 3

1

500k 的动态数组会不会在内存方面造成严重的问题？

没问题，假设每个只是一个 3 个整数的数组。通常，您会避免将其作为单独的分配进行，因为它过多——它会有点慢，并且所需的簿记也会消耗相当多的内存。有一个更好的方法：

在给定路径的情况下，在哪里存储值并比较和组织它们？

我将从一个包含这 3 个字段的结构/类开始，然后使用其中的一个std::vector。这会将您的所有值存储为一个连续的分配。相比之下，创建、搜索和分配速度非常快。

于 2012-11-12T06:26:24.347 回答
1

一般来说，假设您的应用程序有 2 gigs 的内存，那么 12 字节的 500K 记录（假设您的值使用 32 位）不会有问题。
如果您希望减少数据集大小，例如，您可以使用如下数据格式： 

struct {
   unsigned short city_a;
   unsigned short city_b; 
   char length;
}


查看城市集的大小（城市数量），以及两个城市之间的最大长度。
此外，索引城市对（AB 变为 Pair_ID）之类的东西也可以减少数据集。

于 2012-11-12T06:27:35.823 回答
1

这可能与您的问题没有直接关系，但我认为您要完成的是 - http://en.wikipedia.org/wiki/Connected_component_(graph_theory )。如果您将图形建模为邻接矩阵，则无需分配 500k 动态数组。考虑以下格式来存储您的数据：

int city_map [MAX_NO_OF_CITIES][MAX_NO_OF_CITIES];

city_map[i][j] = length_of_brigde_connecting_city_i_to_j;

这种方式存储 500,000 个条目只需要 1MB 多一点的内存。

于 2012-11-12T06:57:11.987 回答