0

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 ?

4
  • How does [(2, 3), (3,4)] mean user 3 follows user 2? Mar 4, 2014 at 2:07
  • @user2357112: it is the result; as the main list contains both (2,3) and (3,2) the result got (2,3); same for (3,4)
    – mshsayem
    Mar 4, 2014 at 2:10
  • Oh, the (3, 4) is a separate result. The description seems to imply that the (2, 3) means 2 follows 3 and the (3, 4) means 3 follows 2. Mar 4, 2014 at 2:11
  • This algorithm runs in linear time. It's possible to get a decent constant factor speedup, but if you need anything dramatic, it'll probably require reworking some other aspect of the code. Mar 4, 2014 at 2:11

1 Answer 1

2

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
2
  • Your timing results favor the set-based algorithm much more than mine did. It looks like your input was a lot smaller than what I timed it on. I wonder what caused the effect. Mar 4, 2014 at 2:38
  • I use IPython + CPython for timing, I had no idea why it's six time faster not two...
    – Zhuo.M
    Mar 4, 2014 at 7:07

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.