algorithm - 在 8GB 以上的文本文件中查找 "key"

Question

我有一些“小”文本文件，其中包含大约 500000 个条目/行。每行还有一个“键”列。我需要在一个大文件(8GB，至少 2.19 亿个条目)中找到这些 key 。找到后，我需要将大文件中的“值”附加到小文件中，在行的末尾作为新列。

大文件是这样的:

KEY                 VALUE
"WP_000000298.1"    "abc"
"WP_000000304.1"    "xyz"
"WP_000000307.1"    "random"
"WP_000000307.1"    "text"
"WP_000000308.1"    "stuff"
"WP_000000400.1"    "stuffy"

简单地说，我需要在大文件中查找'key'。

显然我需要将整个表加载到 RAM 中(但这不是问题，因为我有 32GB 可用空间)。大文件似乎已经排序。我必须检查一下。
问题是我无法使用 TDictionary 之类的东西进行快速查找，因为如您所见，键不是唯一的。

注意:这可能是一次性计算。我将使用该程序一次，然后将其丢弃。因此，它不一定是最佳算法(难以实现)。它只需要在合适的时间内完成(比如 1-2 天)。 PS:我更喜欢在没有数据库的情况下这样做。

我在考虑这个可能的解决方案:TList.BinarySearch .但似乎 TList 仅限于 134,217,727 (MaxInt div 16) 个项目。所以 TList 不会工作。

---

结论:
我选择 Arnaud Bouchez 解决方案。他的 TDynArray 令人印象深刻!如果您需要处理大文件，我完全推荐它。
AlekseyKharlanov 提供了另一个不错的解决方案，但 TDynArray 已经实现。

Answer 1

与其重新发明二进制搜索或 B 树的轮子，不如尝试使用现有的实现。

将内容输入 SQLite3 内存数据库(使用适当的索引，并且每 10,000 次 INSERT 执行一次事务)，您就完成了。确保你的目标是 Win64，以便在 RAM 中有足够的空间。您甚至可以使用基于文件的存储:创建速度有点慢，但有了索引，Key 查询将是即时的。如果您的 Delphi 版本不支持 SQlite3(通过最新的 FireDAC)，您可以使用我们的 OpenSource unit及其 associated documentation .

与常规的客户端-服务器 SQL 数据库相比，使用 SQlite3 无疑会更快，并且使用的资源更少 - 顺便说一句，MS SQL 的“免费”版本无法处理您需要的那么多数据，AFAIR。

更新:我写了一些示例代码来说明如何使用 SQLite3 和我们的 ORM 层来解决您的问题 - 请参阅 this source code file in github .

以下是一些基准信息:

  with index defined before insertion:
    INSERT 1000000 rows in 6.71s
    SELECT 1000000 rows per Key index in 1.15s

  with index created after insertion:
    INSERT 1000000 rows in 2.91s
    CREATE INDEX 1000000 in 1.28s
    SELECT 1000000 rows per Key index in 1.15s

  without the index:
    INSERT 1000000 rows in 2.94s
    SELECT 1000000 rows per Key index in 129.27s

因此对于庞大的数据集，索引是值得的，并且在数据插入之后创建索引可以减少使用的资源!即使插入速度较慢，按键选择时索引的增益也是巨大的。您可能会尝试使用 MS SQL 或使用其他 ORM 来做同样的事情，我想您会哭的。 ;)