如何基于python中的列表对字典进行排序

Question

我有一本字典

a = {'ground': obj1, 'floor 1': obj2, 'basement': obj3}

我有一份清单.

a_list = ['floor 1', 'ground', 'basement']

我想基于列表使用其键对字典a进行排序.有可能吗？

即:

sort(a).based_on(a_list) #this is wrong. But I want something like this. 

输出不必是另一个字典,我不介意将字典转换为元组然后对它们进行排序.

Answer 1

天真的方式,使用sorted()函数和自定义排序键(为每个(key, value)生成的对调用)对(键,值)元组列表进行排序dict.items()):

sorted(a.items(), key=lambda pair: a_list.index(pair[0]))

更快的方法是,首先创建一个索引图:

index_map = {v: i for i, v in enumerate(a_list)}
sorted(a.items(), key=lambda pair: index_map[pair[0]])

这是更快的,因为字典查找index_map需要O(1)恒定时间,而a_list.index()调用必须每次扫描列表,因此采用O(N)线性时间.由于针对字典中的每个键值对调用该扫描,因此天真排序选项采用O(N ^ 2)二次时间,而使用映射使得排序保持有效(O(N log N),线性时间).

两者都假设a_list包含所有键a.但是,如果是这种情况,那么您也可以反转查找并按顺序检索键:

[(key, a[key]) for key in a_list if key in a]

这需要O(N)线性时间,并允许在a_list其中不存在额外的键a.

明确:O(N)> O(N log N)> O(N ^ 2),请参阅此备忘单以供参考.

演示:

>>> a = {'ground': 'obj1', 'floor 1': 'obj2', 'basement': 'obj3'}
>>> a_list = ('floor 1', 'ground', 'basement')
>>> sorted(a.items(), key=lambda pair: a_list.index(pair[0]))
[('floor 1', 'obj2'), ('ground', 'obj1'), ('basement', 'obj3')]
>>> index_map = {v: i for i, v in enumerate(a_list)}
>>> sorted(a.items(), key=lambda pair: index_map[pair[0]])
[('floor 1', 'obj2'), ('ground', 'obj1'), ('basement', 'obj3')]
>>> [(key, a[key]) for key in a_list if key in a]
[('floor 1', 'obj2'), ('ground', 'obj1'), ('basement', 'obj3')]

Answer 2

您可以按列表提供的键的顺序检索值,并从键值对中创建一个新列表.

例:

d = a      # dictionary containing key-value pairs that are to be ordered
l = a_list # list of keys that represent the order for the dictionary
# retrieve the values in order and build a list of ordered key-value pairs
ordered_dict_items = [(k,d[k]) for k in l]