用於存儲時間戳數據和在滾動窗口中計算的高效數據結構

我有一個大的Twitter數據流，並且我有興趣分析每條推文中的hashtags的關係。例如，如果哈希標籤A和哈希標籤B出現在同一條推文中，我會將此推文連同推文的時間戳一起記錄爲「A-B」。用於存儲時間戳數據和在滾動窗口中計算的高效數據結構

這樣，樣品輸入是：

hashtags,  Timestamp 
A-B,  created_time: 2016-04-07T01:33:19Z 
B-C,  created_time: 2016-04-07T03:53:19Z 
C,  created_time: 2016-04-08T03:31:19Z 
C-A,  created_time: 2016-04-08T04:33:19Z 
A-D,  created_time: 2016-04-07T07:33:19Z # (Note: an example of out of order) 
B-D,  created_time: 2016-04-09T09:33:19Z

注意，流數據可能不會被時間排序。

任務： 1）使用流數據構建哈希標籤（A，B，C，C ...）及其相互關係的圖形。 2）計算圖形中頂點的平均度數，並在每次出現新的流數據時（在一天的滑動窗口上）更新。

頂點的平均度定義爲：度=邊數/節點數。例如，如果當前圖形是A-B，那麼平均度數= 1（邊緣）/ 2（節點數量）。

樣本輸出：

Output 
1/2, 
2/3, 
1/2, 
1/2, 
2/3, 
1/2

什麼是最有效的Python數據結構來存儲以計算在一天的滾動窗口頂點的平均度這樣一個時間戳數據*

？我的直覺是使用字典來存儲和維護標籤作爲關鍵字，並將created_time作爲值。所以爲了保持一天的窗口，我需要先排序字典，這需要很多時間。有沒有一種更有效的方式來根據時間自動存儲時間戳數據（無需排序）？

我發現使用Pandas DataFrame和滾動功能來完成類似任務的帖子。但在我的情況下，我正在尋找一個最高效的數據結構來完成這項任務。

更新：經過對我的問題的更多研究後，我發現這個問題與我的很好匹配。 Ideal data structure with fast lookup, fast update and easy comparison/sorting

的核心思想是利用[heapq][2]

來源

2016-07-06 enaJ

一旦排序就會消耗這些數據？一個，兩個，多個流程？也許數據庫會是適當的。 –

如果你的所有數據都適用於內存，熊貓是非常有效的 - 但目前還不清楚爲什麼你需要'滾動窗口'功能。你能發佈想要的數據集嗎？ – MaxU

@MaxU，複製和粘貼，排序後，我想計算在一天的時間窗口中的邊緣和節點的平均程度。邊和節點的平均度被定義爲度=總邊數/總節點。這就是我談到滾動窗口功能的原因。 – enaJ

的鳴叫可以預計將大多排序，所以用insertion sort序列類型應該是讓他們有序的好方法。達到24小時後，添加滾動窗口以替換最舊的窗口。

爲了有效插入，您需要一個比list更好的插入支持的序列類型。我會試一試blist。事實上，它提供了一個sortedlist類型，所以你可以嘗試一下，看看它達到了什麼樣的性能。

這一切都假設您的數據流不會增長得太快，無法在內存中保留一整天的tweets。如果是這樣，你會有委託給某種數據庫。

來源

2016-07-06 21:08:38 alexis

你說得對，這個問題應該使用高效的插入排序相關的數據結構來解決。但是在專門搜索可以完成這項工作的所有可能的數據結構後，我覺得python heapq應該是最好的，因爲它可以保持插入，更好地刪除流數據。 – enaJ

然後heapq它應該是。你不會從我這裏得到任何爭論 - 我剛剛提到了一些我聽說過的選項。 – alexis

我會用熊貓。這是一個基於窗口對時間戳進行排序的示例實現。您需要先將數據複製到數據框中。

import datetime 
import dateutil.relativedelta 

days_back = 1 
datetimeFormat = '%Y-%m-%d %H:%M:%S' 
dt_now = datetime.datetime.now() 
start_date = dt_now - dateutil.relativedelta.relativedelta(days=days_back) 
start_date = start_date.strftime(datetimeFormat) 
df2 = df[df['time_stamp'] > start_date]

來源

2016-07-06 21:19:52 sparrow

謝謝。這對於正常的時間序列數據操作可能效果不錯，但是不足以完成流數據。 – enaJ

看不到pd的任何用法？ – slashdottir

謝謝slashdottir我刪除它。熊貓是創建數據框df所必需的。 – sparrow

用於存儲時間戳數據和在滾動窗口中計算的高效數據結構

回答

相關問題