-3

我有两个文件：

一个文件存储 10GB 的名称“mapping.txt”：

1 "First string"
2 "Second string"
3 "Third string"
...
199000000 "199000000th string"

另一个文件以任意顺序存储来自 mapping.txt 的整数（存储在 file.txt 中）：

88 76 23  1  5 7 9 10 78 12 99  12  15  16 77  89  90  51

现在我想按照上面整数指定的顺序对“mapping.txt”进行排序，例如：

88 "88th string"
76 "76th string"
23 "23rd string"
1  "1st string"
5  "5th string"
7  "7th string"

如何使用 C++ 完成此任务？

我知道对于文件中的每个整数，都可以在“mapping.txt”中执行二进制搜索，但由于它的时间复杂度为O(n log n)，因此对于大文件来说效率不是很高。

我想要一种比0(n log n).

4

6 回答 6

4

这就是我要做的。这可能不是最有效的方法，但我想不出更好的方法。

首先，您将大文件传递一次以建立每行开始的偏移量的索引。如果您的行足够长，该索引应该适合内存。

然后你传递小文件，读取每个索引，跳转到大文件中的相应位置，并将该行复制到目标文件。

因为您的索引是连续的并且由整数索引，所以查找是恒定的时间。不过，无论如何，任何内存中的查找时间都将完全被磁盘寻道时间所掩盖。

于 2013-06-10T13:12:38.290 回答
2

我知道对于 file.txt 中的每个整数，都可以在“mapping.txt”中执行二进制搜索

正如你所说的二进制搜索在这里没有用，除了你暴露的原因之外，你还面临着 mapping.txt 不是一种友好的格式来执行搜索或索引的挑战。

如果可能的话，我建议将映射文件的格式更改为更适合直接查找调用的格式。例如，您可以在包含固定长度字符串的文件中思考，这样您就可以计算每个条目的位置（这在 fseek 调用的数量中是恒定的，但请记住，函数本身不会是恒定的）

[编辑]：

您可以采取的其他措施来最大限度地减少对 mapping.txt 的访问：

  • 将“订单”文件加载到内存中的数组中，但位置是 mapping.txt 上的实际行，元素是新文件上的所需位置，例如该数组的第一个元素是 4，因为1 位于第 4 位（在您的示例中）。
  • 为方便起见，将新数组拆分为 N 个存储桶文件，因此如果一个元素到达第 200 个位置，则该位置将是第 4 个存储桶上的第一个位置（例如）。
  • 现在您可以按顺序访问映射文件，您将在阵列上的每一行检查新文件中的实际位置，然后将其放入相应的存储桶中。
  • 一旦您传递了整个映射文件（您只需检查一次），您只需将 N 个存储桶附加到您想要的文件中。
于 2013-06-10T13:32:20.080 回答
2

正如塞巴斯蒂安建议的那样，尝试

  1. 使用文件中每个字符串的偏移量（和可选长度）在映射文件（“mapping.txt”）上创建索引。
  2. 然后访问排序文件（“file.txt”）中每个条目的索引并查找文本文件中存储的位置。

这具有取决于两个文件的大小的线性时间复杂度和取决于“mapping.txt”的行数的小因素的线性空间复杂度

要对大型常规文件进行快速且内存高效的顺序读取访问，请使用Windows API 中的mmap(2)和madvise(2)/或它们相应的构造。如果文件大于您的地址空间，请将其映射为尽可能大的块。不要忘记在第 2 步（随机与顺序）中对内核进行不同的访问模式。

如果您以后不需要它并且您的系统有内存映射，请不要从文件中复制那么多东西到堆上！

于 2013-06-10T13:15:22.957 回答
1

鉴于您有一个确切的数据输出列表，我会尝试一个数组

于 2013-06-10T13:03:44.333 回答
1

最好将这个问题分解成更小的问题：

  • 将 mapping.txt 和 file.txt 分别拆分为n和m条目块（n并且m可以是相同的大小或不同的）
  • 使用您的普通地图排序例程并对其进行修改以获取一个块编号（该块是m您正在操作的 file.txt 的 -offset），并对来自各种 mapping.txt 块的那些索引执行地图排序。
  • 完成后，您将拥有moutput-X.txt 文件，您可以将其合并到您的实际输出文件中。

由于您的数据是 ASCII，将固定窗口映射到任一文件将是一件痛苦的事情，因此将两者拆分为较小的文件将很有帮助。

于 2013-06-10T13:15:37.270 回答
1

这是合并排序的一个很好的候选者。这将是 O(n log n)，但大多数算法都不会超过它。您只需要使用索引文件来更改键比较。您会在任何体面的算法教科书中找到合并排序，并且对磁盘进行外部排序是很好的排序，因为当要排序的文件大于内存时。

如果您真的必须击败 O(n log n)，请传递文件并构建一个哈希表，由键索引，每行所在的位置。然后读取索引文件并使用哈希表来定位每一行。理论上，这将是 O(n + 大常数)。但是，我看到了一些问题：n 是什么？那将是一个很大的哈希表。由于“大常数”非常大，实现可能比 O(n log n) 解决方案慢得多。即使您将文件映射为有效访问，您也可能会获得大量分页。

于 2013-06-10T13:17:19.317 回答