Python中按键sorting的字典
我正在寻找一个有序的关联数组，即一个有序的字典的可靠实现。 我想按照键的顺序，而不是插入顺序。
更确切地说，我正在寻找一个int-to-float（或另一个用例的string到浮点数）映射结构的空间有效实现，其中：
- 有序迭代是O（n）
- 随机访问是O（1）
我想出的最好的方法是粘合一个字典和一个键列表，保持最后一个alignment并插入。
任何更好的想法？
“随机访问O（1）”是一个非常严格的要求，基本上强加了一个基础的散列表 – 我希望你的意思是随机的只读，因为我认为它可以在math上certificate比在一般情况下不可能有O （1）写以及O（N）有序的迭代。
我不认为你会发现一个预先打包的容器适合你的需求，因为它们太极端了 – O（log N）访问当然会使世界上的所有变化。 要获得读取和迭代所需的大O行为，需要粘合两个数据结构，实质上是一个字典和一个堆（或sorting列表或树），并保持同步。 虽然你没有指定，但我认为你只能得到你想要的种类的摊销行为 – 除非你真的愿意支付插入和删除的任何性能命中，这是你expression规格的字面含义，但是似乎是一个相当不太现实的要求。
对于O（1）读和分期 O（N）有序的迭代，只需保留一个字典的一侧的所有键列表。 例如：
class Crazy(object): def __init__(self): self.d = {} self.L = [] self.sorted = True def __getitem__(self, k): return self.d[k] def __setitem__(self, k, v): if k not in self.d: self.L.append(k) self.sorted = False self.d[k] = v def __delitem__(self, k): del self.d[k] self.L.remove(k) def __iter__(self): if not self.sorted: self.L.sort() self.sorted = True return iter(self.L) 如果你不喜欢“分期付款O（N）顺序”，你可以删除self.sorted，只需在__setitem__本身重复self.L.sort() 。 这使得写O（N日志N），当然（当我仍然有写在O（1））。 这两种方法都是可行的，很难想象其中一个本质上优于另一个。 如果你倾向于做一堆写，然后一堆迭代，那么上面的代码中的方法是最好的; 如果它通常是一个写，一个迭代，另一个写，另一个迭代，那么这只是一个洗。
顺便说一句，这需要Python的sorting（又名“timsort”）的不寻常的（和美好的; – ）性能特点的无耻优势：其中，sorting列表大多是sorting，但最后加上一些额外的项目基本上是O （N）（如果与已sorting的前缀部分相比，增加的项目数量不够）。 我听说Java很快就获得了这样的成绩，因为Josh Block对Python的技术讲座印象深刻，所以他开始在他的笔记本电脑上为它的JVM编写代码。 大多数系统（包括我认为今天的Jython和IronPython）基本上都是按照O（N log N）操作进行sorting，而不是利用“大部分有序”的input。 蒂姆·彼得斯（Tim Peters）在今天提出的“自然融合”（natural mergesort）就是Python的缩影，在这方面是一个奇迹。
sortedcontainers模块提供了一个SortedDicttypes来满足您的需求。 它基本上粘合SortedList和字典types在一起。 该字典提供O（1）查找和SortedList提供O（N）迭代（它非常快）。 整个模块是纯Python，并具有基准图来备份性能声明（快速C实现）。 SortedDict也经过了全面的testing，覆盖率达到100％，时间紧迫。 它与Python 2.6到3.4兼容。
这是我自己的实现：
import bisect class KeyOrderedDict(object): __slots__ = ['d', 'l'] def __init__(self, *args, **kwargs): self.l = sorted(kwargs) self.d = kwargs def __setitem__(self, k, v): if not k in self.d: idx = bisect.bisect(self.l, k) self.l.insert(idx, k) self.d[k] = v def __getitem__(self, k): return self.d[k] def __delitem__(self, k): idx = bisect.bisect_left(self.l, k) del self.l[idx] del self.d[k] def __iter__(self): return iter(self.l) def __contains__(self, k): return k in self.d
插入是O（n）（因为插入，但在我的情况下，不是一个杀手，因为我追加远多于真正插入，所以通常的情况是分期偿还O（1） ））。 访问是O（1），迭代O（n）。 但也许有人发明了一种更聪明的结构（C）
对于这种情况，有序树通常更好，但随机访问将是log（n）。 您应该考虑到插入和移除成本…
你可以build立一个允许遍历的字典，在每个位置存储一个对(value, next_key) 。
随机访问：
my_dict[k][0] # for a key k
穿越：
k = start_key # stored somewhere while k is not None: # next_key is None at the end of the list v, k = my_dict[k] yield v
保持一个指针start和end ，你将有效地更新这些情况下，你只需要添加到列表的末尾。
插入中间显然是O（n）。 如果你需要更多的速度，可能你可以build立一个跳过列表 。
我不确定你正在使用哪个python版本，但是如果你想尝试一下，Python 3.1包含Ordered字典的官方实现： http : //www.python.org/dev/peps/pep-0372/ http ：//docs.python.org/3.1/whatsnew/3.1.html#pep-372-ordered-dictionaries
我在2007年实施的ordereddict包（ http://anthon.home.xs4all.nl/Python/ordereddict/ ）包含sorteddict。 sorteddict是一个KSO（Key Sorted Order）字典。 它以C语言实现，非常节省空间，比纯Python实现快几倍。 缺点是只能和CPython一起使用。
>>> from _ordereddict import sorteddict >>> x = sorteddict() >>> x[1] = 1.0 >>> x[3] = 3.3 >>> x[2] = 2.2 >>> print x sorteddict([(1, 1.0), (2, 2.2), (3, 3.3)]) >>> for i in x: ... print i, x[i] ... 1 1.0 2 2.2 3 3.3 >>>
对不起，回复迟了，也许这个答案可以帮助别人find那个图书馆。
这是一个馅饼：我需要类似的东西。 但是请注意，这个特定的实现是不可变的，一旦创build实例，就没有插入：然而，确切的性能并不完全符合你的要求。 查找是O（log n），全面扫描是O（n）。 这可以根据键/值（元组）对的元组来使用bisect模块。 即使你不能正确使用它，你也可能会有一些成功的适应你的需求。
import bisect class dictuple(object): """ >>> h0 = dictuple() >>> h1 = dictuple({"apples": 1, "bananas":2}) >>> h2 = dictuple({"bananas": 3, "mangoes": 5}) >>> h1+h2 ('apples':1, 'bananas':3, 'mangoes':5) >>> h1 > h2 False >>> h1 > 6 False >>> 'apples' in h1 True >>> 'apples' in h2 False >>> d1 = {} >>> d1[h1] = "salad" >>> d1[h1] 'salad' >>> d1[h2] Traceback (most recent call last): ... KeyError: ('bananas':3, 'mangoes':5) """ def __new__(cls, *args, **kwargs): initial = {} args = [] if args is None else args for arg in args: initial.update(arg) initial.update(kwargs) instance = object.__new__(cls) instance.__items = tuple(sorted(initial.items(),key=lambda i:i[0])) return instance def __init__(self,*args, **kwargs): pass def __find(self,key): return bisect.bisect(self.__items, (key,)) def __getitem__(self, key): ind = self.__find(key) if self.__items[ind][0] == key: return self.__items[ind][1] raise KeyError(key) def __repr__(self): return "({0})".format(", ".join( "{0}:{1}".format(repr(item[0]),repr(item[1])) for item in self.__items)) def __contains__(self,key): ind = self.__find(key) return self.__items[ind][0] == key def __cmp__(self,other): return cmp(self.__class__.__name__, other.__class__.__name__ ) or cmp(self.__items, other.__items) def __eq__(self,other): return self.__items == other.__items def __format__(self,key): pass #def __ge__(self,key): # pass #def __getattribute__(self,key): # pass #def __gt__(self,key): # pass __seed = hash("dictuple") def __hash__(self): return dictuple.__seed^hash(self.__items) def __iter__(self): return self.iterkeys() def __len__(self): return len(self.__items) #def __reduce__(self,key): # pass #def __reduce_ex__(self,key): # pass #def __sizeof__(self,key): # pass @classmethod def fromkeys(cls,key,v=None): cls(dict.fromkeys(key,v)) def get(self,key, default): ind = self.__find(key) return self.__items[ind][1] if self.__items[ind][0] == key else default def has_key(self,key): ind = self.__find(key) return self.__items[ind][0] == key def items(self): return list(self.iteritems()) def iteritems(self): return iter(self.__items) def iterkeys(self): return (i[0] for i in self.__items) def itervalues(self): return (i[1] for i in self.__items) def keys(self): return list(self.iterkeys()) def values(self): return list(self.itervalues()) def __add__(self, other): _sum = dict(self.__items) _sum.update(other.__items) return self.__class__(_sum) if __name__ == "__main__": import doctest doctest.testmod()
对于“string浮动”问题，您可以使用Trie – 它提供O（1）访问时间和O（n）sorting迭代。 按“sorting”我的意思是“按键sorting” – 似乎这个问题意味着相同。
一些实现（每个都有自己的优点和缺点）：
- https://github.com/biopython/biopython具有全function的Trie的Bio.trie模块;; 其他Trie包更有记忆力;
- https://github.com/kmike/datrie – 随机插入可能会很慢，密钥字母表必须事先知道;
- https://github.com/kmike/hat-trie – 所有操作都很快，但是许多字典方法没有实现。 底层的C库支持sorting的迭代，但不是在包装中实现;
- https://github.com/kmike/marisa-trie – 非常有效的内存，但不支持插入; 迭代不是默认sorting，但可以进行sorting（文档中有一个示例）;
- https://github.com/kmike/DAWG – 可以看作是最小化的Trie; 非常快速和高效的内存，但不支持插入; 有大小限制（几GB的数据）
