python - 计算满足特定条件的组合？

Question

我正在处理一个包含大约 700 个观测值的数据集，我想计算有多少 4 个观测值的组合具有介于高值和低值之间的平均值。

我已经创建了可以执行此操作的代码，但将其应用于我的大型数据集会产生数十亿种组合，并且需要几天时间才能运行。肯定有更快或更有效的方法来做到这一点

这是我尝试过的:

import pandas as pd
import numpy as np
import itertools
from numpy import mean


df = pd.DataFrame(np.random.randint(0,100,size=(700, 2)), columns=['Value', 'Other'])

truehi = 25
truelow = 10

combs = sum(1 for e in itertools.combinations(df['Value'], 4))

meets = 0
for item in itertools.combinations(df['Value'], 4):
    avg = mean(item)
    if (avg <= truehi) & (avg >= truelow):
        meets = meets + 1

我发现这个问题看起来应该可以满足我的需要，但我无法根据我的具体情况调整它。如果有人能提供帮助那将是不可思议的:Efficiently count sets in a cartesian product that sum above a specific number

Answer 1

这里一个有用的想法是 itertools.combinations 返回组合按字典顺序。因此，如果输入序列已排序，则输出序列也将被排序。

这有助于减少要评估的组合序列，因为它可以肯定的是，如果 item[0] > truehi，则 item[0] >= item[1] >= item[2] >= item[3]，所以没有更多的组合将满足条件。

这允许我们更早地停止循环。对于我运行的一些测试，它跳过了根据测试数据，100 码的最后 30% 左右的组合高斯分布。

为了进一步扩展这个想法，我编写了一个自定义版本的组合对 1 级和 2 级使用相同的方法。这又减少了 40% 左右。

其他一些提高运行时性能的想法是计算使用 n 的对数版本的组合取 4，而不是迭代在所有组合中(由评论@crissal 暗示)，并使用 np.sum，而不是 np.avg(评论 @Sam cd)。

对于大小 100，这将我机器上的运行时间从 42 秒减少到 7.5 秒。

对于 200 大小，我用下面的算法测量了 217 秒的运行时间，不是评估 69.3% 的组合。这大约长了 29 倍，尽管整体组合的次数只有16.5倍左右更大。

尺寸为 300 时，运行时间约为 514 秒，在一个示例中，它会跳过85% 的组合。

大小为 700 时，运行时间约为 21,858 秒，在一个示例中，它会跳过79% 的组合。

import math
import pandas as pd
import numpy as np

setsz = 200 #100 #700 is target, too many combinations
df = pd.DataFrame(np.random.randint(0, 100, size=(setsz, 2)),
                  columns=['Value', 'Other'])
truehi = 25
truelow = 10
# With combinations, this is a factiorials game:
# combs has n! / ((n-4)! * 4!) combinations;
# about 10**10 for n=700
# n=100 is 3_921_225; lapse of 42.3s; sample 159_004 meets
# combs = sum(1 for e in itertools.combinations(df['Value'], 4))
log_fact_n = math.log(math.factorial(setsz), 10)
log_fact_n_4 = math.log(math.factorial(setsz-4), 10)
log_fact_4 = math.log(math.factorial(4), 10)
log_combs = log_fact_n - log_fact_n_4 - log_fact_4
meets = 0

def c_combinations(iterable, r, vmax):
    # Modified from itertools.combinations
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n or r < 4:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        if pool[indices[0]] > vmax:
            return
        sum_pool_01 = pool[indices[0]] + pool[indices[1]]
        if sum_pool_01 > 2*vmax:
            for i in reversed(range(1, r)):
                indices[i] = i + n - r
            continue
        if sum_pool_01 + pool[indices[2]] > 3*vmax:
            for i in reversed(range(2, r)):
                indices[i] = i + n - r
            continue
        yield tuple(pool[i] for i in indices)

first = None
for i,item in enumerate(c_combinations(sorted(df['Value']), 4, truehi)):
    sum = np.sum(item)
    if 4*truelow <= sum <= 4*truehi:
        if first is None:
            first = i
        meets = meets + 1
    if item[0] > truehi:
        break
print(f"{meets:,} found in 10**{log_combs:,.6} combinations")
print(f"First match {first:,}, last iteration {i:,}")
# 5,711,643 found in 10**7.8108 combinations
# First match 87, last iteration 19,889,389

另一件需要考虑的事情:对于非常大的数据集，估计数量满足某些条件的组合也可以通过使用抽样来完成技巧。当您可以首先选择时，为什么要运行数十亿个组合一个随机子集并运行数百万种组合？