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

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

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

    前提: 假设有 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
        1
    kingname   2018-05-02 15:39:54 +08:00 via iPhone
    你知道集合是可以求交集的吗?你直接求 A 与 B 的交集就可以了。
        2
    zn   2018-05-02 15:49:04 +08:00
    要看你的实现了,如果遍历速度、定位速度足够快,那就直接遍历,就是这样么简单粗暴。
        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 做成其他的数据结构,比如平衡树等。
        4
    owenliang   2018-05-02 17:52:17 +08:00
    你得说说业务场景,脱离业务谈算法感觉不太对劲。
        5
    davinci   2018-05-02 19:19:21 +08:00
    如果内存存的下两个百万集合,直接 hash。如果两个集合都大到内存放不下,可以参考数据库的 hash join 实现。
        6
    1cming   2018-05-02 20:25:45 +08:00
    @glacer 好的谢谢我看一下

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

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