mzh/blog

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上的解答

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

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