问题标签 [external-sorting]

我char*在一个文件中有一个数组。我工作的公司将数据存储在平面文件中。有时数据是排序的，但有时不是。我想对文件中的数据进行排序。

现在我可以从头开始编写代码来做到这一点。有没有更简单的方法？

当然，就地排序将是最好的选择。我正在处理大文件并且内存很小。但我会考虑所有选项。

所有字符串的长度相同。

这是一些示例数据：

这将表示长度为 28 的三个记录。应用程序知道长度。每条记录都以 CRLF ( \r\n) 结尾，尽管这对于这种排序无关紧要。

参考我的最后一个问题（多个子进程），我现在正在尝试使用多个子进程进行外部排序实现。

但当然，由于 fscanf，这段代码会从 inputfile 输出相同的排序整数序列。例如，如果输入文件的开头包含 5 1 4，那么它会输出：

(第一个孩子) 1 4 5
(第二个孩子) 1 4 5

（有两个子进程）.. 因为 fscanf 从输入流的开头开始读取整数。

我现在的问题是如何继续从前一个子进程离开的点开始读取数字？例如，如果输入文件包含 5 1 4 8 5 10，那么它可以输出：

（第 1 个孩子） 1 4 5

(第二个孩子) 5 8 10

提前致谢;）

假设您有一个大型集合，磁盘上有 n 个对象，每个对象都有一个可变大小的字符串。使用纯字符串比较对这些对象进行索引的有效方法的常见做法是什么。从长远来看，由于大小和 I/O 的原因，将整个字符串存储在索引上会令人望而却步，但由于磁盘具有高延迟，因此仅存储引用也不是一个好主意。

我一直在考虑使用类似 B-Tree 的设计和尝试，但找不到使用这种方法的任何数据库实现。事实上，很难找到主要数据库如何为字符串实现索引（它可能会在大量 SQL 级信息的结果中丢失。）

蒂亚！

编辑：将标题从“有效的外部排序和搜索具有大字符串的存储对象”更改为“有效存储字符串的外部索引”。

我有一个文件，它由一行组成：

在此表示中，空格分隔整数和逗号。这个字符串太大了，我无法用 RandomAccessFile.readLine() 读取它（几乎需要 4 Gb）。所以我创建了一个缓冲区，它可以包含 10 个整数。我的任务是对字符串中的所有整数进行排序。

能否请你帮忙？

编辑

@奥斯卡雷耶斯

我需要将一些整数序列写入文件，然后从中读取。其实我不知道，该怎么做。我是新手。所以我决定用chars来写整数，整数之间的分隔符是“，”，序列之间的分隔符是“\n\r”。所以我创建了一个可以读取它的怪物：

如果您能建议如何做，请做=）

我正在写一个外部合并排序。它的工作原理是这样的：从大文件中读取 k 个块，在内存中对它们进行排序，执行 k 路合并，完成。所以我需要在 k-way 合并阶段从文件的不同部分顺序读取。最好的方法是什么：几个 ifstream 或一个 ifstream 和寻找？另外，是否有一个易于异步 IO 的库？

哪一个更好？说 1GB 内存和 100GB 文件进行排序。

10 路合并的一个实例需要： - 100 个 1GB 加载，然后是 10*10 + 10*100 个 100MB 加载（对于 10 路，然后是 10 路合并）

快速排序需要 100*7*2 (nlogn) 1GB 负载？

Java没有实现内置的外部排序算法是否有特定原因？

我正在使用leveldb来存储记录（键值），其中键是 64 位散列，值是双精度。打个比方：认为 64 位散列是客户的唯一 ID，双倍是帐户余额（即他们的帐户中有多少钱）。我想按账户余额对数据库进行排序，并首先列出账户余额最高的客户。但是，数据库无法装入内存，因此我必须使用其他方法对其进行排序，以便按帐户余额进行排序。

我正在考虑使用STXXL，但它要求我将数据库的副本复制到一个平面文件中，然后我可以使用 STXXL 进行外部排序（这会生成一堆较小的文件，对它们进行排序然后合并它们回到另一个平面文件）。有更好的数据排序方法还是我应该使用 STXXL 排序？

这个问题看起来很简单，但我无法理解它背后的真正工作。我知道人们会说，分解成 512 Megs 块并像使用 Map reduce 的 Merge Sort 一样对它们进行排序。

所以这是我的实际问题：

假设我将文件分成 512 Megs 块，然后发送到不同的主机对它们进行排序。假设这些机器使用了归并排序。现在说，我有 2000 台机器，每台机器都分类了 2000、512 兆的块。现在，当我将它们合并回来时，它是如何工作的？尺寸不会继续增加吗？例如，合并两个 512 兆将产生 1024 兆，这是我的 RAM 的大小，那么这将如何工作？任何机器都不能将超过 512 megs 的块与另一个块合并，因为那时大小 > 1 GB。

在合并结束时，我将如何能够将两个 0.5 TB 块与另一个 0.5 TB 块合并.. 虚拟内存的概念在这里发挥作用吗？

我来这里是为了澄清我的基础知识，我希望我能正确地（正确地）问这个非常重要的问题。另外，谁应该做这个合并（排序后）？我的机器还是那 2000 台机器中的几台？

我必须对大量无法放入内存的数据进行排序，而我知道可以做到这一点的一件事是“外部排序”。但我想知道是否可以映射这个大数据文件，并使用'qsort'，因为它是一个'普通数据数组'？如果这是可行的，那么与“外部排序”有什么区别？