V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
qazwsxkevin
V2EX  ›  Python

有两个这样的字典列表,如何按字典的 key 值进行去重合并? 比较高效率的做法?

  •  
  •   qazwsxkevin · 2020-02-26 19:37:01 +08:00 · 4243 次点击
    这是一个创建于 1492 天前的主题,其中的信息可能已经有所发展或是发生改变。

    请教思路算法,或者用什么轮子会更高效?
    毕竟整个 List 还是挺大的,7 到 8 万个元素,
    今天试着用 for,for,for 来整,不太成功,而且解决思路线径还把自己绕晕了
    后来想着是放入 Mysql 搞的,但考虑到使用环境,不太现实
    今天试着用 pandas 来弄了一下,结果还把自己弄晕在 index 和 row 的事情上了

       AList = [{'型号': 12, '重量': 16, '产地': 19,'审核人':33},
                {'型号': 22, '重量': 92, '产地': 87,'审核人':34},
                {'型号': 15, '重量': 27, '产地': 86,'审核人':35},
                {'型号': 71, '重量': 55, '产地': 21,'审核人':36}]
    
       BList = [{'产地': 87, '型号': 22, '重量': 92,'审核人':34},
                {'产地': 86, '型号': 15, '重量': 27,'审核人':35},
                {'产地': 44, '型号': 65, '重量': 91,'审核人':33}]
    
    A,B 两个列表每个元素都是一个字典  
    A,B 两个 List 选择性进行合并,得出 CList  
    
    例子是只有四个 k/v 对, 但实际字典很多 k/v 对,而且每个字典里面的键值对的数量,也不尽相同  
    
    合并有以下去重条件:  
    只以型号, 重量, 审核人三个 value 作为去重判断,  
    A,B 两个列表,如果有这三个 value 重复, 只保留 AList 内容(整个字典)加入到 CList  
    BList 里面字典里三个 value 不重复的,整个字典作为元素加入到 CList
    
    15 条回复    2020-03-04 10:53:27 +08:00
    1373569162
        1
    1373569162  
       2020-02-26 20:20:36 +08:00
    构造一个 dict,型号, 重量, 审核人拼接起来作为 key,遍历两个 list,key 不在 dict 里就加进去,最后输出 dict.values()
    epicnoob
        2
    epicnoob  
       2020-02-26 22:24:09 +08:00
    f = lambda _: (_['产地'], _['型号'], _['重量'])
    t = sorted(AList+BList, key=f)
    CList = reduce(lambda l, v: l + [v] if f(l[-1]) != f(v) else l, t, [t[0]])
    epicnoob
        3
    epicnoob  
       2020-02-26 22:25:03 +08:00
    排序是稳定的,相同值肯定是 Alist 的在前面
    ferstar
        4
    ferstar  
       2020-02-26 22:50:52 +08:00
    python >= 3.6

    ```python3
    a_list = [
    {"型号": 12, "重量": 16, "产地": 19, "审核人": 33},
    {"型号": 22, "重量": 92, "产地": 87, "审核人": 34},
    {"型号": 15, "重量": 27, "产地": 86, "审核人": 35},
    {"型号": 71, "重量": 55, "产地": 21, "审核人": 36},
    ]

    b_list = [
    {"产地": 87, "型号": 22, "重量": 92, "审核人": 34},
    {"产地": 86, "型号": 15, "重量": 27, "审核人": 35},
    {"产地": 44, "型号": 65, "重量": 91, "审核人": 33},
    ]


    def generate_key(item):
    return "_".join(v for k, v in item.items() if k != "型号")


    hash_map = {}

    for item in a_list:
    hash_map.setdefault(generate_key(item), item)

    for item in b_list:
    hash_map.setdefault(generate_key(item), item)

    c_list = list(hash_map.values())
    ```
    MoYi123
        5
    MoYi123  
       2020-02-26 22:57:20 +08:00
    tmp = set()
    rt = []
    for i in AList + BList:
    t = (i['型号'], i['重量'], i['审核人'])
    if t not in tmp:
    tmp.add(t)
    rt.append(i)
    bugmakerxs
        7
    bugmakerxs  
       2020-02-26 23:12:58 +08:00
    就用 mysql 啊
    bugmakerxs
        8
    bugmakerxs  
       2020-02-26 23:16:11 +08:00
    型号+重量+产地 md5 做 key,该行数据为 value 放入一个字典,Blist 先放进去,alist 后放进去。或者直接做张标,key 做唯一索引
    BlackBerry999
        9
    BlackBerry999  
       2020-02-27 08:34:11 +08:00
    构建一个 3 层的多叉树,一层型号,二层重量,三层审核人。然后遍历 AB 两个 list 构建 3 层多叉树,并且来自于 AList 的值可以覆盖重写叶子节点。
    wuwukai007
        10
    wuwukai007  
       2020-02-27 10:54:29 +08:00
    逻辑梳理一下,
    第一、A 与 B 找固定那三个列的重复,重复的值只保留 原 A 的,保存到 c
    第二,B 根据三列去重后,并且不在刚刚第一步 的结果中 保存到 c
    第三、A 根据三列去重,保存到 c
    wuwukai007
        11
    wuwukai007  
       2020-02-27 11:19:45 +08:00
    regex = ['型号','审核人','重量']
    d1 = pd.DataFrame(a_list).drop_duplicates(regex)
    d2 = pd.DataFrame(b_list).drop_duplicates(regex)
    buf = d1.merge(d2,on=regex,how='inner')
    new_col = [col for col in buf.columns.tolist() if str(col).endswith('_x')] + regex
    buf_c = buf[new_col]
    buf_c.columns = [str(col).replace('_x','') for col in buf_c.columns.tolist()]
    c1 = d1.append(buf_c).drop_duplicates(regex).to_dict(orient="records")
    c2 = d2.to_dict('records')
    c_list = c1 + c2
    wuwukai007
        12
    wuwukai007  
       2020-02-27 11:43:21 +08:00
    还有我试了下 几万条数据 就算用纯 for 循环写,也不慢的吧。
    MisterLee
        13
    MisterLee  
       2020-02-27 17:29:49 +08:00
    ——Python&Pandas

    a_df= pd.DataFrame(a_list)
    b_df= pd.DataFrame(b_list)

    a_b_df = pd.concat([a_df, b_df], axis=0).drop_duplicates(['型号', '重量', '审核人'], keep='first')

    c_list = []

    for _, item in a_b_df.iterrows():
    c_list.append(item.dropna().to_dict())
    wdc63
        14
    wdc63  
       2020-02-27 18:35:39 +08:00
    @bugmakerxs 嗯,遍历列表 A,以型号, 重量, 审核人的值做 key,下标做 value,建立 hash 表,遍历列表 B,查找每一个元素是否在 hash 表中,有的话合并到 Alist,没有的话添加到 Alist 末尾,每个字典都很简单,合并过程复杂度可以认为是 O(1),整个算法复杂度为 O(M+N),应该是效率最高的算法了。
    moxiaowei
        15
    moxiaowei  
       2020-03-04 10:53:27 +08:00
    @wdc63 确实是的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1029 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 22:29 · PVG 06:29 · LAX 15:29 · JFK 18:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.