python - 在大型数据集中搜索

Question

我有一个用户列表：朋友（50,000）和一个活动参与者列表（25,000 个活动和每个活动的参与者列表）。我想找到用户参加活动的前 k 个朋友。这需要为每个用户完成。

我尝试遍历列表，但计算成本非常高。我也试图通过创建加权图来做到这一点。（Python）

让我知道是否有其他方法。

Answer 1

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)

Answer 2

我建议您在数据库（例如sqlite）中执行此操作，或者对于纯 python 内存选项，请参阅norman。无论哪种方式都比尝试使用列表自己实现这一点要快得多。

Answer 3

你能做这样的事情吗。

我假设用户的朋友相对较少，并且特定用户参加的活动也远少于活动总数。

因此，对于用户的每个朋友，都有一个参加事件的布尔向量。

做一个点积和那些有最大值的将是最有可能与用户相似的朋友。

再次，.在你这样做之前..你将不得不过滤一些事件以保持你的向量的大小是可管理的。

Answer 4

如果我更好地理解您当前的数据结构是什么样子，我会给您一个代码示例，但这听起来像是熊猫数据框 groupby 的工作（以防您不喜欢像其他人建议的那样实际使用数据库）。