Понимание набора Python, вложенное в понимание Dict

Question

У меня есть список кортежей, где каждый tuple содержит string и число в виде:

[(string_1, num_a), (string_2, num_b), ...]

Строки не уникальны, как и числа, например (string_1 , num_m) или же (string_9 , num_b) скорее всего, существуют в списке.

Я пытаюсь создать словарь со строкой в ​​качестве ключа и набором всех чисел, встречающихся с этой строкой в ​​качестве значения:

dict = {string_1: {num_a, num_m}, string_2: {num_b}, ...}

Я сделал это несколько успешно с помощью следующего словарного понимания с вложенным множественным пониманием:

#st_id_list = [(string_1, num_a), ...]
#st_dict = {string_1: {num_a, num_m}, ...} 
st_dict = {
    st[0]: set(
        st_[1]
        for st_ in st_id_list
        if st_[0] == st[0]
    )
    for st in st_id_list
}

Есть только одна проблема: st_id_list 18000 наименований. Этот фрагмент кода занимает менее десяти секунд, чтобы запустить список из 500 кортежей, и более двенадцати минут, чтобы запустить полный 18 000 кортежей. Я должен думать, что это потому, что я вложил определенное понимание в понимание диктата.

Есть ли способ избежать этого или умнее?

Answer 1

У вас есть двойной цикл, поэтому вы тратите O(N**2) время, чтобы создать свой словарь. Для 500 предметов необходимо сделать 250 000 шагов, а для ваших 18 тысяч нужно сделать 324 миллиона шагов.

Вот вместо этого петля O(N), поэтому 500 шагов для вашего меньшего набора данных, 18 000 шагов для большего набора данных:

st_dict = {}
for st, id in st_id_list:
    st_dict.setdefault(st, set()).add(id)

Это использует dict.setdefault() метод, который гарантирует, что для данного ключа (ваших строковых значений), по крайней мере, пустой набор доступен, если ключ отсутствует, затем добавляет текущий id значение этого набора.

Вы можете сделать то же самое с collections.defaultdict() объект:

from collections import defaultdict

st_dict = defaultdict(set)
for st, id in st_id_list:
    st_dict[st].add(id)

defaultdict() использует переданную фабрику, чтобы установить значение по умолчанию для отсутствующих ключей.

Недостаток defaultdict Подход заключается в том, что объект продолжает генерировать значения по умолчанию для отсутствующих ключей после цикла, что может скрывать ошибки приложения. использование st_dict.default_factory = None отключить фабрику явно, чтобы предотвратить это.

Answer 2

Почему вы используете два цикла, когда вы можете сделать в одном цикле, как это:

list_1=[('string_1', 'num_a'), ('string_2', 'num_b'),('string_1' , 'num_m'),('string_9' , 'num_b')]

string_num={}
for i in list_1:
    if i[0] not in string_num:
        string_num[i[0]]={i[1]}
    else:
        string_num[i[0]].add(i[1])

print(string_num)

выход:

{'string_9': {'num_b'}, 'string_1': {'num_a', 'num_m'}, 'string_2': {'num_b'}}