搜索大型數據集

我有一個用戶列表：朋友（50,000）和一個事件參加者列表（每個事件25,000個事件和參加者列表）。我想找到用戶前往參加活動的頂級k朋友。這需要爲每個用戶完成。搜索大型數據集

我試過遍歷列表，但在計算上非常昂貴。（Python）

讓我知道是否有任何其他的方法。

來源

2013-02-12 Jack

爲什麼不將數據轉儲到一個數據庫，然後查詢呢？這是數據庫的用途，並且已經針對它進行了優化。 – Hyperboreus 2013-02-12 05:53:20

好的。謝謝。我會嘗試一下樣本數據並查看性能 – Jack 2013-02-12 06:03:01

@Hyperboreus我不確定將事情複製到磁盤並重新讀取它們可以稱爲優化或曾經被認爲是加速算法的一種方式。 – NotAUser 2013-02-12 11:36:22

我建議你在數據庫（例如sqlite）或純python，內存中選項中執行該操作，請參閱norman。無論哪種方式比嘗試用列表自己實現這個要快得多。

來源

2013-02-12 05:54:45 aquavitae

好的。感謝您的建議 – Jack 2013-02-12 06:04:41

你能做這樣的事情嗎？我假設用戶的朋友相對較少，並且特定用戶參與的事件也比事件的總數少得多。

因此，爲用戶的每個朋友都有一個參加事件的布爾向量。

做一個點積和那些有最大值將是最有可能類似於用戶的朋友。

再次說明，在你做這件事之前，你必須過濾一些事件來保持你的向量的大小可以管理。

來源

2013-02-12 06:07:15 smk

我會給你一個代碼示例，如果我更好地理解你當前的數據結構是什麼樣子的，但是這聽起來像是一個熊貓數據框組的工作（如果你不想使用其他數據庫已建議）。

來源

2013-02-12 07:37:52

我有兩個csv文件。 1 -usr_frnds.csv其中包含兩列：用戶和朋友。用戶是用戶的ID，朋友是用戶朋友的空格分隔列表。 2- event_attendees.csv有列event_id，是的。 event_id標識事件。 yes是空格分隔的用戶標識列表。我也在研究熊貓數據框。感謝您的建議 – Jack 2013-02-12 08:47:43

Python的集合對象（字典，集合和collections.Counter）使這一任務的短期工作：

from collections import Counter 

def top_k_friends(friends, events, k=2): 
    '''Given a dictionary users mapped to their set of friends 
    and a dictionary of events mapped to a set of their attendees, 
    find the top k friends with whom the user goes to the event. 
    Do this for each user. 

    ''' 
    for user, users_friends in friends.iteritems(): 
     c = Counter() 
     for event, attendees in events.iteritems(): 
      if user in attendees: 
       c.update(users_friends.intersection(attendees)) 
     print user, '-->', c.most_common(k) 

if __name__ == '__main__': 

    friends = { 
     'robert' : {'mary', 'marty', 'maggie', 'john'}, 
     'paul' : {'marty', 'mary', 'amber', 'susan'} 
    } 

    events = { 
     'derby': {'amber', 'mary', 'robert'}, 
     'pageant': {'maggie', 'paul', 'amber', 'marty', 'john'}, 
     'fireworks': {'susan', 'robert', 'marty', 'paul', 'robert'} 
    } 

    top_k_friends(friends, events)

來源

2013-02-12 09:02:29

感謝您的示例代碼。 – Jack 2013-02-12 10:18:49

最差情況下的複雜度：O（用戶^ 3 *事件）。非常糟糕，但平均而言，朋友和參與者的數量將遠遠低於總用戶數量。 – NotAUser 2013-02-12 11:41:52

搜索大型數據集

回答

相關問題