问题标签 [external-sorting]

什么是高效稳定的外部排序算法实现（用c编写）？

我正在尝试使用合并排序来实现（在 C 中）用于大学作业的数据库的外部排序算法。可用内存是buffSize块。我发现这个链接很有帮助：

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

但我的问题是关于这行伪代码，在算法的第一阶段：

sort array a using an in-memory algorithm like quicksort

如果我无权使用我的buffSize空间以外的任何内存，所以我无法分配a链接的数组，我如何对包含在这些块中的记录进行排序（然后将它们存储在临时运行文件中） ，使用内存中的排序过程（例如快速排序）。在那种情况下，我的记录不会位于连续数组中，而是位于非连续内存块中，我无法直接应用 qsort。有什么提示吗？

当我们对一个大文件进行外部合并排序时，我们将其拆分为小文件，对它们进行排序，然后将它们合并回一个大的排序文件。

合并时，我们可以进行多次 2 路合并，也可以进行一次多路合并。

我想知道哪种方法更好？为什么？

我再次需要你的帮助！！

我有一个 android 应用程序，可以向外部存储器写入/读取文件。我已经在 AndroidManifest 中编写了所有必需的权限，但我仍然收到拒绝访问的错误。

继承我的代码：

我的 AndroidManifest.xml

拜托，谁能帮忙！！

谢谢

我已经了解外部排序的作用，它的用途；但是我有一个关于合并极端情况的问题。

外部排序 第一个答案解释了外部排序合并的工作原理。但如果：

假设我们有 10 个单位的内存大小，我们想要对 50 个单位的文件进行排序

首先，我们将文件分成 5 个运行（每个运行 10 个单元）并单独排序

其次，我们必须将它们与 4-way merge 合并

和 10/4 = 2.5 ~ 2; 我们从每次运行中取出 2 个单元（块），将它们放入内存并开始合并；

那么实际的问题是：如果（假设）第三次运行的第二和第三块有

比其他运行的第一块更小的元素？合并过程会成功吗？

如果我对我的理解有错误，任何解释都会有所帮助。

原来的问题是这样的：
你要对 1PB 大小的整数进行排序，范围是 -2^31 ~ 2^31 - 1 (int)，你有 1024 台机器，每台机器有 1TB 磁盘空间和 16GB 内存空间。假设磁盘速度为 128MB/s (r/w)，内存速度为 8GB/s (r/w)。CPU时间可以忽略。为简单起见，可以忽略网络传输时间。计算所需的近似时间。

我知道通过外部排序，我们可以在大约 10 小时内对单台机器上的 1TB 数据进行排序，计算如下：

磁盘访问（2r2w）：1T * 4 / 128MB/s = 2 ^ 15 sec ~ 9 hrs
内存访问：
将 2^48 个整数分成 64 个部分（每个 2 ^ 42 个）大约需要 1.3 分钟。所以总共1.4小时。
63 路合并需要几秒钟，因此被忽略。

但是下一步呢：1024T数据的组合呢？我不知道这是如何计算的。那么有什么帮助吗？

如果以前重复过这种情况，我深表歉意，但我找不到任何使用我选择的措辞的帖子。我正在准备面试，并且一直在阅读有关外部排序的信息。例如，如果要对几个 32 位整数的硬盘进行排序，可以进行计数排序，并使用 64 位计数器对 32 位整数进行计数。然后，对于每一个可能的 32 位整数值，您都会有一个计数器来表示它。您还可以对类似的事情使用外部合并排序，花费 O(nlogn) 时间而不是 O(1) 时间。但是，我一直在考虑一个可能很常见的案例，但我想不出最好的方法 - 将新数据添加到可能跨越许多硬盘的一堆排序文件中。

如果内存中有数据，则可以使用堆（优先队列）在登录时间内完成此插入。但是，我们不能从硬盘空间中进行堆。使用列表，您必须使用 O(logn) 搜索来查找数据的位置（对于二进制搜索，已排序），然后将其余数据向后或向前颠簸，或者您可能不必根据实现进行任何移动容器（数组、链表等）。然而，在硬盘世界中，读写比在 RAM 中要昂贵得多，因此在某处插入数据然后转移（重写）其余数据似乎非常昂贵。你们有什么技术可以推荐给我吗？我很乐意阅读自己，我只是找不到正确的方式来表达我的问题以找到任何信息。谢谢！

至少从标题搜索来看，似乎没有任何预先存在的问题。我正在寻找外部合并的最佳通行证数量。因此，如果我们有 1000 个数据块，那么一次将是 1000 路合并。两遍可能是 5 组 200 个块，然后是 1 组 5 个块的最终合并。等等。我做了一些数学运算，这肯定有缺陷，因为看起来两次传球永远不会胜过一次传球。不过，这很可能是对如何读取数据的误解。

首先，一个数值示例：

数据：100 GB
内存：1 GB

由于我们有 1GB 内存，我们可以一次加载 1GB 以使用快速排序或合并排序进行排序。现在我们有 100 个要排序的块。我们可以进行 100 路合并。这是通过制作RAM/(chunks+1)大小桶 = 1024MB/101=来完成的10.14MB。10.14MB100个块中的每一个都有 100 个桶，并且一个输出桶的大小也为10.14MB. 当我们合并时，如果任何输入存储桶为空，我们会执行磁盘搜索以重新填充该存储桶。同样，当输出桶装满时，我们写入磁盘并将其清空。我声称“磁盘需要读取的次数”是(data/ram)*(chunks+1). 我从我们已经确定了输入桶大小的事实中得到了这一点，ram/(chunks+1)我们必须为给定的 pass 读取整个数据，所以我们读取(data/bucket_size)次。换句话说，每次输入桶清空时，我们都必须重新填充它。我们在这里做了 100 多个块，所以numChunks*(chunk_size/bucket_size)=datasize/bucket_size或100*(1024MB/10.14MB). BucketSize = ram/(chunks+1)so 100*(1024/10.14)= (data/ram) * (chunks+1)= 1024*100MB/1024MB * 101= 10100 次读取。

对于两遍系统，我们执行 A 组 B #chunks，然后最终合并 1 组 A #chunks。使用前面的逻辑，我们有 numReads = A*( (data/ram)*(B+1)) + 1*( (data/ram)*(A+1))。我们也有A*B= Data/Ram。例如，10 个组，每组 10 个块，其中每个块是一个 GB。这里，A = 10 B = 10。10*10 = 100/1 = 100，即Data/Ram。这是因为Data/Ram是原始的块数。对于 2 次通过，我们想要Data/Ram分成 A 组 B #chunks。

我将尝试在这里分解公式，让 D = 数据，A = #groups，B = #chunks/group，R = RAM

A*(D/R)*(B+1) + 1*(D/R)*(A+1)- 这是 A 乘以 B #chunks 上的外部合并的读取次数加上 A #chunks 上的最终合并。

(D^2/R^2)*[1 + 2/B] + D/R是 2 次通过外部合并的读取次数。对于 1 遍，我们有(data/ram)*(chunks+1)where chunks = data/ram for 1 pass。因此，对于一次通行证，我们有D^2/R^2 + D/R. 我们看到，只有当块大小 B 变为无穷大时，第 2 遍才达到这一点，即使如此，额外的最终合并也给了我们D^2/R^2 + D/R. 所以一定有一些关于我错过的阅读，或者我的数学有缺陷。感谢任何花时间帮助我的人！

我试图在 C 中实现外部排序。

我最初必须从文件中读取 N 个整数（取决于主内存），以便我可以对它们应用快速排序，然后继续合并过程。

我可以想到这两种方式：

1. 从文件中一个一个地读取 N 个整数并将它们放入一个数组中，然后对它们进行排序。
2. 将大量数据读入一个大字符数组，然后使用 sscanf 从中读取整数。

第一种方法显然很慢，第二种方法使用大量额外内存（但我们的主内存有限）

有没有更好的办法？

该程序基本上从名为 data.bin 的二进制文件中读取大量数据，其中文件中的每个项目都是 1024 字节长。每个项目的前 24 个字节是密钥，其余 1000 个字节只是随机信息。并将所有这些项目添加到一个名为“项目”的数组列表中，然后可以使用合并排序算法对其进行排序。

但是在添加大约 227475 个项目后，我在用 ERROR 注释的行上得到了 OutOfMemoryError。这一切都应该是外部排序的，但它显然不能正常工作。那么我怎么能把大量的项目分成更小的集合进行排序然后合并呢？