Python dict 排序

Python 的基础数据类型中的字典类型分为：无序字典 与 有序字典 两种类型

1、无序字典（普通字典）：

my_dict = dict()
my_dict["name"] = "lowman"
my_dict["age"] = 26
my_dict["girl"] = "Tailand"
my_dict["money"] = 80
my_dict["hourse"] = None
for key, value in my_dict.items(): 
　　print(key, value)

输出：

money 80
girl Tailand
age 26
hourse None
name lowman

可以看见，遍历一个普通字典，返回的数据和定义字典时的字段顺序是不一致的。

注意：

Python3.6 改写了 dict 的内部算法，Python3.6 版本以后的 dict 是有序的，所以也就无须再关注 dict 顺序性的问题。

2、有序字典

import collections

my_order_dict = collections.OrderedDict()
my_order_dict["name"] = "lowman"
my_order_dict["age"] = 45
my_order_dict["money"] = 998
my_order_dict["hourse"] = None

for key, value in my_order_dict.items():
    print(key, value)

输出：

name lowman
age 45
money 998
hourse None

有序字典可以按字典中元素的插入顺序来输出。

注意：

有序字典的作用只是记住元素插入顺序并按顺序输出。如果有序字典中的元素一开始就定义好了，后面没有插入元素这一动作，那么遍历有序字典，其输出结果仍然是无序的，因为缺少了有序插入这一条件，所以此时有序字典就失去了作用，所以有序字典一般用于动态添加并需要按添加顺序输出的时候。

import collections

my_order_dict = collections.OrderedDict(name="lowman", age=45, money=998, hourse=None)

for key, value in my_order_dict.items():
    print(key, value)

输出：

hourse None
age 45
money 998
name lowman

发现输出还是无序的，因为在定义有序字典的同时也定义了初始值，没有存在按序添加的操作，所以有序字典是没有记录插入字段的顺序，最后遍历时，得到数据的顺序仍然是无序的。

最简单的方法，这个是按照 key 值排序：

def sortedDictValues1(adict): 
    items = adict.items() 
    items.sort() 
return [value for key, value in items] 

又一个按照 key 值排序，貌似比上一个速度要快点

def sortedDictValues2(adict): 
	keys = adict.keys() 
	keys.sort() 
	return [dict[key] for key in keys] 

还是按 key 值排序，据说更快。。。而且当 key 为 tuple 的时候照样适用

def sortedDictValues3(adict): 
	keys = adict.keys() 
	keys.sort() 
return map(adict.get, keys) 

一行语句搞定：

[(k,di[k]) for k in sorted(di.keys())]

来一个根据 value 排序的，先把 item 的 key 和 value交 换位置放入一个 list 中，再根据list每个元素的第一个值，即原来的value 值，排序：

def sort_by_value(d): 
	items=d.items() 
	backitems=[[v[1],v[0]] for v in items] 
	backitems.sort() 
	return [ backitems[i][1] for i in range(0,len(backitems))] 

还是一行搞定：

[ v for v in sorted(di.values())]

用 lambda 表达式来排序，更灵活：

#正序
sorted(d.items(), lambda x, y: cmp(x[1], y[1]))
#反序
sorted(d.items(), lambda x, y: cmp(x[1], y[1]), reverse=True) 

用 sorted 函数的 key = 参数排序：

按照 key 进行排序

sorted(dict1.items(), key=lambda d: d[0])

按照 value 进行排序

sorted(dict1.items(), key=lambda d: d[1])

下面给出 python 内置 sorted 函数的帮助文档：

sorted(…)

sorted(iterable, cmp=None, key=None, reverse=False) –> new sorted list

看了上面这么多种对 dictionary 排序的方法，其实它们的核心思想都一样，即把 dictionary 中的元素分离出来放到一个list中，对 list 排序，从而间接实现对 dictionary 的排序。这个“元素”可以是 key，value 或者 item。

将 key, value 以 tuple 一起放在一个 list 中

l = []
 
l.append((akey,avalue))
 
# 用sort（）
# cmp前加“-”表示降序排序
 
l.sort(lambda a,b :cmp(a[1],b[1]))

Python 3.6 以后字典有序

在 Python 3.5（含）以前，字典是不能保证顺序的，键值对A先插入字典，键值对B后插入字典，但是当你打印字典的 Keys 列表时，你会发现 B 可能在 A 的前面。

但是从 Python 3.6 开始，字典是变成有顺序的了。你先插入键值对A，后插入键值对B，那么当你打印Keys列表的时候，你就会发现B在A的后面。

不仅如此，从 Python 3.6 开始，下面的三种遍历操作，效率要高于 Python 3.5 之前：

for key in 字典

for value in 字典.values()

for key, value in 字典.items()

从 Python 3.6 开始，字典占用内存空间的大小，视字典里面键值对的个数，只有原来的 30%~95%。

Python 3.6 到底对字典做了什么优化呢？为了说明这个问题，我们需要先来说一说，在Python 3.5（含）之前，字典的底层原理。

当我们初始化一个空字典的时候，CPython 的底层会初始化一个二维数组，这个数组有 8 行，3 列，如下面的示意图所示：

my_dict = {}

'''
此时的内存示意图
[[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---]]
'''

现在，我们往字典里面添加一个数据：

my_dict['name'] = 'kingname'

'''
此时的内存示意图
[[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[1278649844881305901, 指向 name 的指针, 指向 kingname 的指针],
[---, ---, ---],
[---, ---, ---]]
'''

假设在某一个运行时里面，hash(‘name’) 的值为 1278649844881305901。现在我们要把这个数对 8 取余数：

>>> 1278649844881305901 % 8
5

余数为 5，那么就把它放在刚刚初始化的二维数组中，下标为 5 的这一行。由于 name 和 kingname 是两个字符串，所以底层 C 语言会使用两个字符串变量存放这两个值，然后得到他们对应的指针。于是，我们这个二维数组下标为 5 的这一行，第一个值为 name 的 hash 值，第二个值为 name 这个字符串所在的内存的地址（指针就是内存地址），第三个值为 kingname 这个字符串所在的内存的地址。

现在，我们再来插入两个键值对：

my_dict['age'] = 26
my_dict['salary'] = 999999

'''
此时的内存示意图
[[-4234469173262486640, 指向 salary 的指针, 指向 999999 的指针],
[1545085610920597121, 执行 age 的指针, 指向 26 的指针],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[1278649844881305901, 指向name的指针, 指向kingname的指针],
[---, ---, ---],
[---, ---, ---]]
'''

那么字典怎么读取数据呢？首先假设我们要读取 age 对应的值。

此时，Python 先计算在当前运行时下面，age 对应的 Hash 值是多少

>>> hash('age')
1545085610920597121

然后对 8 取余数

当你要循环遍历字典的 Key 的时候，Python 底层会遍历这个二维数组，如果当前行有数据，那么就返回 Key 指针对应的内存里面的值。如果当前行没有数据，那么就跳过。所以总是会遍历整个二位数组的每一行。

每一行有三列，每一列占用 8 byte 的内存空间，所以每一行会占用 24 byte 的内存空间。

由于 Hash 值取余数以后，余数可大可小，所以字典的 Key 并不是按照插入的顺序存放的。

在 Python 3.6 以后，字典的底层数据结构发生了变化，现在当你初始化一个空的字典以后，它在底层是这样的：

my_dict = {}
'''
此时的内存示意图
indices = [None, None, None, None, None, None, None, None]
entries = []
'''

当你初始化一个字典以后，Python 单独生成了一个长度为 8 的一维数组。然后又生成了一个空的二维数组。

现在，我们往字典里面添加一个键值对：

my_dict['name'] = 'kingname'

'''
此时的内存示意图
indices = [None, 0, None, None, None, None, None, None]
entries = [[-5954193068542476671, 指向 name 的指针, 执行 kingname 的指针]]
'''

为什么内存会变成这个样子呢？我们来一步一步地看：

在当前运行时，name 这个字符串的 hash 值为 -5954193068542476671，这个值对 8 取余数是 1：

所以，我们把 indices 这个一维数组里面，下标为 1 的位置修改为0。

这里的 0 是什么意思呢？0 是二位数组 entries 的索引。现在 entries 里面只有一行，就是我们刚刚添加的这个键值对的三个数据：name 的 hash 值、指向 name 的指针和指向 kinganme 的指针。所以 indices 里面填写的数字 0，就是刚刚我们插入的这个键值对的数据在二位数组里面的行索引。

新的这种方式，当我要插入新的数据的时候，始终只是往 entries 的后面添加数据，这样就能保证插入的顺序。当我们要遍历字典的 Keys 和 Values 的时候，直接遍历 entries 即可，里面每一行都是有用的数据，不存在跳过的情况，减少了遍历的个数。

老的方式，当二维数组有 8 行的时候，即使有效数据只有 3 行，但它占用的内存空间还是 8 24 = 192 byte。但使用新的方式，如果只有三行有效数据，那么 entries 也就只有 3 行，占用的空间为 3 24 =72 byte，而 indices 由于只是一个一维的数组，只占用 8 byte，所以一共占用 80 byte。内存占用只有原来的 41%。