c - 在 C 中处理大数据集

Question

我有一个超过 400 万行的文本文件。每行给出道路链接的详细信息，即起始节点和结束节点的坐标、节点 ID、链接 ID 等。我将首先从文本文件中将数据提取到两个数据结构中，第一个数据结构将保存链接 ID 和对应的开始和结束节点id。第二个数据结构将保存节点 ID 以及相应节点的 x 和 y 坐标。然后，我将研究这两个数据结构，以查找从给定的起始节点和目标节点开始的路径。

我的 C 技能已经变得有点生疏，我想知道考虑到数据的大小，存储和访问数据的最佳方式是什么。

非常感谢

Answer 1

对我来说听起来没有那么多数据。我会从这样的事情开始:

struct link;
struct node {
    struct link **links;
    int nlinks;
    /* whatever else you need to describe the node. */
};
struct link {
    struct node *n1, *n2;
};

将节点放入树或哈希表或其他在读取文本文件时查找节点的有效方法，对于每一行，分配一个链接，查找开始和结束节点(如果需要则分配)，增长他们的链接数组，将链接插入到数组中。

最坏的情况是，如果每个链接都有两个唯一的节点，那么您的开销是“链接数量”* (2*sizeof(struct node) + 2 * sizeof(struct link *) + sizeof(struct link)) 64 位机器应该有大约 256MB 的数据加上您想要存储的有关节点的任何附加信息，再加上节点查找表的开销。如果您使用内联 avl 树，则树链接需要额外 24 个字节，(64 位)坐标和节点 ID 需要 24 个字节(如果您确实需要它们)，那么您的工作数据量仍然低于半千兆字节与。

如果节点 ID 是连续的，则可以使用更少的内存和一个数据结构，因为您可以将节点放入数组中，而不是链接，只需保存链接另一侧的节点 ID在最坏的情况下，您的文件大小会降至 100MB 以下。