매우 큰 튜플 목록의 부분 일치 목록

Question

저는 파이썬에 초보자입니다. 여기서 멋진 토론을 위해 모두에게 감사해야합니다. 그러나 나는 어떤 조언도 보지 못했습니다. (또는 내가 이해하기에는 너무 복잡했다.)

두 개의 목록 (튜플?)에 각각 약 백만 항목이 있습니다. 둘 다 첫 번째 항목 (단어)에 정렬되며 동일한 형식을 갖습니다. 각 목록에서 단어/페이지 조합은 고유합니다.

List1= [('word1', 'page1'), ('word1', 'page2'), ('word3', 'page1'),...] 
List2 = [('word1', 'page4'), ('word2', 'page2'), ('word3', 'page1'),...] 

list2에서도 발생하는 '단어'를 list1에서 찾아야합니다. 이 예제의 출력은 내가 지금 세트,리스트, 튜플, dicts와 완전히 혼란 스러워요 너무 많이 찾아 봤는데

[('word1', 'page1'), ('word1', 'page2'), ('word1', 'page4'),('word3','page1')] 

해야한다 ... 나는 루프를 할 아마 수 있지만 보인다 여기 어딘가에서 더 나은 선택입니다.

Answer 1

나는 생각이 당신의 범위를 달성하기 위해 많은 방법을. 데이터가 실제로 크기 때문에 성능을 고려하여 시간, 공간 또는 실적을 고려해야합니다. 다음은 예제입니다.

#!/usr/bin/python 
#-*- coding:utf-8 -*- 

L1 = [('word1', 'page1'), ('word1', 'page2'), ('word3', 'page1'), ] 
L2 = [('word1', 'page4'), ('word2', 'page2'), ('word3', 'page2'), ] 

def func1(): 
    ''' 
    Time Complexity is O(n^2) 
    ''' 
    res = [] 
    for i in L1: 
     for k in L2: 
      if i[0] == k[0]: 
       res.append(i) 
       res.append(k) 
    return list(set(res)) 

def func2(): 
    ''' 
    Time Complexity is O(n) 
    ''' 
    d1 = {} 
    for i in L1: 
     if d1.has_key(i[0]): 
      d1[i[0]].append(i[1]) 
     else: 
      d1[i[0]] = [i[1]] 
    d2 = {} 
    for i in L2: 
     if d2.has_key(i[0]): 
      d2[i[0]].append(i[1]) 
     else: 
      d2[i[0]] = [i[1]] 
    d3 = {} 
    for key in d1.keys(): 
     if d2.has_key(key): 
      d3[key] = d2[key] + d1[key] 

    return [(m,n) for m in d3.keys() for n in d3[m]] 



if __name__ == '__main__': 
    print func1() 
    print func2() 

    import timeit 
    t = timeit.Timer(func1) 
    print t.timeit(10000) 
    t = timeit.Timer(func2) 
    print t.timeit(10000) 

Answer 2

단어를 페이지에 매핑해야하는 경우 단어를 페이지에 매핑하는 데 사용할 수 있습니다.

from collections import defaultdict 
word_pages_1 = defauldict(list) 
for w, p in List1: 
    word_pages_1[w].append(p) 

당신은 다음

Answer 3

외모가 빅 데이터 문제처럼 그들 사이의 비교에 대한 귀하의 DICT 키에 대한 설정 작업을 수행 할 수 있습니다. numpy 및 pandas과 같은 특정 도구를 사용할 수 있습니다. 당신은 메모리에 데이터를 모두 맞게 충분한 RAM이있는 경우, 그것은 numpy으로 수행 할 수 있습니다

In [103]: 
import numpy as np 
List1= [('word1', 'page1'), ('word1', 'page2'), ('word3', 'page1')] 
List2 = [('word1', 'page4'), ('word2', 'page2'), ('word3', 'page1')] 

In [104]: 
arr1 = np.array(List1) 
arr2 = np.array(List2) 

In [105]: 
arr3=np.vstack((arr1, arr2)) #stack two dataset together 
arr3 

Out[105]: 
array([['word1', 'page1'], 
     ['word1', 'page2'], 
     ['word3', 'page1'], 
     ['word1', 'page4'], 
     ['word2', 'page2'], 
     ['word3', 'page1']], 
     dtype='|S5') 

In [106]: 
np.in1d(arr3[:,0], arr1[:,0]) 
#for each item in arr3, is the first value appears in the 1st position of arr1? 

Out[106]: 
array([ True, True, True, True, False, True], dtype=bool) 

In [107]: 
arr3[np.in1d(arr3[:,0], arr1[:,0])] #Boolean indexing 

Out[107]: 
array([['word1', 'page1'], 
     ['word1', 'page2'], 
     ['word3', 'page1'], 
     ['word1', 'page4'], 
     ['word3', 'page1']], 
     dtype='|S5') 

In [108]: 
set(map(tuple, arr3[np.in1d(arr3[:,0], arr1[:,0])])) 

Out[108]: 
{('word1', 'page1'), 
('word1', 'page2'), 
('word1', 'page4'), 
('word3', 'page1')}