问题标签 [external-sorting]

我写了一个类似于外部排序的程序。我从这个博客中得到了一个好主意。在这里，他们试图只做外部排序的数字。我的要求有点不同。我的输入文件可能有超过百万条记录，并且很难在内存中对它们进行排序，所以我必须利用我的磁盘。我将我的输入分成不同的部分，对其进行排序，然后将其存储在临时文件中。然后将排序后的输出合并到一个文件中。下面我可以将其拆分为临时文件，然后仅合并密钥。

我有一个输入文件如下：

假设磁盘上文件的大小是 10，内存缓冲区可以容纳的最大项目是 4，所以我所做的是一次获取 4 条记录并将其存储在 HashMap 中，将我的值与更新的计数一起排序。该输入将被拆分为 3 个排序文件，如下所示。您可以看到，对于每个键，我都有一个计数以及词典上的最高值。

临时文件-0.txt

临时文件 1.txt

临时文件 2.txt

然后合并所有这 3 个文件后，输出应如下所示：

我不确定将整行与计数和该键的字典最高值合并的逻辑，我的以下代码能够给我所有键，如下所示：

在下面的代码中，我打开每个文件并合并它们，然后写回磁盘到一个名为external-sorted.txt

任何想法表示赞赏。请询问，如果您有任何问题。TIA。

在研究排序算法时，称为堆排序，用于外部排序。当我们处理外部存储时，我无法弄清楚它在排序技术方面有何不同？或者堆排序唯一被认为对外部排序有用的东西是什么？

有人可以解释一下吗？

我不知道从哪里开始，但这很混乱。基本上我需要为单链表编写一个插入排序方法——这会导致足够的问题，因为通常对于插入排序——你应该向后遍历数组/列表元素——实现单链表似乎毫无意义，因为重点-您只能在列表中前进，除此之外->我需要在外部执行“交换”操作，我不完全了解如何在使用列表结构时执行该操作。

这是我使用的 ArrayClass 和 Swap 方法：

这是我的数组插入排序：

现在我必须以某种方式做同样的事情 - 但是使用单链表，我可以使用这种类（允许进行更改）：

老实说-我不确定我应该如何实现插入排序，也不确定如何将其转换为外部排序。我以前使用此代码不进行外部排序：

因此，如果有人可以提供某种提示/解释 - 或者如果你曾经尝试过这个 - 如何解决此类问题的代码示例，将不胜感激！

我想从文件中读取几个单词。我没有找到任何方法来做到这一点，所以我决定逐个读取 char，但我需要在空格处停下来将读取的单词存储在我的数组中并转到下一个。

我正在制作一个外部排序应用程序，这就是我有内存限制的原因，在这种情况下，我不能只使用readLine()然后split()，我需要控制我阅读的内容。

该read()方法返回一个int，我不知道我可以做什么来read()方法返回一个char并在空格后停止读取。

这是我到目前为止的代码：

编辑1：我使用了扫描仪和next()方法，它有效。Scanner 的初始化位于 Main。

我正在尝试创建一个新的文件目录，但该功能mkdir()不起作用，mkdirs().

这是我的代码：

编辑：我进行了编辑，现在它正在工作！

我最近致力于外部合并排序算法（外部排序）的实现，我的实现需要使用多线程方法。

我尝试使用 ForkJoinPool 而不是使用 Java 中较旧的实现，例如 Thread 和 ExecutorService。该算法的第一步需要读取一个文件，每x行收集并发送以排序并写入文件。此操作（排序和保存）可以在主线程读取下一批时在单独的线程中完成。我已经写了一个方法来做到这一点（见下文）。

我担心的是，实际的并行工作在我使用时并没有开始，ForkJoinPool.commonPool().submit(()->SortAndWriteToFile(lines, fileName))而是只有在我task.join()在循环完成后调用时才开始。这意味着在一个足够大的循环中，我将整理要运行的任务，但没有任何时间运行它们。当我使用它invoke而不是submit它时，我似乎无法控制join意志在哪里，也不能保证在继续之前完成所有工作。

有没有更正确的方法来实现这一点？

我的代码如下。列出了该方法和两个实用方法。我希望这不会太长。

我正在为外部排序编写一个合并排序，它一次从文件 A 中读取 2 块数据，将它们合并成一个更大的块，然后将其写入文件 B。之后，我需要读取其中增加的 2 个从文件 B 一次块，将它们合并为 1 个更大的块，并将其写入文件 A。这种切换一直持续到最后所有数据都计为 1 个块。

我尝试在每次迭代后像这样交换标识符：

这要求我使用新的文件目录名称更新 BufferedInput 和 BufferedOutputStreams 并每次都构造它们。

我的 RAM 数量有限，因此除非必须，否则我无法继续创建新对象。每次迭代是否有更好的方法来切换目标文件和源文件？

我有 2 个类似“数据框”的大型 csv 数据集，每个数据集有 4 列。column1+column2 是键，column4 是我要比较的值。key1 和 key2 相同，可以比较 val，key1 和 key2 可以重复，key1 有大约 1M 的唯一记录，key2 有 4000 条唯一记录。

使用 dataframe 可以很容易，但是当涉及到每个数据集 100GB 时，它无法将所有数据加载到内存中，并且 pandas dataframe 限制了 48GB 的​​对象大小。

我目前有一个程序：

这将导致 5 小时的运行时间。我的问题是获得大约 30 分钟的运行时间有什么合理的想法吗？重新设计程序也是可以接受的。

提前致谢。

我的问题是关于大文件中的数据。

我有一个采用这种格式的大文件 - Primary_key 值（例如：10000001 1 10000002 5 10000009 200 等。我想在 primary_key 列中找到与 k 大元素相对应的值。例如：如果 k=2，它应该按照上面的例子输出 200 和 5 。

由于它是一个非常大的文件，我计划使用最小堆方法，我对此非常了解。但是，我的数据位于键值对中，我不知道如何在最小堆排序中使用它。

关于如何实现这一目标的任何建议。非常感谢您对此的任何帮助。

假设我们有k排序数组（每个大小n），在这种情况下使用优先级堆比传统合并（类似于合并排序中使用的）更好，反之亦然？

优先队列方法：在这种方法中，我们有一个最小堆大小k（最初，每个数组的第一个元素被添加到堆中）。我们现在删除 min 元素（从输入数组之一），将其放入最终数组并从同一个输入数组中插入一个新元素。这种方法需要O(kn log k)时间和O(kn)空间。注意：它占用O(kn)空间，因为这是最终数组的大小，并且在计算渐近空间复杂度时，它决定了堆的大小。

传统合并：在这种方法中，我们合并前 2 个数组以获得大小为的排序数组2n。我们对所有输入数组重复此操作，并且在第一遍之后，我们获得k/2每个大小为的排序数组2n。我们重复这个过程，直到我们得到最终的数组。每次比较都有一个时间复杂度，O(kn)因为每次比较后都会将一个元素添加到相应的输出数组中。我们有 log k 通行证。因此，总时间复杂度为O(kn log k)。而且由于我们可以在每次传递后删除输入数组，因此在任何时候使用的空间都是O(kn).

正如我们所见，两种方法的渐近时间和空间复杂度完全相同。那么，我们究竟什么时候更喜欢其中一个呢？我知道对于外部排序，优先队列方法更好，因为您只需要O(k)内存空间，并且您可以从磁盘读取和写入每个元素。但是当我们有足够的内存时，这些方法如何相互叠加呢？