Сортировать список словаря по порядку указания ключа c

Question

У меня есть list из dict, например:

data = [{"uid": "a1", "name": "b1"}, 
        {"uid": "a3", "name": "b3"}, 
        {"uid": "a4", "name": "b4"},
        {"uid": "a5", "name": "b5"}]

Теперь я хочу отсортировать list по порядку поля uid следующим образом:

uid_order = ['a1', 'a5', 'a3', 'a4']

Что означает, что выходные данные должны быть:

[{"uid": "a1", "name": "b1"}, 
 {"uid": "a5", "name": "b5"},
 {"uid": "a3", "name": "b3"},
 {"uid": "a4", "name": "b4"}]

Конечно, я могу создать новый пустой list, а затем использовать 2 for циклы для проверки и добавления каждого элемента, но есть ли какой-нибудь элегантный способ (или лучшая сложность) сделать это?

Answer 1

O (n) решение:

>>> [*map({d['uid']: d for d in data}.get, uid_order)]
[{'uid': 'a1', 'name': 'b1'},
 {'uid': 'a5', 'name': 'b5'},
 {'uid': 'a3', 'name': 'b3'},
 {'uid': 'a4', 'name': 'b4'}]

Answer 2

Вы можете отсортировать список на месте с помощью метода sort, если хотите избежать создания нового списка. При этом будет использоваться Timsort, который имеет O(n log n) сложность, намного лучше, чем предложенная вами O(n^2) реализация:

uid_order = {k: i for i, k in enumerate(uid_order)}
data.sort(key=uid_order.get)

Чтобы ускорить поиск в uid_order, я инвертирую его в словарь (инвертировать, потому что список отображает индекс на элемент, в то время как вы хотите, чтобы элемент индексировал). Вместо O(n) поиска при каждой оценке ключа теперь у вас есть O(1) поиск.

Альтернативный способ сделать словарь, используя только вызовы функций:

uid_order = dict(map(reversed, enumerate(uid_order)))

Смотри также: Python Сортировка КАК

Answer 3

С помощью функции sorted вы можете указать ключ, по которому должна сортироваться функция. Вы хотите получить доступ к значению ключа "uid" для каждого словаря, и индекс этого значения в uid_order определяет индекс этого словаря в отсортированном списке:

sorted(data, key = lambda x: uid_order.index(x["uid"]))

Что означает этот код, каждый элемент список передается функции lambda. Полученное значение используется в качестве ключа для сортировки после.