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 实现。
|
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 了解一下
|