Python如何查找Follow关系

Twitter中Follower和Followee,现需要找到互相关注的两个人(不关心顺序) 例如:现有列表

 l = [(1, 2), (2, 3), (3, 2), (3, 4), (4, 1),
(4, 3), (4, 3)]

可以通过下列函数生成

def gen_pairs():
return (random.randint(0, 30), random.randint(0, 30))
l = [gen_pairs() for x in xrange(20)]

解法一:

import collections
[x for x, y in collections.Counter([tuple(sorted(x)) for x in l]).iteritems() if y > 1]
  1. [tuple(sorted(x)) for x in l] 首先是将列表的内容按小到大重新排列
  2. 通过计数器collections.Counter,来统计重复的数量
  3. if y > 1 将大于一个的放入结果集中

最后统计用时best of 3: 38.9 µs per loop 老湿,还能给力点吗? 解法二:
[Stackover上的解答](http://stackoverflow.com/questions/22161370/algorithm-to-find-
follow-relationship-like-twitter/22161585#22161585 “Stackover上的解答” )

[x for x in set_l if x[::-1] in set(l)]

快了6倍……答主说到这个算法最快也就是O(n)了,因为必须遍历所有项有木有啊!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据