Python算法來排序大塊數據

我一直在尋找一種方法來排序我有的數據類型（LDIF文件），但我還沒有找到我以後的相當。已經有程序來完成這種排序，但是它們會以極大的數據集失敗。那麼，對我而言，非常大的值大約是2 GB的這些塊，而且即使我有6 GB的RAM可用和更多的GB交換，在使用ldifsort.pl腳本時也會耗盡內存。所以我希望編寫一個程序，將數據塊存儲到硬盤驅動器，將鍵排序在內存中，然後按照排序順序重新組合塊。我想使用python3，因爲我正在嘗試學習該語言。所以如果任何人有基本的策略或具體的方式來做到這一點python3的建議，我非常感謝幫助。Python算法來排序大塊數據

我有一個包含LDAP數據大的文本文件，基本上是在（多簡化的）形式：

dn: [email protected];RestOfTree=node1 
groups: 1 
permissions: 1 
IsActive: FALSE 
Barring: TRUE 

dn: [email protected];Subscriber=UniqueName1;RestOfTree=node1 
groups: 1 
permissions: 1 
ServiceProfile: Lemur 

dn: [email protected];RestOfTree=node1 
groups: 1 
permissions: 1 
IsActive: FALSE 
Barring: TRUE 

dn: [email protected];Subscriber=UniqueName2;RestOfTree=node1 
groups: 1 
permissions: 1 
ServiceProfile: Lemur

每個用戶具有與它相關聯的三個以上塊（我的示例代碼僅示出了一個其它塊與用戶關聯），並且我想在排序完成後將所有四個塊保持在一起。

所以，如果我讀了這個順序的DN（與DN的相關的數據被隱藏了簡潔）：

dn: [email protected];RestOfTree=node 
dn: [email protected];Subscriber=UniqueName2;RestOfTree=node 
dn: [email protected];RestOfTree=node 
dn: [email protected];Subscriber=UniqueName4;RestOfTree=node 
dn: [email protected];RestOfTree=node 
dn: [email protected];RestOfTree=node 
dn: [email protected];Subscriber=UniqueName3;RestOfTree=node 
dn: [email protected];Subscriber=UniqueName1;RestOfTree=node

我想輸出是：

dn: [email protected];RestOfTree=node 
dn: [email protected];Subscriber=UniqueName1;RestOfTree=node 
dn: [email protected];RestOfTree=node 
dn: [email protected];Subscriber=UniqueName2;RestOfTree=node 
dn: [email protected];RestOfTree=node 
dn: [email protected];Subscriber=UniqueName3;RestOfTree=node 
dn: [email protected];RestOfTree=node 
dn: [email protected];Subscriber=UniqueName4;RestOfTree=node

一個想法我曾經使用sqlite3來存儲數據，因爲python讀取它，然後在python中對鍵進行排序，然後使用查詢從sqlite中再次提取數據並將數據寫入文件。但恐怕在sqlite中搜索密鑰的時間過長了。然後我想我可以在插入數據時在sqlite中對數據進行排序，但似乎sqlite不支持這一點，我不知道是否有另一個數據庫系統。

任何幫助或方向表示讚賞。

感謝Zach提出的僅僅使用GNU排序而不是數據庫系統的建議。這是我在他的幫助下開發的解決方案。

awk -f ldifformatter.awk LDAP-data-files * .ldif | sort -t \ | -k1 | sed'1d; s/|/\ n/g'> sorted.txt

其中ldifformatter.awk用「|」來交換所有換行符。除了用於排序的頂級dn之外。

感謝，生鏽

來源

2013-08-28 Rusty Lemur

如果查找列被索引，SQLite將快速搜索關鍵字。 –

訂單由用戶名稱中的@之前的數字確定？ – Bakuriu

@Bakuriu順序由dn和第一個之間的所有內容決定。該域可以用於排序。 –

命令行實用sort可以不讀他們完全進入內存中的排序非常大的文本文件（至少，GNU版本都可以）。但是，要使用它，您必須重新格式化數據，以便每條記錄（應該保存在一起的所有內容）出現在同一行上。如果記錄看起來是這樣的：

dn: [email protected];RestOfTree=node1|groups: 1|permissions: 1|IsActive: FALSE|Barring: TRUE||dn: [email protected];Subscriber=UniqueName1;RestOfTree=node1|groups: 1|permissions: 1|ServiceProfile: Lemur

然後sort -t \| -k1將做的工作。

您可以用Python編寫一個程序，將數據以適當的格式流入臨時文件，使用subprocess.check_call調用sort，然後恢復原始格式。使用tmpfile.NamedTemporaryFile創建臨時文件。

來源

2013-08-28 15:48:11 zwol

感謝您的建議。我現在正在研究這個。 –

哇。我不知道GNU排序是如此強大。凡ldifsort.pl會因墜毀內存耗盡，這完美地工作：的awk -f ldifsorter.awk數據文件* .ldif | sort -t \ | -k1 | SED '1D; S/|/\ N/G'> sorted.ldif 其中ldifsorter.awk只是重新格式化等你建議的數據。可悲的是沒有使用Python，但這很快。 –

說實話，用'awk'和'sed'你的shell的管道是什麼，如果我有這個問題我自己我都習慣了。我只是建議Python包裝器，因爲你有興趣學習如何用這種語言做事。 – zwol

我不知道是否SQLite是真的不勝任這個任務。但無論如何，您可以使用外部排序算法，例如Mergesort，以保持內存使用率低。

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

來源

2013-08-28 15:47:43 oefe

你不應該在內存中排序你的數據。你可以使用merge sort。

Guido van Rossum寫了一篇關於同樣問題的文章 - Sorting a million 32-bit integers in 2MB of RAM using Python。本文中有代碼示例。

來源

2013-08-28 15:54:05

Python算法來排序大塊數據

回答

相關問題