python – 使用不同的哈希和排序键的有序元组

概述我有以下数据结构(带有示例数据)： edgeID (unique key) | timeStep (ordering key, | value | can have multiple occurrences) | --------------------------------------------------------- 我有以下数据结构(带有示例数据)：

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中实现这个数据结构？

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

>一个存储数据的字典,一个根据排序键存储密钥的SortedSet：

data = {}dataOrder = SortedSet(key=lambda x: data[x][0])maxDataSize = 20def 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 = 20def 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构造函数中定义哈希函数.这导致我采用我认为必须工作的第三种方法：
>而不是使用元组作为数据条目,我可以定义一个实现__hash __()函数的类,它只返回edgeID.然后我可以在OrderedSet中存储这个类的对象

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

解决方法 你想要的是一个heapq,在timestep上排序.

抬头：https://docs.python.org/2/library/heapq.html

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

您可以使用另一个dict协调它,以便根据您喜欢的特定键快速获取其他剩余条目

总结

以上是内存溢出为你收集整理的python – 使用不同的哈希和排序键的有序元组全部内容，希望文章能够帮你解决python – 使用不同的哈希和排序键的有序元组所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。