加速從2.92M個數據點創建圖形

我在3.0GB CSV文件中有2.92M個數據點，我需要循環兩次以創建一個我想要加載到NetworkX的圖形。按照目前的速度，我需要花幾天的時間來生成這個圖表。我如何加快速度？加速從2.92M個數據點創建圖形

similarity = 8 

graph = {} 
topic_pages = {} 

CSV.foreach("topic_page_node_and_edge.csv") do |row| 
       topic_pages[row[0]] = row[1..-1] 
end 

CSV.open("generate_graph.csv", "wb") do |csv| 
     i = 0 
     topic_pages.each do |row| 
       i+=1 
       row = row.flatten 
       topic_pages_attributes = row[1..-1] 
       graph[row[0]] = [] 
       topic_pages.to_a[i..-1].each do |row2| 
         row2 = row2.flatten 
         topic_pages_attributes2 = row2[1..-1] 
         num_matching_attributes = (topic_pages_attributes2 & topic_pages_attributes).count 
         if num_matching_attributes >= similarity or num_matching_attributes == topic_pages_attributes2.count or num_matching_attributes == topic_pages_attributes.count 
           graph[row[0]].push(row2[0]) 
         end 
       end 
       csv << [row[0], graph[row[0]]].flatten 
     end 
end

來源

2014-09-12 Karan Verma

向我們展示您的代碼？ – 2014-09-12 23:23:15

@theTinMan添加了代碼。謝謝。 – 2014-09-13 00:00:59

您在該機器上有多少RAM？您試圖在內存中保存2.92M個數據點，並且每個點*不是*佔用一個字節。 – 2014-09-13 00:09:43

花費最多的時間用於從磁盤加載數據。將讀取數據並行化爲多個線程/進程，然後創建圖形。

另外，你也可以在不同的機器上創建子圖並稍後將它們合併。

來源

2014-09-13 03:53:35 Deepank

如果磁盤I/O確實是這裏的瓶頸，我看不到創建多個線程來從磁盤讀取會有所幫助。 – wookie919 2014-09-13 04:04:33

@Deepank即使我在內存中讀取圖形。我需要處理屬性2.92M其他節點以確定邊緣是否存在。我在替補席上註明了這一點，大約需要4-5分鐘。請詳細說明我可以如何將問題簡化爲子問題並稍後將其合併。 – 2014-09-13 06:45:36

基準。例如使用Python自帶的cProfile。代碼中存在代價高昂的低效率很容易，而且在密集型應用程序中，它們的性能成本可能會高出10倍。

漂亮的代碼，如
```
(topic_pages_attributes2 & topic_pages_attributes).count 
```
可以變成是在運行時的主要因素，可以很容易地通過使用更傳統的代碼被降低。
使用更高效的語言。例如在benchmarksgame.alioth中，對於一些密集型問題，Python 3程序的速度比最快的C程序慢了63倍（Ruby是67x，33x是JRuby）。是的，性能差距可以是，即使是經過良好優化的Python代碼。但是如果你沒有優化你的代碼，它可能會更大;通過使用更高效的語言並仔細優化代碼，您可以獲得100x-1000x的加速。
考慮更聰明的問題表達方式。例如，不是迭代每個節點，而是遍歷每個邊緣一次。在你的情況下，這可能意味着建立一個倒排索引，主題 - >頁面。這與文本搜索引擎的工作方式非常相似，也是計算集羣上這種操作的流行方式：各個主題可以分散在不同的節點上。這種方法可以從您的數據中的稀缺中受益。這可以大幅減少算法的運行時間。

您有大約3個Mio文檔。從您的總數據量來看，他們平均可能少於100個話題？你的兩兩比較方法需要3mio^2的比較，這是傷害你的東西。如果每個人只有30,000個文檔使用更受歡迎的主題，那麼您可能只計算30k^2 *的主題數量。假設你有100個這樣的熱門話題（罕見的話題無關緊要），這將是100倍加速。
簡化您的問題。例如，第一個合併所有具有的文檔恰好是通過排序相同的主題。爲了使這更有效，還要消除所有隻發生一次的話題。但大概只有一些10.000-100.000不同的套的文件。這一步可以使用排序輕鬆解決，並且會使您的問題更容易900-90000倍（假設值在上述範圍內）。

有些數字可能過於樂觀了 - 例如，IO並沒有考慮到所有的，如果你的問題是I/O綁定，使用C/Java的可能沒有太大的幫助。可能有一些非常受歡迎的話題可能會受到C中討論的方法的傷害。對於D）您需要O（n log n）時間來對數據進行排序;但有很好的實現可用。但這絕對是你應該做的簡化。這些文件也將在您的最終數據中形成完全連接的派系，這也可能會影響其他分析。

來源

2014-09-13 22:15:57

加速從2.92M個數據點創建圖形

回答

相關問題