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

我有以下数据结构（带有示例数据）：

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

我希望能够在此结构上高效地执行以下任务：
添加一个新的数据条目，其atimeStep高于任何其他存储的timeStep。如果达到数据项（如20）的maxNumber，则应删除timeStep最低的数据项。
合并两个数据集，使数据项的maxNumber保持最高timeStemp项，而每个edgeID项当然最多保持一次（如果一条边有两个项，则应使用最高timeStep项）。
如何在python中实现此数据结构？
我尝试过一种有效的方法：
一个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存储了两次，并且总是必须更新这两个数据结构。
我尝试过一种不起作用的方法：
只有一个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构造函数中定义散列函数这就引出了我认为必须奏效的第三种方法：
我可以定义一个实现__hash__()函数的类，该函数只返回edgeID，而不使用元组作为数据项。然后我可以将这个类的对象存储在OrderedSet
第三种方法真的是最好的吗你有什么建议？

最佳答案

你想要的是一个heapq，按时间步排序。
查找：https://docs.python.org/2/library/heapq.html
实际上，python的堆是一个最小的堆，因此最小的时间步将存储在堆的顶部，并可以在o（1）中获取。
每次，在将元素输入堆之前，检查它是否有20个或更多的条目…如果有>=20个条目，则从堆中heappop…这将删除时间戳最少的条目。。。
您可以将其与另一个dict进行协调，以便基于您喜欢的特定键更快地获取其他剩余条目

timestep

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