효율적인 튜플 목록 비교

Question

저는이 문제에 대해 벽을 치고 있습니다. 신선한 두뇌가 나를 도울 수 있는지 궁금합니다.

내가 형식의 네 가지 요소 튜플의 큰 목록이 있습니다

(ID 번호, 종류, 시작 인덱스, 끝 색인) 코드에서 이전

을, 나는 블록의 수천을 통해 검색 한 두 가지 특정 유형의 하위 문자열에 대한 텍스트 이 튜플은 텍스트의 큰 덩어리에 부분 문자열이 있는지, 두 가지 유형의 부분 문자열 중 어디에 있는지,이 하위 문자열의 시작 및 끝 인덱스가 저장됩니다.

최종 목표는이 목록을 살펴보고 동일한 ID가있는 텍스트 블록의 유형 2 부분 문자열 앞에 유형 1 부분 문자열이있는 모든 인스턴스를 찾는 것입니다. 그런 다음이 오브젝트를 ID, 유형 1, 시작, 끝, 유형 2, 시작, 끝의 형식으로 저장하려고합니다.

저는 비효율적 인 많은 자료를 가지고 혼란스럽게 노력했습니다. ID로 정렬 한 다음 시작 인덱스를 정렬 한 목록을 비교 목록에서 제외하여 다양한 방법으로 시도한 경우. 나는 더 우아한 해결책이 있다고 상상해야한다. 거기 밖으로 어떤 화려한 사람들은 내 피곤한 두뇌를 돕고 싶다 ??? 사전에

감사

Answer 1

솔루션 :

result = [(l1 + l2[1:]) 
      for l1 in list1 
      for l2 in list2 
      if (l1[0] == l2[0] and l1[3] < l2[2]) 
      ] 

... 테스트 코드 :

list1 = [(1, 'Type1', 20, 30,), 
     (2, 'Type1', 20, 30,), 
     (3, 'Type1', 20, 30,), 
     (4, 'Type1', 20, 30,), 
     (5, 'Type1', 20, 30,), 
     (6, 'Type1', 20, 30,), # does not have Type2 

     (8, 'Type1', 20, 30,), # multiple 
     (8, 'Type1', 25, 35,), # multiple 
     (8, 'Type1', 50, 55,), # multiple 
     ] 

list2 = [(1, 'Type2', 40, 50,), # after 
     (2, 'Type2', 10, 15,), # before 
     (3, 'Type2', 25, 28,), # inside 
     (4, 'Type2', 25, 35,), # inside-after 
     (4, 'Type2', 15, 25,), # inside-before 
     (7, 'Type2', 20, 30,), # does not have Type1 

     (8, 'Type2', 40, 50,), # multiple 
     (8, 'Type2', 60, 70,), # multiple 
     (8, 'Type2', 80, 90,), # multiple 
     ] 

result = [(l1 + l2[1:]) 
      for l1 in list1 
      for l2 in list2 
      if (l1[0] == l2[0] and l1[3] < l2[2]) 
      ] 

print '\n'.join(str(r) for r in result) 

그런 다음 더있을 경우 당신이 원하는 어떤 결과 명확하지 않다 동일한 텍스트 ID 내에 Type1과 Type2가 모두 하나씩 나타납니다. 명시 해주세요.

Answer 2

귀하의 유형이 몇 개인 지 잘 모릅니다. 그러나 유형 1과 유형 2 만 있다고 가정하면 병합 정렬과 비슷한 문제 인 것처럼 들립니다. 병합 정렬을 사용하면 목록을 한 번 통과하게됩니다.

유형 1과 유형 2 (I1, I2)의 두 가지 색인을 사용하십시오. id, start1로 목록을 정렬하십시오. type1의 첫 번째 인스턴스로 I1을 시작하고 0으로 I2를 시작합니다. I1.id < I2.Id이면 I1을 증가시킵니다. I2.id < I1.id이면 I2를 증가시킵니다. I1.id = I2.id 인 경우 iStart를 선택하십시오.

I1은 유형 1 레코드에서만 중지 할 수 있고 I2는 유형 2 레코드에서만 중지 할 수 있습니다. 인덱스가 적절한 레코드에 도달 할 때까지 계속 증가시킵니다.

이 작업을 더 빠르게 수행 할 수 있습니다. 성공한 블록을 찾으면 I1을 다음 블록으로 이동할 수 있습니다. I2 < I1이있을 때마다 I1 + 1에서 I2를 시작할 수 있습니다. (우물은 실패 할 것입니다. 왜냐하면 실패 사례가 있기 때문에!) 명백한 실패 사례를 발견 할 때마다 I1과 I2를 다음 블록으로 이동하십시오 (적절한 경우 물론 recs).

Answer 3

나는 최근에 이렇게했습니다. 나는 당신의 문제를 이해하지 못할 수도 있지만 여기에 간다.

from collections import defaultdict: 
masterdictType1=defaultDict(dict) 
masterdictType2=defaultdict(dict) 


for item in myList: 
    if item[1]=Type1 
     if item[0] not in masterdictType1: 
      masterdictType1[item[0]]['begin']=item[2] # start index 
      masterdictType1[item[0]]['end']=item[-1] # end index 
    if item[1]=Type2 
     if item[0] not in masterdictType2: 
      masterdictType2[item[0]]['begin']=item[2] # start index 
      masterdictType2[item[0]]['end']=item[-1] # end index 

joinedDict=defaultdict(dict) 

for id in masterdictType1: 
    if id in masterdictType2: 
     if masterdictType1[id]['begin']<masterdictType2[id]['begin']: 
      joinedDict[id]['Type1Begin']=masterdictType1[id]['begin'] 
      joinedDict[id]['Type1End']=masterdictType1[id]['end'] 
      joinedDict[id]['Type2Begin']=masterdictType2[id]['begin'] 
      joinedDict[id]['Type2End']=masterdictType2[id]['end'] 

이것은 당신이 명확성 제공하고 당신에게 당신이 쉽게 사전을 피클 수 있기 때문에 내구성이 뭔가를 제공합니다

나는 사전을 사용합니다.각 ID에 대한 항목이 많이가있는 가정

Answer 4

나는 것 (의사 코드)

 
    for each ID: 
     for each type2 substring of that ID: 
      store it in an ordered list, sorted by start point 
     for each type1 substring of that ID: 
      calculate the end point (or whatever) 
      look it up in the ordered list 
      if there's anything to the right, you have a hit 

그래서, 당신은 초기 종류의 제어, 다음 대신 (ID 시작,), 당신이 원하는의이있는 경우 ID별로 정렬 한 다음 유형별로 정렬합니다 (2 이전은 1). 그런 다음 유형 내에서 type2의 시작점별로 정렬하고 type1에 ​​대해 비교할 오프셋을 지정하십시오. 나는 "A 앞에 B"가 "B가 시작되기 전에 시작"또는 "A가 B가 시작되기 전에 끝남"을 의미하는지 여부는 모르지만 적절한 것은 수행합니다.

그런 다음 목록을 한 번 실행하여 전체 작업을 수행 할 수 있습니다. 이미 순서대로되어 있기 때문에 type2의 인덱스를 실제로 생성 할 필요가 없습니다. type1도 정렬되기 때문에 이전 검색 결과에서 시작하는 선형 또는 2 진 검색을 사용하여 각 조회를 수행 할 수 있습니다. type2s와 비교하여 type1이 많이 (그래서 결과가 가깝다), type1s와 비교하여 type2가 많이있는 경우 이진 검색을 사용하면 선형 검색을 사용합니다 (결과가 희박합니다). 또는 선형 검색을 사용하는 것이 더 간단 할뿐입니다.이 조회는 내부 루프이지만 성능은 중요하지 않을 수도 있습니다.

정렬을 제어 할 수 없다면 이동하면서 각 ID에 대해 type2 하위 문자열 목록을 만드는 것이 더 빠를 지 모르겠습니다. 또는 필요한 순서로 시작하기 전에 전체 목록을 정렬 할 수 있습니다. type2를 통해 검색 할 때 type1 항목을 무시하는 "조회"를 작성하여 (필요한 경우 이미 정렬되어있는) 사용자가 가지고있는 것을 사용하기 만하면됩니다. 테스트 해보거나 더 명확한 코드로 결과를 얻으십시오. 다시 정렬하지 않고도 "시작 인덱스로 정렬"이 type1에 ​​대해 잘못된 경우가 아니면 병합 스타일 최적화를 계속 사용할 수 있습니다.

Answer 5

나는 t1_a, t2_b, t2_c, t2_d 그냥 쌍 (t1_a, t2_b)를 제공해야합니다. 당신은 (즉, 이전 즉시을 의미합니까, 전에 에 의해 확인, 또는 당신이 타입 1의 값이 타입 2 일 내에 전에 어디 발생하는 모든 쌍을하고자 할 수 같은 블록. (앞의 예를 들면, 즉 (t1_a, t2_b), (t1_a, t2_c), (t1_a, t2_d)). 어느 경우

, 당신은 당신의 목록을 통해 하나의 패스로이 작업을 수행 할 수 있어야한다 (다음 인덱스를 시작 ID로 분류 가정).

여기에 가정이있다. 그냥 직전이라면

import itertools, operator 

def find_t1_t2(seq): 
    """Find every pair of type1, type2 values where the type1 occurs 
    before the type2 within a block with the same id. 

    Assumes sequence is ordered by id, then start location. 
    Generates a sequence of tuples of the type1,type2 entries. 
    """ 
    for group, items in itertools.groupby(seq, operator.itemgetter(0)): 
     type1s=[] 
     for item in items: 
      if item[1] == TYPE1: 
       type1s.append(item) 
      elif item[1] == TYPE2: 
       for t1 in type1s: 
        yield t1 + item[1:] 

, 그것도 간단 : 두 번째 옵션 (모든 쌍)을 보내고 단지 이전 항목을 추적하고 타입 1이며, 현재는 타입 2 때마다 튜플을 얻을 수 있습니다.

다음은 사용의 예, 그 결과를 반환

l=[[1, TYPE1, 10, 15], 
    [1, TYPE2, 20, 25], # match with first 
    [1, TYPE2, 30, 35], # match with first (2 total matches) 

    [2, TYPE2, 10, 15], # No match 
    [2, TYPE1, 20, 25], 
    [2, TYPE1, 30, 35], 
    [2, TYPE2, 40, 45], # Match with previous 2 type1s. 
    [2, TYPE1, 50, 55], 
    [2, TYPE2, 60, 65], # Match with 3 previous type1 entries (5 total) 
    ] 

for x in find_t1_t2(l): 
    print x 

이 반환

[1, 'type1', 10, 15, 'type2', 20, 25] 
[1, 'type1', 10, 15, 'type2', 30, 35] 
[2, 'type1', 20, 25, 'type2', 40, 45] 
[2, 'type1', 30, 35, 'type2', 40, 45] 
[2, 'type1', 20, 25, 'type2', 60, 65] 
[2, 'type1', 30, 35, 'type2', 60, 65] 
[2, 'type1', 50, 55, 'type2', 60, 65]