Xin*_*ang 8 python dictionary key sorted
假设我有一本字典
{1:5, 2:5, 4:5}
是否有一个数据结构,如果我添加键值对3:5,让它输入字典中,以便键按排序顺序？即
{1:5, 2:5, 3:5, 4:5}
我知道collections.OrderedDict()这一点,但这只是按键添加顺序(这对我来说还不够).
我不想使用普通字典dic = {},然后必须使用sorted(dic)[0]抓取最小的密钥.我宁愿有sorted_dict[0]类型功能.
这样做的原因是,如果我使用普通字典,我将不得不多次调用排序,因为我不断将字符串添加到字典中.
编辑:我应该提到,它不仅是我关心的最小和最大的键,我还需要定期打印这本词典......
如果你打算不断地从字典中添加和删除键,你真的想要一些使用适当数据结构来解决问题的东西 - 不是哈希表(或哈希表加列表,就像SortedOrderedDict-type配方一样),但是平衡树(或类似的,如跳过列表).
如果你环顾一下PyPI,你会发现很多选择.我的建议是blist.尽管它的数据结构可能不像其他一些数据结构那样最优(因为B +树比二叉树更广泛),但对于几乎所有遇到的用例来说,它可能已经足够好了.它拥有完整且经过良好测试的界面,包括经过良好测试的性能保证.其他严肃的项目也使用了很多.
如果您正在处理树性能真正关键的罕见情况之一,您应该查看各种红黑树,splay树,skiplist等实现.我之前使用bintrees过,它有一个很棒的界面(例如,你可以通过索引访问键和值,甚至可以对树进行切片,以及将其视为一个dict,并且作者已经考虑过并避免了所有潜在的歧义),但我没有认真对其进行性能测试.
或者,如果您的键和值确实都是小整数,您可能需要考虑使用Cython将C++包装map<int, int>在Pythonic界面中.(在C++之上提供一个完整的界面是不太可能的map,但是你通常不需要它.)或者,或者修改其中一个实现,比如bintrees.FastRBTree存储和比较long而不是PyObject*.
另一方面,如果您只是一次创建字典然后使用它,那么答案会更简单.对它进行排序,并将其粘贴在一个OrderedDict.然后你不需要stdlib之外的任何东西.
sorted_dict = collections.OrderedDict(sorted(d.iteritems()))
从另一个答案的评论,你说"我没有权限安装新模块......"
首先,确保这是真的.你可能做在用户站点包目录下安装模块的许可.或者,如果virtualenv已安装和/或您使用内置的3.3 venv,甚至更好,您可能有权创建一个venv并安装模块.
但如果是这样,您需要做的是将文件从blist/ bintrees/ 复制到项目中.
您可能遇到的问题是大多数这些软件包都包含C扩展模块,这意味着您必须能够构建它们(好吧,build_ext -i它们).如果您的系统没有安装Python dev文件和编译器工具链,则无法执行此操作.在这种情况下,您正在寻找最好的纯Python解决方案.bintrees附带一个纯Python实现,与普通的C扩展实现相同,除了速度较慢.当然,它仍然是O(log N),只是常数因子要高很多.如果N足够大,它仍然是一个巨大的胜利; 如果没有,它可能不是.
如果这听起来很合理,但您需要帮助设置每用户站点包或虚拟环境,或者将模块复制到您的项目中,或者就地构建扩展等,您应该搜索对于现有问题,如果你找不到问题,可以问一个新问题(如果没有其他原因,因为安装问题专家的人不一定是数据结构的专家,甚至可能都没有读过这个问题题).