嵌套在Dict理解中的Python集合理解

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长达18,000个项目.这段代码运行500个元组的列表只需不到10秒,但运行完整的18,000个元组需要12分钟以上.我必须认为这是因为我在dict理解中嵌套了一套理解.

有没有办法避免这种情况,或者更聪明的方法呢？

Answer 1

你有一个双循环,所以你需要O(N**2)时间来制作你的字典.对于500件物品,采取250.000步骤,对于18k物品,需要完成3.24 亿步骤.

这是一个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显式禁用工厂以防止这种情况.