V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
fields
V2EX  ›  问与答

对约 35g 的数据去重

  •  
  •   fields · 2020-02-04 10:23:01 +08:00 · 4298 次点击
    这是一个创建于 1514 天前的主题,其中的信息可能已经有所发展或是发生改变。
    数据占了 35g 左右存储,有标识每条数据的 id,还剩大约 7g 空闲空间,需要对这 35g 的数据去重,内存是 8g 的.如何对数据进行去重?
    34 条回复    2020-02-05 09:44:08 +08:00
    alalida
        1
    alalida  
       2020-02-04 10:33:49 +08:00 via Android
    你先想一想目标时间复杂度和空间复杂度。去重意味要查找,那最好也就对数时间复杂度。此外要看能否分批处理,数据有无规律。可以分批处理也会快很多。总之要先看数据长什么样。
    otakustay
        2
    otakustay  
       2020-02-04 10:36:13 +08:00
    数据是 35G,其中 id 部分有多大?不大的话哈希应该是有办法建起来的……
    shuangyeying
        3
    shuangyeying  
       2020-02-04 10:39:03 +08:00
    是裤子么?
    opengps
        4
    opengps  
       2020-02-04 10:39:44 +08:00
    去重字段仅仅是 id 字段?还是全字段匹配?
    malusama
        5
    malusama  
       2020-02-04 10:44:37 +08:00
    bloomfilter 有误差率
    fields
        6
    fields  
    OP
       2020-02-04 10:50:10 +08:00
    @opengps 每个 id 字段标识这条数据
    fields
        7
    fields  
    OP
       2020-02-04 10:50:23 +08:00
    @shuangyeying 不是的,亲
    fields
        8
    fields  
    OP
       2020-02-04 10:51:43 +08:00
    @alalida 在用分片,时间换空间,但很慢,每次 10w 条
    fields
        9
    fields  
    OP
       2020-02-04 10:52:31 +08:00
    @malusama 有空间限制的
    fields
        10
    fields  
    OP
       2020-02-04 10:53:41 +08:00
    @alalida 经过分析,每条数据里边的 id 唯一标识这条数据
    wysnylc
        11
    wysnylc  
       2020-02-04 11:11:07 +08:00 via Android
    把 id 提出来,还能有 35g ?
    ho121
        12
    ho121  
       2020-02-04 11:17:06 +08:00 via Android
    对每条数据 hash 后存到哈希表或者二叉树中。
    hash 算法也不需要碰撞率很低的那种,比如 crc32,crc64 这种简单的就行,这样可以加快 hash 速度,并减少内存使用。当碰到 hash 相同的,需要做完全匹配来判断数据是否真的是相等。
    哈希表或者二叉树每个节点要存下每个 hash 对应的 id (可能有多个)。

    数据用流式读取,或者扔进数据库中。


    手机码字,有点乱
    grimpil
        13
    grimpil  
       2020-02-04 11:18:08 +08:00 via Android   ❤️ 5
    还以为是 35 克数据
    fields
        14
    fields  
    OP
       2020-02-04 11:22:23 +08:00
    @grimpil 哈哈哈哈哈哈
    keepeye
        15
    keepeye  
       2020-02-04 11:24:07 +08:00
    遍历所有数据,id 字段走布隆过滤器去重 用不了多少内存
    mxT52CRuqR6o5
        16
    mxT52CRuqR6o5  
       2020-02-04 11:26:58 +08:00 via Android
    Bitmap
    binux
        17
    binux  
       2020-02-04 11:29:05 +08:00
    如果数据>>id,拿 id 出来随便爱怎么搞怎么搞
    如果数据就是 id,每 7g 分片排序再 merge 排序。
    zengguibo
        18
    zengguibo  
       2020-02-04 11:57:32 +08:00
    如果只是文本数据,压缩一下传到性能强内存大的机器上,直接导入内存去重
    Tlvncks
        19
    Tlvncks  
       2020-02-04 12:06:51 +08:00
    引用;@grimpil #13 还以为是 35 克数据

    -------------------------------------------------------
    我也看了半天,还在想 35g 啥玩意?难道想提纯??
    Rekkles
        20
    Rekkles  
       2020-02-04 12:19:26 +08:00
    数据 hash 然后对比去重?
    有个笨一点的办法,数据导入 db 做唯一索引 一条一条导入,导入失败的就是重复的,牺牲时间换空间。
    coolcfan
        21
    coolcfan  
       2020-02-04 12:26:52 +08:00 via Android
    跟 13 楼一样,看到是小写第一反应是 35 克数据……
    suotm
        22
    suotm  
       2020-02-04 12:36:19 +08:00
    取 3.5G 做好去重的脚本,然后开一个 64GB 内存的云主机跑
    lululau
        23
    lululau  
       2020-02-04 12:36:41 +08:00 via iPhone
    35g? 用什么称的?
    hhhsuan
        24
    hhhsuan  
       2020-02-04 12:39:39 +08:00 via Android
    大小写很重要啊
    netnr
        25
    netnr  
       2020-02-04 12:47:28 +08:00
    直接执行开窗函数按 id 分组排序取大于 1 的项并删除,难道顶不住?
    ofblyt
        26
    ofblyt  
       2020-02-04 13:19:18 +08:00
    最近做饭做的,看到 35g 还想 35 克去重( zhong )是给什么去皮吗
    yufeng0681
        27
    yufeng0681  
       2020-02-04 13:28:10 +08:00
    根据 id 第一位进行文件分拣(切割到),假设有 26 个字母,10 个数字; 估计每个文件 1G 左右,那样问题就变成了 1G 文件的处理
    gfreezy
        28
    gfreezy  
       2020-02-04 14:08:20 +08:00
    shell 里面 sort | uniq 就可以。内存不够的时候 sort 会自动交换到磁盘上。

    https://unix.stackexchange.com/questions/383056/sort-huge-list-130gb-in-linux
    fields
        29
    fields  
    OP
       2020-02-04 14:34:54 +08:00
    @lululau 电子秤吧
    fields
        30
    fields  
    OP
       2020-02-04 14:35:40 +08:00
    @ofblyt 姜吧
    fields
        31
    fields  
    OP
       2020-02-04 14:55:15 +08:00
    @gfreezy 存储有限的,都在数据库里
    fields
        32
    fields  
    OP
       2020-02-04 14:57:54 +08:00
    @yufeng0681 id 是纯数字,剩余的空间只有 7 个 G
    gfreezy
        33
    gfreezy  
       2020-02-04 16:02:47 +08:00
    @fields 建个新表加上 unique key,重新 load 一下就可以
    fuye
        34
    fuye  
       2020-02-05 09:44:08 +08:00 via Android
    create table tmp(id bigint,unique key id ( id ))
    insert into tmp select id from 你的表
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   961 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 43ms · UTC 20:43 · PVG 04:43 · LAX 13:43 · JFK 16:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.