V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
1cming
V2EX  ›  Java

两个百万集合之间的查找、组合

  •  
  •   1cming · 2018-05-02 15:30:32 +08:00 · 3517 次点击
    这是一个创建于 2157 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前提: 假设有 objectX,objectY 两个对象,这两个对象通过其自身属性唯一的 ID 可关联到。 现在 objectX 存在于集合 A 中,objectY 存在于集合 B 中,A、B 的 size 都是百万级别。

    操作步骤: step1:对 A 进行遍历 step2:如果 A 中 objectX 的 ID 在 B 集合中可以找到对应的 objectY step3:把 objectX、objectY 合并成一个新的 objectZ 放入到集合 C 中

    疑问: 一.百万级别的数据这样操作是否合适? 二.step1 步骤避免不了,step2 中定位到 objectY 有没有什么好的思路(考虑性能、速度)? 目前是把集合 B 转换成了 k-v 形式,key 放 ID,用 API 提供的 contains 去判断是否存在。

    9 条回复    2018-05-03 19:11:26 +08:00
    kingname
        1
    kingname  
       2018-05-02 15:39:54 +08:00 via iPhone
    你知道集合是可以求交集的吗?你直接求 A 与 B 的交集就可以了。
    zn
        2
    zn  
       2018-05-02 15:49:04 +08:00
    要看你的实现了,如果遍历速度、定位速度足够快,那就直接遍历,就是这样么简单粗暴。
    glacer
        3
    glacer  
       2018-05-02 16:34:20 +08:00   ❤️ 1
    参考 MySQL 的 Join 实现:(Nested Loop join)[https://dev.mysql.com/doc/refman/5.7/en/nested-loop-joins.html]
    遍历 A 是避免不了的,那我们可以在 B 上做索引来实现加速。
    楼主自己想到了将 B 转为 K-V 形式这就相当于 hash 索引,时间复杂度为 O(n)。
    当然可以将 B 做成其他的数据结构,比如平衡树等。
    owenliang
        4
    owenliang  
       2018-05-02 17:52:17 +08:00
    你得说说业务场景,脱离业务谈算法感觉不太对劲。
    davinci
        5
    davinci  
       2018-05-02 19:19:21 +08:00
    如果内存存的下两个百万集合,直接 hash。如果两个集合都大到内存放不下,可以参考数据库的 hash join 实现。
    1cming
        6
    1cming  
    OP
       2018-05-02 20:25:45 +08:00
    @glacer 好的谢谢我看一下

    @owenliang 业务场景是特意模糊掉的

    @davinci 内存放的下
    shoumu
        7
    shoumu  
       2018-05-02 20:49:57 +08:00
    A、B 集合分别以 ID 进行排序,然后从头到位遍历 Join 即可
    jorneyr
        8
    jorneyr  
       2018-05-03 08:56:13 +08:00
    Hash 的方式可以的,百万不算多
    buliugu
        9
    buliugu  
       2018-05-03 19:11:26 +08:00
    bitmap 了解一下
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3334 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 13:25 · PVG 21:25 · LAX 06:25 · JFK 09:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.