在itertool产品中跳过具有特定结构的t-uples的最快方法是什么？

Question

我必须处理由 k 个整数组成的大量元组，每个元组的范围从 1 到 Max_k。

每个 Max 可以不同。 我需要跳过元素已达到最大值的元组，在这种情况下，仅保留剩余位置中带有“1”的元组。 例如，如果三元组的第二个元素的最大值是 4，我需要保留 (1,4,1) 但跳过 (1,4,2) , (1,4,3) ... (2,4,1) 等

在 Python 中，作为具有硬编码 Maxes (5,4,2) 的玩具示例，以下 itertools.filterfalse 谓词可以完成这项工作：

def filtering_logic(y):

    if y[0]==5:
        if y[1] > 1 or y[2] >1:
            return True
   
    if y[1]==4:
        if y[0] > 1 or y[2] >1:
            return True
           
    if y[2]==2:
        if y[0] > 1 or y[1] >1:
            return True
       
    return False   

我很确定我缺少一种更快的方法来做到这一点。 我的典型场景是包含 16 到 20 个元素的元组，最多为 50-70 个元素。 推荐的方法是什么？

Answer 1

关于丢弃元组的规则的假设：

A

1. 任何值

   >=

   其索引的最大值，

   AND

2. 任何其他值（即不是满足 #1 的值）

   >= 1

B

1. 两个或多个值

   >=

   各自索引的最大值

这样，如果规则 A 或规则 B 被命中，则元组将被丢弃。

如果这个规则集描述了您的问题，那么解决方案就很容易管理。从我的基本测试来看，即使在本机 python 中，它的性能也相对较高 - 但我还提供了一个

numpy

解决方案，如果您有如此多的数据数据而本机 python 明显慢的话，假设该解决方案应该快几个数量级。

import itertools
import numpy as np

def should_discard(values, max_values):
    any_max_val    = False
    any_gt_one_val = False

    for val, max_val in zip(values, max_values): # zip truncates automatically
        #print(f"Val: {val} < {max_val}: {max_val >= val}") # Manual inspection
        if val >= max_val:
            if any_max_val:
                any_gt_one_val = True
            any_max_val = True
        elif val > 1:
            any_gt_one_val = True

        if any_max_val and any_gt_one_val: 
            return True

    return False

def should_discard_numpy(values, max_values):
    values = np.array(values)
    max_values = np.array(max_values[:len(values)])  # Truncate max_values

    ge_max_arr = values >= max_values

    if np.sum(ge_max_arr) >= 2:
        return True

    any_ge_max = np.any(ge_max_arr)
    any_gt_one = np.any((values > 1) & ~ge_max_arr)  # A.2 - compare for >1 but exclude the val(s) that hit A.1

    if any_ge_max and any_gt_one:
        return True

    return False

def filter_tuples(func, tuples, max_values):
    return itertools.filterfalse(lambda t: func(t, max_values), tuples)

vals = [
    (1, 4, 1), # Keep
    (1, 4, 2), # Discard - rule A
    (2, 4, 1), # Discard - rule A
    (0, 4, 1), # Keep
    (1, 3, 3), # Discard - rule A
    (2, 1, 3), # Discard - rule A OR rule B
]
max_vals = (2, 4, 3)

vals2 = [
    (1, 2, 1, 5, 3, 1, 6, 1, 0, 1, 1, 1, 1, 2, 0, 1, 0, 0, 0, 7), # Discard - rule A
    (2, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1), # Discard - rule B
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5), # Keep
    (1, 1, 0, 4, 3, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1), # Keep
    (1, 1, 0, 4, 3, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1), # Discard - rule A
]
max_vals2 = (2, 2, 2, 5, 4, 1, 6, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 7)

print("Native python:", list(filter_tuples(should_discard,       vals,  max_vals)))
print("Numpy        :", list(filter_tuples(should_discard_numpy, vals,  max_vals)))
print("Native python:", list(filter_tuples(should_discard,       vals2, max_vals2)))
print("Numpy        :", list(filter_tuples(should_discard_numpy, vals2, max_vals2)))