Algorithm to find follow relationship like Twitter

Question

I had a list like

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

which means user 1 follow user 2 and so on...

The goal is to find a list like

[(2, 3), (3,4)]

which means user 2 followed user 3 and vice verse.

So far, I had came up one way which I think is still not fast enough ( written in Python )

[x for x, y in collections.Counter([tuple(sorted(x)) for x in l]).iteritems() if y > 1]

Can anyone show me some faster algorithm ?

Answer 1

Your algorithm runs in linear time. That's the fastest asymptotic runtime possible for this problem, since any algorithm that solves it must look at all the input. It's possible to get a constant factor speedup; for example, this code:

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

runs a bit better than twice as fast as yours when I time it, but if you need major improvement, you may need to look at improving other aspects of your program.

----Run time----

In [125]: %%timeit
set_l = set(l);[x for x in set_l if x[::-1] in set_l]
   .....: 
100000 loops, best of 3: 6.26 µs per loop

In [126]: %%timeit
   .....: [x for x, y in collections.Counter([tuple(sorted(x)) for x in l]).iteritems() if y > 1]
   .....: 
10000 loops, best of 3: 39.3 µs per loop