python - 具有不同哈希和排序键的有序元组集

Question

我有以下数据结构(带有示例数据):

edgeID (unique key) | timeStep (ordering key,            | value
                    |     can have multiple occurrences) | 
-----------------------------------------------------------------
"edge1"             | 15                                 | 12.1
"edge3"             | 18                                 | 17.32
"edge2"             | 23                                 | 15.1
"edge5"             | 23                                 | 65.6

我希望能够在此结构上高效地执行以下任务:

• 添加一个 timeStep 高于任何其他存储的 timeStep 的新数据条目。如果达到数据条目的 maxNumber(例如 20)，则应删除具有最低 timeStep 的数据条目。
• 合并两个数据集，保持数据条目的 maxNumber(例如 20)最高 timeStemp 条目，同时当然保持每个 edgeID 最多一次(如果一条边有两个条目，则应使用最高的 timeStep 条目)。

如何在 python 中实现这个数据结构？

我试过一种有效的方法:

1. 一个存储数据的字典，一个SortedSet根据排序键存储键:

   data = {}
   dataOrder = SortedSet(key=lambda x: data[x][0])
   maxDataSize = 20
   
   def addData(edgeID, dataTuple):
       if(len(data) >= maxDataSize):
           # remove oldest value
           key = dataOrder.pop(0)
           del data[key]
       # add
       data[edgeID] = dataTuple
       dataOrder.add(edgeID)
   
   addData("edge1", (15, 12.1))
   

   这种方法的缺点是我将 edgeID 存储了两次，而且我总是必须更新这两个数据结构。

我试过一种无效的方法:

1. 只有一个SortedSet存储整个数据并根据排序键排序:

   data = SortedSet(key=lambda x: x[1])
   maxDataSize = 20
   
   def addData(dataTuple):
       if(len(self.data) >= self.maxDataSize):
           # remove oldest value
           data.pop(0)
       # add
       data.add(dataTuple)
   
   addData(("edge1", 15, 12.1))
   

   这个方法不起作用的事实是它让我用不同的 timeSteps 输入相同的 edgeID 两次，因为(我认为)它散列了整个元组而不是只是 edgeID。不幸的是，我无法在 OrderedSet 构造函数中定义哈希函数。这引出了我认为必须有效的第三种方法:

2. 我可以定义一个实现 __hash__() 函数的类，而不是使用元组作为数据条目，它只会返回 edgeID。然后我可以将此类的对象存储在 OrderedSet

中

第三种方法真的是最好的吗？你有什么建议？

Answer 1

你想要的是一个 heapq ，按 timeStep 排序。

查找:https://docs.python.org/2/library/heapq.html

本质上，python 的堆是一个最小堆，因此最小的时间步长将存储在堆的顶部，并且可以在 O(1) 的时间内获取。每次，在将元素输入堆之前，检查它是否有 20 个条目或更多...如果有 >= 20 个条目，heappop 从堆中...这将删除时间戳最少的条目...

您可以将其与另一个字典协调，以便根据您喜欢的特定键更快地获取其他剩余条目