Какой самый быстрый способ преобразовать частоту словаря в список в Python?

Question

У меня частота словаря следующая:

freq = {'a': 1, 'b': 2, 'c': 3}

Это просто означает, что у меня есть один a, два b и три c.

Я хотел бы преобразовать его в полный список:

lst = ['a', 'b', 'b', 'c', 'c', 'c']

Какой самый быстрый (экономичный по времени) или самый компактный (экономичный) способ сделать это?

Answer 1

Давайте разберем это на два O (N) прохода: один для каталогизации чисел и один для создания отсортированного списка. Я обновил имена переменных; List - особенно плохой выбор, учитывая встроенный тип list. Я также добавил 10 к каждому значению, чтобы вы могли видеть, как работает смещение нижнего конца.

coll = [11, 14, 15, 12, 16, 17, 19, 13]
last = 19
first = 11

offset = first
size = last-first+1

# Recognize all values in a dense "array"
need = [False] * size
for item in coll:
    need[item - offset] = True

# Iterate again in numerical order; for each True value, add that item to the new list
sorted_list = [idx + offset for idx, needed_flag in enumerate(need) if needed_flag] 
print(sorted_list)

ВЫХОД:

[11, 12, 13, 14, 15, 16, 17, 19]

Answer 2

Да, но только если элементы являются (или могут быть представлены как) целыми числами, и если количество элементов между самым маленьким и самым большим элементом достаточно близко к разнице между ними, в этом случае вы можете использовать bucket sort , что приводит к O (n) сложности времени, где n - это разница между самым маленьким и самым большим предметом. Это было бы более эффективно, чем использование других алгоритмов сортировки, со средней сложностью по времени O (n log n) .

В случае List = [1, 4, 5, 2, 6, 7, 9, 3], как в вашем вопросе, действительно, более эффективно использовать сортировку по сегменту, когда известно, что 1 - это наименьший элемент, а 9 - наибольший, поскольку между диапазонами отсутствует только 8. В следующем примере используется collections.Counter для учета возможности того, что в списке ввода могут быть дубликаты:

from collections import Counter
counts = Counter(List)
print(list(Counter({i: counts[i] for i in range(1, 10)}).elements()))

Это выводит:

[1, 2, 3, 4, 5, 6, 7, 9]