Python的值排序字典 [英] Value-sorted dict for Python?
问题描述
我感兴趣的是为Python提供了一个迭代接口来排序值的 dict 实现。即， dict 与 sortedvalues（）功能。
I am interested in a dict implementation for Python that provides an iterating interface to sorted values. I.e., a dict with a "sortedvalues()" function.
可以做到 sorted（dict.values（）），但这不是我想要的。每次都插入或删除项目时，必须运行一个完整的排序效率不高的。
Naively one can do sorted(dict.values()) but that's not what I want. Every time items are inserted or deleted, one has to run a full sorting which isn't efficient.
请注意，我不是询问关键字排序的字符串（for那个问题，在 python中的键序命令和
Note that I am not asking about key-sorted dict either (for that question, there are excellent answers in Key-ordered dict in python and Python 2.6 TreeMap/SortedDictionary?).
推荐答案
问题在于，您需要对其进行排序（问题/ 6886294> Python 2.6 TreeMap / SortedDictionary？或者通过键哈希来获得合理的插入和查找性能。实现它的天真的方法将是条目的值排序树结构，以及用于查找密钥的树位置的dict。您需要深入更新树，因为这个查找字典需要保持正确。实际上，正如你对可更新的堆一样。
The problem is that you need to sort or hash it by keys to get reasonable insert and lookup performance. A naive way of implementing it would be a value-sorted tree structure of entries, and a dict to lookup the tree position for a key. You need to get deep into updating the tree though, as this lookup dictionary needs to be kept correct. Essentially, as you would do for an updatable heap.
我认为有太多的选择可以使这种结构的共同的标准库选项，而它也是很少需要。
I figure there are too many options to make a resonable standard library option out of such a structure, while it is too rarely needed.
更新：一个可能适用于您的技巧是使用双重结构：
Update: a trick that might work for you is to use a dual structure:
-
常规
dict按常规存储键值对
任何类型的排序列表，例如使用 bisect
any kind of sorted list, for example using bisect
然后，您必须在两者上执行常用操作：将两个结构中插入一个新值。更棘手的部分是更新和删除操作。您使用第一个结构来查找旧值，从第二个结构中删除旧值，然后（更新时）重新插入。
Then you have to implement the common operations on both: a new value is inserted into both structures. The tricky part are the update and delete operations. You use the first structure to look up the old value, delete the old value from the second structure, then (when updating) reinsert as before.
如果您需要知道钥匙也可以在b列表中存储（值，键）对。
If you need to know the keys too, store (value, key) pairs in your b list.
更新2 ：尝试此类：
import bisect
class dictvs(dict):
def __init__(self):
self._list = []
def __setitem__(self, key, value):
old = self.get(key)
if old is None:
bisect.insort(self._list, value)
dict.__setitem__(self, key, value)
else:
oldpos = bisect.bisect_left(self._list, old)
newpos = bisect.bisect_left(self._list, value)
if newpos > oldpos:
newpos -= 1
for i in xrange(oldpos, newpos):
self._list[i] = self._list[i + 1]
else:
for i in xrange(oldpos, newpos, -1):
self._list[i] = self._list[i - 1]
self._list[newpos] = value
dict.__setitem__(self, key, value)
def __delitem__(self, key):
old = self.get(key)
if old is not None:
oldpos = bisect.bisect(self._list, old)
del self._list[oldpos]
dict.__delitem__(self, key)
def values(self):
return list(self._list)
这不是一个完整的 dict 但我猜。我没有测试删除，只是一个微小的更新集。您应该对其进行更大的单元测试，并将 values（）的返回值与 sorted（dict.values（instance））那里。这只是为了展示如何使用 bisect更新排序列表
It's not a complete dict yet I guess. I havn't tested deletions, and just a tiny update set. You should make a larger unit test for it, and compare the return of values() with that of sorted(dict.values(instance)) there. This is just to show how to update the sorted list with bisect
这篇关于Python的值排序字典的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
