Самый быстрый способ извлечь элементы из списка, который не соответствует условию в Python

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) (-> последнее условие). Этот пример очень маленький, мне нужно выполнить это в списке из тысяч кортежей.

Из кода, который я создал из ваших ответов, результаты в секундах:

my_naive1, как предложено Эмилем Викстрёмом? +13,0360000134

my_naive2 110.727999926

Тим Пицкер 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)]

Это быстро, потому что t[1]>2 оценивается, только если t[0]>3 равно False (то же самое для третьего условия). Таким образом, в вашем списке примеров необходимо только 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

Имеет три списка, по одному для каждого условия, и просто циклически перебирает входной набор с циклом for, сортируя каждый кортеж в правильный список целей.Это будет выполнено за O (n) (линейное) время, которое является максимально быстрым асимптотическим временем выполнения для этой задачи.Он также будет зацикливаться на списке только один раз.

Answer 3

Если вам не важен порядок получаемых элементов, я предлагаю поиск в отсортированном списке с условием разрыва для первого несовпадающего элемента: это пропустит хвосты списка.

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)
...