对20GB数据进行排序

Question

对20GB数据进行排序

8

过去我需要处理大文件，大小约为0.1-3GB。并不需要所有“列”，所以将剩余的数据放入RAM中是可以的。现在我需要处理1-20GB的文件，而且随着时间的推移它们可能会变得更大。这完全不同，因为你不能再把数据放入RAM中了。

我的文件包含数百万个“条目”（我发现了一个有3000万个条目的文件）。一个条目包含大约10个“列”：一个字符串（50-1000个Unicode字符）和几个数字。我需要按“列”对数据进行排序并显示出来。对于用户来说，只有前面的条目（1-30%）是相关的，其余的都是低质量数据。

因此，我需要一些关于该如何解决问题的建议。我绝对不想把数据放到数据库中，因为对于非计算机专业人士来说安装和配置很困难。我希望提供一个单体程序。

展示数据并不难。但是排序…在常规PC上（2-6GB RAM）而又不加载数据到RAM中…会花费一些好时光。

我对MMF（内存映射文件）有些了解，但Danny Thorpe的这篇文章表明它可能不太适合：http://dannythorpe.com/2004/03/19/the-hidden-costs-of-memory-mapped-files/ 因此，我考虑只在RAM中加载需要排序的“列”的数据和指向（磁盘文件中）“条目”地址的指针。我对“列”进行排序，然后使用指针找到对应于每个列单元格的“条目”。还原将直接写入磁盘，因此不需要额外的RAM。

PS：我正在寻找适用于Lazarus和Delphi的解决方案，因为Lazarus（实际上是FPC）支持Mac的64位。64位意味着更多的可用RAM=更快的排序。

- Gabriel Moraru

虽然这不是特定于Delphi的，但这里有数十篇与排序大型文本文件相关的帖子。搜索“sort large files”并查看结果；其中有各种技术的链接，例如第一个结果中的链接。正如所述，您的问题范围非常广泛，如果没有示例数据，我不确定是否可以在此处具体回答。 - Ken White

如果你想自己写，我可以从备份 CD 中找出一些旧的归并排序代码，并上传到某个地方。不过这是 DOS 命令行的东西。 - Jan Doggen

@JanDoggen-无论是命令行还是GUI都没关系。反正我需要的是没有图形界面的。已经写好的代码总是受欢迎的。非常感谢。 - Gabriel

1

@KenWhite-这个问题可能是一般性的（很可能StackOverflow上的许多Delphi问题都可以归类为“一般性”），但是像往常一样，Delphi解决方案可能与Java解决方案不同。只需看看manlio的答案，您就会明白我的意思。 - Gabriel

1

糟糕的标签会让不熟悉Delphi的人无法看到您的问题。使用诸如“排序”、“算法”等标签。您没有提到关键字“列”的大小，但是如果它只有10个字节+您仅需要30m条目的前30％，那么只需要对10mb的关键字进行排序；任何现代机器都可以处理。我经常在小型廉价PC上使用Kernighan + Plauger的1976年归并排序来排序5GB文件，这些作业通常只需要几分钟而不是几小时。请注意，“更少或更快的读/写”才是真正使排序变快的原因，因此即使您的RAM很少或算法很差，使用固态硬盘也可以实现快速排序。 - joe snyder

5个回答

5

如果您只需要整个数据的一部分，可以按顺序扫描文件，并仅保留显示所需的条目。例如，假设您只需要100万条中的300条记录。请在文件的前300条记录中进行扫描并将它们排序到内存中。然后，对于每个剩余的记录，请检查它是否低于内存中最低记录，并跳过它。如果高于内存中最低记录，请将其插入到300个记录中的正确位置，并丢弃最低记录。这将使第二低的记录成为最低记录。重复此过程，直到文件结束。

- Uwe Raabe

不错的建议，但是保留20GB数据中多达30%的数据仍然很大，更不用说超过32位内存限制（注意OP中提到了64位）。 - Matt Allwood

@MattAllwood，当然这取决于实际所需的数据，但是由于数据是向用户显示的，我怀疑在100万条目中有30%的数据实际上是可见的。我绝对不想看那些。 - Uwe Raabe

@UweRaabe-关于GUI部分：数据必须呈现给用户，但这并不是问题。我可以使用一个字符串网格并显示大约100行（或适合屏幕的任何内容），并仅为这些100行加载内存中的数据。随着用户滚动，我卸载旧数据并加载新数据。因此，对于可视化，内存占用非常小。 - Gabriel

4

实际上，没有任何排序算法可以快速移动30GB的随机排序数据。

如果您需要多种方式进行排序，则技巧在于根本不移动数据本身，而是为您需要排序的每个列创建一个索引。

我在处理文件时也是这样做的，这些文件长度也达到了数十GB，用户可以对数据进行排序、滚动和搜索，而且他们甚至都没有意识到这是一个庞大的数据集。

- Wouter van Nifterick

有这种实现的任何示例吗？如何获得代表要排序的数据的索引？比如我想按字母顺序排序或按列中字符串长度排序，那么就会有两个不同的排序值：1. 按字母顺序排序，2. 按长度排序。谢谢。 - Merlin W.

1

最简单的形式是一个与数据集中项数相同的数组。该数组是（值，索引）列表。这个索引本身是排序的。基于这个索引，你可以很容易地找到与之匹配的数据。当你需要所有以B开头的项目时，你可以搜索你的排序索引，然后你会发现在哪里可以在磁盘上找到整个元组。如果你需要大量插入和删除操作，你可能想使用链表而不是普通数组。或者，你可以使用数据库来代替自己实现所有这些。对于平均数据库来说，20GB只是小菜一碟。 - Wouter van Nifterick

3

请找到这里一个类，它使用稍微优化的归并排序对文件进行排序。我几年前为了好玩写了它。它使用跳表在内存中进行文件排序。

编辑：该论坛是德语的，您需要注册（免费）。它很安全，但需要一些德语知识。

- alzaimar

你需要免费注册。这是德国最大的Delphi网站，您不会受到邮件或类似骚扰。值得一访，英文问题也会得到回答。您会惊喜地发现那里有许多会说英语的德国人 ;-) - alzaimar

嗯，我写了那个类。有机会把它交给你吗？ - alzaimar

代码是为Delphi 7（或其他非Unicode版本的Delphi）编写的吗？程序（目前）在函数TcsStringSkipList.CompareKeys中崩溃。今晚已经很晚了，我明天会尝试弄清楚它是如何工作以及为什么会崩溃。 - Gabriel

那就解释了。我会尝试升级它。 - Gabriel

2

如果您无法将数据放入主内存中，则需要使用外部排序。通常，这涉及到外部合并排序。逐个在内存中对数据进行排序，并写回磁盘。然后合并这些块。

- David Heffernan

我确信这一定有一个技术名词（和算法）。非常感谢，我会去研究一下的。 - Gabriel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- manlio · Accepted Answer

我认为一种可行的方法是归并排序，这是一种用于在内存有限的情况下对大量固定记录进行排序的优秀算法。

总体思路：

从输入文件中读取N行（该值允许您将行保留在内存中）
对这些行进行排序，并将排序后的行写入文件1
重复上述步骤，以获得文件2中的下一个N行
...
当到达输入文件的结尾时，您现在拥有M个已排序的文件
将这些文件合并成单个文件（您还需要分步执行此操作）

你也可以考虑使用基于嵌入式数据库的解决方案，例如Firebird embedded：它与Delphi/Windows兼容良好，只需在程序文件夹中添加一些DLL即可（我不确定Lazarus/OSX是否适用）。