파이썬에서 조건과 일치하지 않는 목록에서 요소를 추출하는 가장 빠른 방법

Question

가장 빠른 방법을 사용하여 조건에서 목록의 모든 튜플 구성원을 추출합니다.

예 : 튜플 목록에서 (예 : [(0,0,4), (1,0,3), (1,2,1), (4,0,0)]) 첫 번째 튜플 위치에 3 개 이상, 두 번째 튜플 위치에 2 개 이상, 마지막 튜플 위치에 1 개 이상있는 모든 멤버를 추출합니다. 이 예 (4,0,0) (-> 첫 번째 조건), 아무 것도 (-> 두 번째 조건) 및 (0,0,4), (1,0,3) (-> 마지막 조건) . 이 예제는 매우 작기 때문에 수천 개의 튜플 목록에서이를 수행해야합니다. 에밀 Vikström에 의해 제안 된 같은

my_naive1 : 나는 당신의 대답에서 생성 된 코드에서

, 여기 초에서의 결과는? 13.0360000134

my_naive2 110.727999926

팀 Pietzcker 9.8329999446

돈 12.5640001297

import itertools, operator, time, copy 
from operator import itemgetter 


def combinations_with_replacement_counts(n, r): #(A, N) in our example.N individuals/balls in A genotypes/boxes 
    size = n + r - 1 
    for indices in itertools.combinations(range(size), n-1): 
     #print indices 
     starts = [0] + [index+1 for index in indices] 
     stops = indices + (size,) 
     yield tuple(map(operator.sub, stops, starts)) 


xp = list(combinations_with_replacement_counts(3,20)) # a very small case 

a1=time.time() 
temp=[] 
for n in xp: 
    for n1 in xp: 

     for i in xp: 
      if i[0] <= min(n1[0],n[0]) or i[1] <= min(n1[1],n[1]) or i[2] <= min(n1[2],n[2]): 
       temp.append(i) 


a2=time.time() 
for n in xp: 
    for n1 in xp: 
     xp_copy = copy.deepcopy(xp) 
     for i in xp: 
      if i[0] > min(n[0],n[0]) or i[1] > min(n[1],n[1]) or i[2] > min(n[2],n[2]): 
       xp_copy.remove(i) 

a3=time.time() 
for n in xp: 
    for n1 in xp: 
     output = [t for t in xp if t[0]<=min(n[0],n[0]) or t[1]<=min(n[1],n[1]) or t[2]<=min(n[2],n[2])] 
a4=time.time() 

for n in xp: 
    for n1 in xp: 
     l1 = sorted(xp, key=itemgetter(0), reverse=True) 
     l1_fitered = [] 
     for item in l1: 
      if item[0] <= min(n[0],n[0]): 
       break 
      l1_fitered.append(item) 

     l2 = sorted(l1_fitered, key=itemgetter(1), reverse=True) 
     l2_fitered = [] 
     for item in l2: 
      if item[1] <= min(n[1],n[1]): 
       break 
      l2_fitered.append(item) 

     l3 = sorted(l2_fitered, key=itemgetter(2), reverse=True) 
     l3_fitered = [] 
     for item in l3: 
      if item[2] <= min(n[2],n[2]): 
       break 
      l3_fitered.append(item) 
a5=time.time()    



print "soluce my_naive1, like proposed by Emil Vikström?",a2-a1 
print "soluce my_naive2",a3-a2 
print "soluce Tim Pietzcker",a4-a3 
print "soluce Don",a5-a4 

Answer 1

>>> l = [(0,0,4), (1,0,3), (1,2,1), (4,0,0)] 
>>> output = [t for t in l if t[0]>3 or t[1]>2 or t[2]>1] 
>>> output 
[(0, 0, 4), (1, 0, 3), (4, 0, 0)] 

이 빠르다. 그래서 귀하의 예제 목록에서, 단 8 비교가 필요합니다.

당신은 시간과 메모리 대신 발전기 표현 사용하는 경우 (필터링 된 데이터와 함께 무슨 일을하는지에 따라) 저장할 수

:

>>> l = [(0,0,4), (1,0,3), (1,2,1), (4,0,0)] 
>>> for item in (t for t in l if t[0]>3 or t[1]>2 or t[2]>1): 
>>>  # do something with that item 

Answer 2

각 정렬 세 목록, 각 조건에 대해 하나, 및 루프에 대한 설정의 입력을 통해 바로 루프를 가지고 튜플을 올바른 대상 목록에 추가하십시오. 이것은 O (n) (선형) 시간에 수행되며,이 문제에 대한 가능한 가장 빠른 점근 시간입니다. 또한 한 번만 목록을 반복합니다. t[1]>2만을 평가 때문에 t[0]>3는 (제 동일한 조건) False 경우

Answer 3

당신이 결과 항목의 순서를 상관하지 않는 경우를, I 첫 번째 일치하지 않는 항목의 중단 조건을 사용하여 정렬 된 목록에서 조회를 제안하십시오. 목록 꼬리를 건너 뜁니다.

from operator import itemgetter 
l = [(..., ..., ...), (...)] 
l1_source = sorted(l, key=itemgetter(0), reverse=True) 
l1_fitered = [] 
for item in l1: 
    if item[0] <= 3: 
     break 
    l1_fitered .append(item) 

l2 = sorted(l, key=itemgetter(1), reverse=True) 
...