Python算法对大块数据进行排序

Question

我一直在网上寻找一种方法来对我拥有的数据类型(LDIF 文件)进行排序，但我还没有找到我想要的东西。已经有程序可以完成这种排序，但它们无法处理非常大的数据集。好吧，对我来说非常大的是这些 block 的值(value)约为 2 GB，这在使用 ldifsort.pl 脚本时会耗尽内存，即使我有 6 GB 可用 RAM 和更多 GB 的交换空间。所以我希望编写一个程序，将数据 block 存储到硬盘驱动器，对内存中的键进行排序，然后按排序顺序重新组合 block 。我想在尝试学习该语言时使用 python3。因此，如果有人对使用 python3 执行此操作的基本策略或具体方法有任何建议，我将非常感谢您的帮助。

我有包含 LDAP 数据的大型文本文件，基本上是(大大简化的)形式:

dn: Subscriber=UniqueName1@domain.com;RestOfTree=node1
groups: 1
permissions: 1
IsActive: FALSE
Barring: TRUE

dn: ProfileID=UniqueName1@domain.com;Subscriber=UniqueName1;RestOfTree=node1
groups: 1
permissions: 1
ServiceProfile: Lemur

dn: Subscriber=UniqueName2@domain.com;RestOfTree=node1
groups: 1
permissions: 1
IsActive: FALSE
Barring: TRUE

dn: ProfileID=UniqueName2@domain.com;Subscriber=UniqueName2;RestOfTree=node1
groups: 1
permissions: 1
ServiceProfile: Lemur

每个订阅者都有另外三个与其关联的 block (我的示例代码仅显示与订阅者关联的另一个 block )，我想在排序完成后将所有四个 block 放在一起。

因此，如果我按此顺序读取 dn(为简洁起见，与 dn 关联的数据被隐藏):

dn: Subscriber=UniqueName2@domain.com;RestOfTree=node
dn: ProfileID=UniqueName2@domain.com;Subscriber=UniqueName2;RestOfTree=node
dn: Subscriber=UniqueName4@domain.com;RestOfTree=node
dn: ProfileID=UniqueName4@domain.com;Subscriber=UniqueName4;RestOfTree=node
dn: Subscriber=UniqueName1@domain.com;RestOfTree=node
dn: Subscriber=UniqueName3@domain.com;RestOfTree=node
dn: ProfileID=UniqueName3@domain.com;Subscriber=UniqueName3;RestOfTree=node
dn: ProfileID=UniqueName1@domain.com;Subscriber=UniqueName1;RestOfTree=node

我希望输出是:

dn: Subscriber=UniqueName1@domain.com;RestOfTree=node
dn: ProfileID=UniqueName1@domain.com;Subscriber=UniqueName1;RestOfTree=node
dn: Subscriber=UniqueName2@domain.com;RestOfTree=node
dn: ProfileID=UniqueName2@domain.com;Subscriber=UniqueName2;RestOfTree=node
dn: Subscriber=UniqueName3@domain.com;RestOfTree=node
dn: ProfileID=UniqueName3@domain.com;Subscriber=UniqueName3;RestOfTree=node
dn: Subscriber=UniqueName4@domain.com;RestOfTree=node
dn: ProfileID=UniqueName4@domain.com;Subscriber=UniqueName4;RestOfTree=node

我的一个想法是使用 sqlite3 在 python 读取数据时存储数据，然后在 python 中对键进行排序，然后使用查询再次从 sqlite 中提取数据并将数据写入文件。但我担心在 sqlite 中搜索键的时间会过多。然后我想我可以在插入数据的同时在sqlite中对数据进行排序，但是sqlite似乎不支持这个，我不知道是否有其他数据库系统支持。

如有任何帮助或指导，我们将不胜感激。

感谢 Zach 建议只使用 GNU 排序而不是数据库系统。这是我在他的帮助下开发的解决方案。

awk -f ldifformatter.awk LDAP 数据文件*.ldif |排序-t\| -k1 | sed '1d;s/|/\n/g' > sorted.txt

其中 ldifformatter.awk 用“|”交换所有换行符除了用于排序的顶级 dn。

谢谢，生锈

Answer 1

你不应该在内存中对你的数据进行排序。你可以使用 merge sort .

Guido van Rossum 写了一篇关于同一问题的文章 — Sorting a million 32-bit integers in 2MB of RAM using Python .文中有代码示例。