在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，像Emil Vikström提议的？13.0360000134秒

my_naive2 110.727999926秒

Tim Pietzcker 9.8329999446秒

Don 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

相关问题：

• 在Python中处理列表的列表并选择子列表
• Python生成带偏移和条件的子列表
• 列表中最长单词的长度
• 在Python中从字符串快速生成重叠子串列表的方法
• 如何在短的Python列表前添加元素？
• 在Python中高效生成百万元素的随机列表
• 根据搜索条件从Python数组中返回随机元素
• Python: 列表转整数

Answer 1

如果你不在乎结果的顺序，我建议你在一个已经排好序的列表中查找，并在遇到第一个不匹配的项时就停止查找：这样可以跳过列表后面的部分。

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

Answer 2

有三个列表，每个列表对应一种情况。你只需要用一个for循环遍历输入的数据，把每一组数据放到正确的目标列表里。这种方法的运行时间是O(n)，也就是线性的，这是解决这个问题最快的方式。而且，它只会遍历这个列表一次。

Answer 3

>>> 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[0]>3 为 False 的情况下，t[1]>2 才会被计算（第三个条件也是一样）。所以在你的例子中，只需要进行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