请教一个PHP的交集算法

我现在需要在已知的两个数组中找出他们的交集，业务关系是：

假设有个白名单用户表member_table
我关注的用户表follow_table
follow_table中的数据可能包含member_table的数据

举个例子：

 //白名单
 $member_table = [5,6,10,11];
 //我关注的用户
 $follow_table = [1,2,3,4,5,6,7,8,9];
 //我需要显示的数据
 $result = [5,6]

这个例子中最简单的方案就是array_intersect, 整个实现就是穷举，大概N^3左右，小数据量还好

而我们实际业务是follow_table可大可小，看用户自己想关注多少了，可能是100，也可能关注1000多个

不过member_info是一直在快速增长的，可能今天是1W，明天到10W，过两个月几百万都有可能的

基本上 member_info到 10W的时候时间上不说，空间上就直接Allowed memory size of了，要是并发在高一点，应该就直接挂了。每次请求动态计算我感觉不是太靠谱，所以想请教下，有没有什么最优方案

算法 php

阅读 4.1k

5 个回答

phper_李sir

✓ 已被采纳

这你完全可以交给redis去做！redis里面有
应用场景：

Redis set对外提供的功能与list类似是一个列表的功能，特殊之处在于set是可以自动排重的，当你需要存储一个列表数据，又不希望出现重复数据时，set是一个很好的选择，并且set提供了判断某个成员是否在一个set集合内的重要接口，这个也是list所不能提供的。

Sets 集合的概念就是一堆不重复值的组合。利用Redis提供的Sets数据结构，可以存储一些集合性的数据，比如在微博应用中，可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合。Redis还为集合提供了求交集、并集、差集等操作，可以非常方便的实现如共同关注、共同喜好、二度好友等功能，对上面的所有集合操作，你还可以使用不同的命令选择将结果返回给客户端还是存集到一个新的集合中。

实现方式：

set 的内部实现是一个 value永远为null的HashMap，实际就是通过计算hash的方式来快速排重的，这也是set能提供判断一个成员是否在集合内的原因。

参考：
http://www.cnblogs.com/si812c...