python - 用于存储时间戳数据并在滚动窗口中计算的高效数据结构

Question

我有一个很大的 Twitter 数据流，我有兴趣分析每条推文中主题标签的关系。例如，如果标签 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]

Answer 1

可以预计推文大部分是排序的，因此序列类型为 insertion sort应该是让他们订购的好方法。达到 24 小时后，添加滚动窗口以替换最旧的窗口。

为了高效插入，您需要一种比 list 具有更好插入支持的序列类型。我会给 blist一试。事实上，它提供了一个 sortedlist 类型，因此您可以尝试一下，看看它实现了什么样的性能。

这一切都假设您的流不会增长得太快以致无法将一整天的推文保存在内存中。如果是这样，您将必须委托(delegate)给某种数据库。