Алгоритм Python для сортировки больших блоков данных

Question

Я искал в Интернете способ сортировки данных, которые у меня есть (файлы LDIF), но я не нашел того, что мне нужно. Уже есть программы для выполнения этой сортировки, но они терпят неудачу с чрезвычайно большими наборами данных. Что ж, для меня чрезвычайно большой размер этих блоков составляет около 2 ГБ, и это исчерпывает память при использовании сценария ldifsort.pl, даже если у меня доступно 6 ГБ оперативной памяти и еще несколько ГБ подкачки. Поэтому я надеюсь написать программу, которая будет хранить блоки данных на жестком диске, сортировать ключи в памяти, а затем собирать блоки в отсортированном порядке. И я хотел бы использовать python3, поскольку я пытаюсь выучить этот язык. Так что, если у кого-то есть предложения по базовой стратегии или по конкретным способам сделать это с помощью python3, я был бы очень признателен за помощь.

У меня есть большие текстовые файлы, содержащие данные LDAP, в основном в (очень упрощенной) форме:

dn: Subscriber=[e-mail];RestOfTree=node1
groups: 1
permissions: 1
IsActive: FALSE
Barring: TRUE

dn: ProfileID=[e-mail];Subscriber=UniqueName1;RestOfTree=node1
groups: 1
permissions: 1
ServiceProfile: Lemur

dn: Subscriber=[e-mail];RestOfTree=node1
groups: 1
permissions: 1
IsActive: FALSE
Barring: TRUE

dn: ProfileID=[e-mail];Subscriber=UniqueName2;RestOfTree=node1
groups: 1
permissions: 1
ServiceProfile: Lemur

У каждого подписчика есть еще три блока, которые связаны с ним (мой пример кода показывает только один другой блок, связанный с подписчиком), и я хотел бы сохранить все четыре блока вместе после завершения сортировки.

Поэтому, если я читаю днс в следующем порядке (данные, связанные с днс, для краткости скрыты):

dn: Subscriber=[e-mail];RestOfTree=node
dn: ProfileID=[e-mail];Subscriber=UniqueName2;RestOfTree=node
dn: Subscriber=[e-mail];RestOfTree=node
dn: ProfileID=[e-mail];Subscriber=UniqueName4;RestOfTree=node
dn: Subscriber=[e-mail];RestOfTree=node
dn: Subscriber=[e-mail];RestOfTree=node
dn: ProfileID=[e-mail];Subscriber=UniqueName3;RestOfTree=node
dn: ProfileID=[e-mail];Subscriber=UniqueName1;RestOfTree=node

Я хотел бы вывод:

dn: Subscriber=[e-mail];RestOfTree=node
dn: ProfileID=[e-mail];Subscriber=UniqueName1;RestOfTree=node
dn: Subscriber=[e-mail];RestOfTree=node
dn: ProfileID=[e-mail];Subscriber=UniqueName2;RestOfTree=node
dn: Subscriber=[e-mail];RestOfTree=node
dn: ProfileID=[e-mail];Subscriber=UniqueName3;RestOfTree=node
dn: Subscriber=[e-mail];RestOfTree=node
dn: ProfileID=[e-mail];Subscriber=UniqueName4;RestOfTree=node

Одна мысль, которая у меня была, заключалась в том, чтобы использовать sqlite3 для хранения данных, когда python читает их, затем сортировать ключи в python, а затем использовать запросы, чтобы снова извлечь данные из sqlite и записать данные в файл. Но я боюсь, что время, потраченное на поиск ключей в sqlite, будет чрезмерным. Тогда я подумал, что могу сортировать данные в sqlite, пока я вставляю данные, но кажется, что sqlite не поддерживает это, и я не знаю, есть ли другая система баз данных, которая это делает.

Любая помощь или направление приветствуется.

Спасибо Заку за предложение просто использовать сортировку GNU вместо системы баз данных. Вот решение, которое я разработал с его помощью.

awk -f ldifformatter.awk LDAP-данные-файлы *.ldif | сортировать -t \| -k1 | sed '1d;s/|/\n/g' > sorted.txt

где ldifformatter.awk заменяет все символы новой строки на "|" кроме верхнего уровня днс, которые привыкли к сортировке.

Спасибо Расти

Answer 1

Командная строка sort Утилита может сортировать очень большие текстовые файлы, не считывая их полностью в память (по крайней мере, версия GNU может). Однако, чтобы использовать его, вам придется переформатировать данные, чтобы каждая запись (все, что должно храниться вместе) отображалась в одной строке. Если записи выглядят примерно так:

dn: Subscriber=[e-mail];RestOfTree=node1|groups: 1|permissions: 1|IsActive: FALSE|Barring: TRUE||dn: ProfileID=[e-mail];Subscriber=UniqueName1;RestOfTree=node1|groups: 1|permissions: 1|ServiceProfile: Lemur

затем sort -t \| -k1 сделаю работу.

Вы можете написать программу на Python, которая передает данные во временный файл в соответствующем формате, вызывает sort с помощью subprocess.check_call, а затем восстанавливает исходный формат. использование tmpfile.NamedTemporaryFile создать временный файл.

Answer 2

Вы не должны сортировать свои данные в памяти. Вы можете использовать сортировку слиянием.

Гвидо ван Россум (Guido van Rossum) написал статью об этой же проблеме: сортировка миллиона 32-разрядных целых чисел в 2 МБ ОЗУ с использованием Python В этой статье приведены примеры кода.

Answer 3

Интересно, SQLite действительно не подходит для этой задачи. Но в любом случае вы могли бы использовать внешний алгоритм сортировки, например, Mergesort, чтобы сохранить низкое использование памяти.

http://en.wikipedia.org/wiki/External_sorting