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

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。如果达到数据条目数（例如20），则应删除maxNumber最低的数据条目。timeStep
• 合并两个数据集，保留maxNumber数据条目（例如 20）个最高timeStemp条目，同时当然edgeID最多保留每个条目一次（如果一条边有两个条目，则应使用最高timeStep条目）。

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

我尝试过一种有效的方法：

1. 一个 dict 存储数据，一个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两次并且总是必须更新这两个数据结构。

我尝试过一种不起作用的方法：

2. 只有一个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))
   

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

3. 我可以定义一个类来实现__hash__()仅返回edgeID. 然后我可以将此类的对象存储在OrderedSet

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

Answer 1

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

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

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

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