排序的键值对的Python数据结构

我有一组（我已经存储了一个值）的键。我经常查找一个键的值并递增或递减它。典型的字典用法。排序的键值对的Python数据结构

x = {'a': 1, 'b': 4, 'c': 3} 
x['a'] += 1

此外然而，就像经常递增或递减值，我也需要知道第i个最大（或最小）值的关键。当然，我可以做的分类：

s = sorted(x, key=lambda k:(x[k],k)) 
s[1] == 'c'

问题是每次排序似乎相当昂贵。特别是因为我只增加一个项目之间的种类。我觉得我可以使用另一种更适合于此的数据结构。一棵树也许？

来源

2013-10-17 Paul

我不知道在后端效率更高的结构。如果你保存了一个有序的键列表，那么你可以在那里节省几个时钟周期。你只需要在插入时对它进行排序，而不是像你现在有效地做的那样。你只是说'[keyList [i]]'来获取你的数据。 – Hoopdady

https://stackoverflow.com/questions/2298165/pythons-standard-library-is-there-a-module-for-balanced-binary-tree –

您可以使用blist的sorteddict来保持值的顺序。这里有一个快速实现的字典，当遍历，返回其键在其价值观的顺序（没有真正深入测试）的：

import collections 
from blist import sorteddict 

class ValueSortedDict(collections.MutableMapping): 
    def __init__(self, data): 
     self._dict = {} 
     self._sorted = sorteddict() 
     self.update(data) 

    def __getitem__(self, key): 
     return self._dict[key] 

    def __setitem__(self, key, value): 
     # remove old value from sorted dictionary 
     if key in self._dict: 
      self.__delitem__(key) 
     # update structure with new value 
     self._dict[key] = value 
     try: 
      keys = self._sorted[value] 
     except KeyError: 
      self._sorted[value] = set([key]) 
     else: 
      keys.add(key)    

    def __delitem__(self, key): 
     value = self._dict.pop(key) 
     keys = self._sorted[value] 
     keys.remove(key) 
     if not keys: 
      del self._sorted[value] 

    def __iter__(self): 
     for value, keys in self._sorted.items(): 
      for key in keys: 
       yield key 

    def __len__(self): 
     return len(self._dict) 

x = ValueSortedDict(dict(a=1, b=4, c=3)) 
x['a'] += 1 
print list(x.items()) 
x['a'] += 10 
print list(x.items()) 
x['d'] = 4 
print list(x.items())

这给：

[('a', 2), ('c', 3), ('b', 4)] 
[('c', 3), ('b', 4), ('a', 12)] 
[('c', 3), ('b', 4), ('d', 4), ('a', 12)]

来源

2013-10-17 15:43:01

这看起来棒极了，如果我把它做对了，__setitem__大概需要O（log（n））。根据排序后的值寻找第i个键只需要遍历整个sorteddict，看起来比O（n log（n））全部排序的复杂性，谢谢！ – Paul

不客气，同时我意识到，对于您特殊的用例，可能会有更明显的进一步优化，而不是删除一个项目然后重新插入更新，需要重新搜索btree，事实上你事先知道self._sorted中的一个项目最多只能移动一个位置（或者保持在原来的位置），你可以通过滚动你自己的特殊cased sorteddict来优化它的关键是整数只能递增和递减，每次更新可节省一次搜索。 –

也许我很密集，但为什么除了'blist.sorteddict'之外，还需要维护一个单独的Python'dict'？ '排序eddict'已经处理了一切？ –

使用运营商：

import operator 

max(x.iteritems(), key=operator.itemgetter(1))[0]

从文档：

operator.itemgetter（*项目）

返回一个可调用对象，使用操作数的的GetItem从操作获取项目（）方法。如果指定了多个项目，则将返回查找值的元组。例如：

我不知道如果这是最好的解决方案，但它的工作原理。

来源

2013-10-17 14:49:41

为什么不使用Counter从collections？然后，您可以使用Counter.most_common()获取排序列表。

>>> from collections import Counter 
>>> x = Counter({'a': 1, 'b': 4, 'c': 3}) 
>>> x['a'] += 1 
>>> x.most_common() 
[('b', 4), ('c', 3), ('a', 2)]

来源

2013-10-17 14:50:32 grim

这将正是我需要的。然而，读取源代码时，'most_common'只是调用'sorted'，这违背了整个目的。 :( – Paul

您可以使用OrderDict从collections。虽然它在旧的python版本中不可用。

from collections import OrderedDict

如果你已经安装的Django可以使用django.utils.datastructures.SortedDict

来源

2013-10-17 15:53:16 Nik

'OrderedDict'只维护广告订单，所以不适合OP的情况（他需要按值排序）。 –

任何方式排序都没有问题。重要的是，该订单已保存。 – Nik

你读过这个问题了吗？他需要能够找到第i个最大的价值。要用OrderedDict来做到这一点，他需要搜索所有的值，或者他必须先按值排序，这是他试图避免的。 –

我想大多数蟒蛇结构会做类似你已经在你的例子做了什么事。我唯一能想到的更有效的方法是保存你的密钥的有序列表。这样，每次插入时只需进行排序。在你的方法中，每次你想通过索引访问一个值时，你必须进行排序。这里是一个例子：

x = {'a': 1, 'b': 4, 'c': 3} 
x['a'] += 1 

keyList = sorted(x.keys()) 

print x[keyList[1]] 
4 

x['e'] = 7 
x['j'] = 11 
x['d'] = 6 
x['h'] = 8 

keyList = sorted(x.keys()) 

print x[keyList[3]] 
6 
print x[keyList[4]] 
7

希望有所帮助。

来源

2013-10-17 18:19:24 Hoopdady

排序的键值对的Python数据结构

回答

相关问题