判断集合1中的元素是否包含集合2中的某个元素

坚持_执着 发布于 2014/01/19 01:52
阅读 1K+
收藏 0

云原生2.0展望丨从“小众”到“首选”,推动云原生产业落地华为云作用几何?>>>

如题,现在有2个集合,集合1的内容类似于:

无间道1爱奇艺

爱奇艺视频

优酷

让子弹飞优酷

集合2的内容类似于:

无间道1

让子弹飞

宫锁沉香

对于集合1中的每个元素elem1,判断elem1是否包含集合2中的某个元素,像上面的这个例子,

“无间道1爱奇艺”和“让子弹飞优酷”是需要获取的,因为“无间道1爱奇艺”包含集合2中的“无间道1”,“让子弹飞优酷”包含集合2中的“让子弹飞


问题是,集合1的元素数量在4万,集合2的元素数量在12万,如果用两层循环,会导致计算量非常大,请问大家,是否有更高效的解决方案呢?

加载中
0
locusxt
locusxt

试试"压缩patricia树".
对集合1建一棵压缩patricia树,改写成类似ac自动机的形式,再对集合2中的元素逐个查询.

0
281165273
281165273
这个用hash类的方式不好处理吧,他这个是个模糊匹配
0
KDash
KDash
布隆过滤器(稍有误差)或者hash都能很好的解决问题。二楼也是不错的思路,排序下利用分半查找。
0
中山野鬼
中山野鬼

引用来自“chyxion”的答案

JavaScript么?这么大的数据,恐怕不太好处理,这样的话可以服务器端处理,服务器端处理,可以用空间换时间,把所有元素存入Map,查找比较就相当容易啦,哈。

这是数学问题,哈,和语言关系不是很大


SuperShaunChyxion
SuperShaunChyxion
亲,JavaScript处理12万条数据。
0
坏孩子
坏孩子
先排序,然后从集合1取一个到集合2里面顺序找,因为排过序了,所以有两种情况,找到和没找到,无论什么情况再从集合2的这个位置去一个元素从集合1的第二个元素开始找。大概就是这样的,如果我没记错的话
0
SuperShaunChyxion
SuperShaunChyxion

JavaScript么?这么大的数据,恐怕不太好处理,这样的话可以服务器端处理,服务器端处理,可以用空间换时间,把所有元素存入Map,查找比较就相当容易啦,哈。

返回顶部
顶部