搜索大型数据集

我有一个用户列表：朋友（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

搜索大型数据集

回答

相关问题