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

This topic created in 3112 days ago, the information mentioned may be changed or developed.

前提：假设有 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 去判断是否存在。

objecty

objectx

集合

step2

9 replies • 2018-05-03 19:11:26 +08:00

kingname

May 2, 2018 via iPhone

你知道集合是可以求交集的吗？你直接求 A 与 B 的交集就可以了。

May 2, 2018

要看你的实现了，如果遍历速度、定位速度足够快，那就直接遍历，就是这样么简单粗暴。

glacer

May 2, 2018

参考 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

May 2, 2018

你得说说业务场景，脱离业务谈算法感觉不太对劲。

davinci

May 2, 2018

如果内存存的下两个百万集合，直接 hash。如果两个集合都大到内存放不下，可以参考数据库的 hash join 实现。

1cming

May 2, 2018

@glacer 好的谢谢我看一下

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

@davinci 内存放的下

shoumu

May 2, 2018

A、B 集合分别以 ID 进行排序，然后从头到位遍历 Join 即可

jorneyr

May 3, 2018

Hash 的方式可以的，百万不算多

buliugu

May 3, 2018

bitmap 了解一下

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

前提： 假设有 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 去判断是否存在。

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

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