算法找到跟隨Twitter等

關係了，我想算法找到跟隨Twitter等

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

名單，這意味着用戶1的後續用戶2，依此類推......

的目標是要找到像

列表

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

這意味着用戶2跟隨用戶3，反之亦然。

到目前爲止，我已經來到了，我認爲還是不夠快（Python編寫）

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

誰能告訴我一些更快的算法的一種方式？

來源

2014-03-04 Zhuo.M

如何'[（2,3），（3,4）]'意味着用戶3如下用戶2？ – user2357112

@ user2357112：這是結果;因爲主列表包含'（2,3）'和'（3,2）'，所以得到'（2,3）'; （3,4）' – mshsayem

相同哦，'（3，4）'是一個單獨的結果。這個描述似乎意味着'（2,3）'意味着2跟隨3，'（3，4）'意味着3跟隨2. – user2357112

您的算法在線性時間內運行。對於這個問題，這是最快的漸近運行時間，因爲任何解決此問題的算法都必須查看所有輸入。有可能獲得恆定的因子加速;例如，下面的代碼：

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

運行有點快兩倍像你當我火候好，但如果你需要重大改進，你可能需要研究改進程序的其他方面。

----運行時間----

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

來源

2014-03-04 02:20:47 user2357112

感謝您的回答。 –

你的計時結果比我的更喜歡基於集合的算法。看起來你的輸入比我的時間要小很多。我想知道是什麼造成了這種影響 – user2357112

我使用IPython + CPython進行計時，我不知道爲什麼它快六倍，而不是兩次... –

算法找到跟隨Twitter等

回答

相關問題