어떻게 파이썬에서 중복 행을 효율적으로 필터링 할 수 있습니까?

Question

내 질문에 고전적인 것처럼 보이지만 정확히 stackoverflow에서 동일한 질문을 찾을 수 없습니다. 나는 내 질문이 중복 된 질문이 아니기를 바랍니다.

큰 파일이 있습니다. 파일에는 많은 행과 고정 열이 있습니다. 나는 모든 열 중에서 열 A와 열 B에 관심이 있습니다. 목표는 (1) 행의 A 열의 값이 다른 행에도 나타나고 (2) A 열과 동일한 값을 가진 행이 두 개 이상있는 행을 얻고 자하는 것입니다. B 열의 다른 값.

다음 표를 고려하십시오. 3 행에 "a"가 나타나고 B 열의 값이 다르기 때문에 행 1,3,5에 관심이 있습니다. 반대로 "b"가 두 번 나타나기 때문에 행 2와 4에는 관심이 없지만 B 열의 해당 값은 항상 "1"입니다. 마찬가지로 "c"가 한 번만 표시되기 때문에 행 6에도 관심이 없습니다.

# A B C D 
========= 
1 a 0 x x 
2 b 1 x x 
3 a 2 x x 
4 b 1 x x 
5 a 3 x x 
6 c 1 x x

는 객체와 각 라인을 변환, 내가 파일의 모든 라인을 읽고, 이러한 열을 찾을 개체에 대한 목록을 작성, 다음과 같은 알고리즘 흥미로운 열을 찾을 수 있습니다. 알고리즘은 작동하지만 내 데이터 세트에 시간이 걸립니다. 알고리즘을 효율적으로 만들 수있는 제안이 있습니까?

def getDuplicateList(oldlist): 
    # find duplicate elements 
    duplicate = set() 
    a_to_b = {} 
    for elements in oldlist: 
     a = elements.getA() 
     b = elements.getB() 
     if a in a_to_b: 
      if b != a_to_b[a]: 
       duplicate.add(a) 
     a_to_b[a] = b 

    # get duplicate list 
    newlist = [] 
    for elements in oldlist: 
     a = elements.getA() 
     if a in duplicate: 
      newlist.append(a) 

    return newlist

p.s. 나는 명확히하기 위해 몇 가지 제약 조건을 추가한다. 내가

나는 "모든 흥미로운 행을"필요 파이썬 2.7을 사용하고

1. : duplicate는 "일부"흥미로운 "A"의가 있습니다.
2. 순서가 중요합니다.
3. 실제로 데이터는 프로그램 실행의 메모리 액세스입니다. A 열에는 메모리 액세스가 있고 B 열에는 내가 관심있는 몇 가지 조건이 있습니다. 런타임에 메모리 액세스에 여러 조건이있는 경우 메모리 액세스 순서를 조사하고 싶습니다.

Answer 1

그럼 oldlist 내의 요소를 두 번 반복 한 번의 반복에 의해 대체 될 수있다. 나는 이것이 대부분의 경우 알고리즘의 효율성을 향상시킬 것이라고 믿습니다. 특히 긴 목록의 경우 더욱 그렇습니다.

newlist의 순서가 문제가되지 않는다면 알고리즘과 동일한 결과를 갖는 단일 루프 대체를 제안합니다. 나는 무작위로 생성 만 요소 목록에 대해 그것을 테스트하고 항상 약 절반의 시간 실행 : (. 아마 조건문 예뻐 할 수있다)

이

def new_getDuplicateList(oldlist): 
    # find duplicate elements 
    newlist = [] 
    duplicate = set() 
    a_to_b = {} 
    for elements in oldlist: 
     a = elements[0] 
     b = elements[1] 
     if a in duplicate: 
      newlist.append(a) 
     else: 
      if a in a_to_b.keys(): 
       if not b in a_to_b[a]: 
        a_to_b[a].append(b) 
        duplicate.add(a) 
        extension = [a for i in a_to_b[a]] 
        newlist.extend(extension) 
       else: 
        a_to_b[a].append(b) 
      else: 
       a_to_b[a] = [b] 

    return newlist 

을 출력 전체를 수정하는 것은 매우 쉬운 것입니다 행 대신에 a 값을 사용합니다. a을 (a, b)으로 바꿉니다. 또한 a_to_b dicts (첫 번째 알고리즘은 현재 목록을 보유하고 있기 때문에)보다 더 많은 메모리를 소비합니다.

Answer 2

원래 주문을 유지 관리해야합니까? 그렇지 않은 경우에는 groupby과 매우 유사하게 보이며 내장 메서드 사용으로 성능이 약간 향상 될 수 있습니다. 이 같은

아마도 뭔가 (테스트되지 않은!) :

는

s = sorted(oldlist, key=lambda e: (e.getA(), e.getB())) 
interesting = (g for k,g in itertools.groupby(s, lambda e: e.getA()) 
       if len(g) > 1) 

Answer 3

귀하의 복잡성은 이미 꽤 좋다. 당신은 여기서 선형 속도 향상을 찾고 있습니다.

두 번째 루프 대신 duplicate을 돌려 줄 수없는 이유가 있습니까?

else을 추가하면 a_to_b[a] = b이 이미있을 때 다시 삽입하지 않아도됩니다.

또한 디스크 I/O가 느리고 읽기를 기다리는 동안 CPU가 다른 작업에 사용할 수있는 시간이 많습니다. 이 작업을 많이해야하기 때문에 다른 스레드가 다음 파일을 읽는 동안 한 스레드에서 중복 된 파일을 찾으면 상당한 속도 향상을 얻을 수 있습니다.

Answer 4

다음은 매우 쉽습니다.흥미로운 행의 A 값을 산출합니다. 행을 산출하도록 수정 간단 할 것이다 :

는

def isInteresting(rows): 
    avals = {} 
    for row in rows: 
     bvals = avals.get(row.getA()) or set() 
     bvals.add(rowgetB()) 
     avals[row.getA()] = bvals 

    return [ aval 
      for aval in avals.keys() 
      if avals[aval] and len(avals[aval]) > 1 ] 

Answer 5

목록의 다른 항목에서 개체를 만들면 속도가 느려질 수 있습니다. 여기서는 collections 모듈을 사용하여 멀티 세트를 만들고 컨테이너 자체가 관련없는 항목을 분류하도록합니다. 이것이 어떻게 작동하는지보십시오. 위에서 준 정확한 파일 형식을 가정합니다.

import collections 

def get_interesting_items(filename): 
    multiset = collections.defaultdict(set) 

    with open(filename) as f: 
     # skip header lines 
     f.readline() 
     f.readline() 

     # add all B items to Bset, indexed by A 
     for line in f: 
      _, a, b, _ = line.split(' ', 3) 
      multiset[a].add(int(b)) 

     # generate all A, Bset pairs where Bset contains at least 2 items. 
     for a, bset in multiset.iteritems(): 
      if len(bset) >= 2: 
       yield a, bset 

def main(): 
    for a, bset in get_interesting_items('myfile.txt'): 
     print a, bset