큰 데이터 세트로 검색

Question

나는 user : friends (50,000) 목록과 이벤트 참석자 목록 (각 이벤트에 대한 25,000 개의 이벤트 및 참석자 목록)이 있습니다. 나는 사용자가 이벤트에가는 최고의 k 친구들을 찾고 싶다. 이것은 각 사용자에 대해 수행되어야합니다.

트래버스 목록을 시도했지만 계산 상 매우 비쌉니다. 나는 또한 가중 그래프를 작성하여 그것을 시도하고있다. (파이썬)

다른 접근법이 있다면 알려줘.

Answer 1

데이터베이스 (예 : sqlite) 또는 pure-python 인 메모리 옵션의 경우 norman을 참조하십시오. 어느 쪽이든 목록을 사용하여 직접 구현하는 것보다 훨씬 빠릅니다.

Answer 2

이렇게 할 수 있습니까?

사용자의 친구가 상대적으로 적고 특정 사용자가 참석 한 일정이 전체 일정 수보다 훨씬 적은 것으로 가정합니다.

그래서 사용자의 각 친구에 대해 참석 한 이벤트의 부울 벡터를가집니다.

내적을 수행하면 최대 사용자 수는 가장 유사 할 것입니다.

이 작업을하기 전에 벡터 관리가 가능한 크기를 유지하기 위해 일부 이벤트를 필터링해야합니다.

Answer 3

현재 데이터 구조가 어떻게 생겼는지 더 잘 이해하면 코드 샘플을 제공 하겠지만, 팬더 데이터 프레임 groupby의 작업처럼 들릴 수 있습니다 (실제로 다른 데이터베이스로 데이터베이스를 사용하고 싶지 않은 경우에 대비해). 제안했다).

Answer 4

파이썬의 수집 객체 (사전, 집합 및 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)