python - 两个数组的交集，保留较大数组中的顺序

Question

我有一个 numpy 数组 a长度n , 其编号为 0 到 n-1以某种方式洗牌。我还有一个 numpy 数组 mask长度 <= n , 包含 a 的一些元素子集, 顺序不同。

我要计算的查询是“给我 a 中的元素，这些元素也在 mask 中，按照它们出现在 a 中的顺序”。

我有一个类似的问题here , 但区别在于 mask是一个 bool 掩码，而不是单个元素的掩码。

我概述并测试了以下 4 种方法:

import timeit
import numpy as np
import matplotlib.pyplot as plt

n_test = 100
n_coverages = 10

np.random.seed(0)


def method1():
    return np.array([x for x in a if x in mask])


def method2():
    s = set(mask)
    return np.array([x for x in a if x in s])


def method3():
    return a[np.in1d(a, mask, assume_unique=True)]


def method4():
    bmask = np.full((n_samples,), False)
    bmask[mask] = True
    return a[bmask[a]]


methods = [
    ('naive membership', method1),
    ('python set', method2),
    ('in1d', method3),
    ('binary mask', method4)
]

p_space = np.linspace(0, 1, n_coverages)
for n_samples in [1000]:
    a = np.arange(n_samples)
    np.random.shuffle(a)

    for label, method in methods:
        if method == method1 and n_samples == 10000:
            continue
        times = []
        for coverage in p_space:
            mask = np.random.choice(a, size=int(n_samples * coverage), replace=False)
            time = timeit.timeit(method, number=n_test)
            times.append(time * 1e3)
        plt.plot(p_space, times, label=label)
    plt.xlabel(r'Coverage ($\frac{|\mathrm{mask}|}{|\mathrm{a}|}$)')
    plt.ylabel('Time (ms)')
    plt.title('Comparison of 1-D Intersection Methods for $n = {}$ samples'.format(n_samples))
    plt.legend()
    plt.show()

产生了以下结果:

因此，对于任何大小的掩码，二进制掩码毫无疑问是这 4 种方法中最快的方法。

我的问题是，有没有更快的方法？

Answer 1

So, binary mask, is, without a doubt, the fastest method of these 4 for any size of the mask.

My question is, is there a faster way?

我完全同意二进制掩码方法是最快的方法。我也不认为在计算复杂性方面可以有任何更好的方法来完成您需要的事情。

让我分析一下您的方法时间结果:

1. 方法运行时间为 T = O(|a|*|mask|) 时间。 a 的每个元素都通过遍历其每个元素来检查是否存在于 mask 中。在 mask 中缺少元素的最坏情况下，它为每个元素提供 O(|mask|) 时间。 |a| 不变，认为它是一个常数。
   |面具| = 覆盖率 * |a|
   T = O(|a|² * 覆盖范围)
   因此，情节中覆盖范围 的线性相关性。请注意，运行时间对 |a| 具有二次依赖性。如果|掩码| ≤ |a| 和 |a| = n 然后 T = O(n²)

2. 第二种方法是使用set。 Set 是一种数据结构，它在 O(log(n)) 中执行插入/查找操作，其中 n 是集合中的元素数。 s = set(mask) 需要 O(|mask|*log(|mask|)) 才能完成，因为有 |mask| 插入操作。
   

   x in s 是一个查找操作。所以第二行在 O(|a|*log(|mask|))

   中运行

   总体时间复杂度为 O(|mask|*log(|mask|) + |a|*log(|mask|))。如果|掩码| ≤ |a| 和 |a| = n 然后 T = O(n*log(n))。您可能观察到 f(x) = log(x) 对绘图的依赖性。

3. in1d 也在 O(|mask|*log(|mask|) + |a|*log(|mask|)) 中运行。相同的 T = O(n*log(n)) 复杂性和 f(x) = log(x) 对图的依赖。

4. 时间复杂度为 O(|a| + |mask|)，即 T = O(n) 及其最好的。您观察到对情节的持续依赖。算法简单地迭代 a 和 mask 数组几次。

问题是，如果您必须输出 n 个项目，您将已经具有 T = O(n) 的复杂性。所以该方法4算法是最优的。

附言为了观察提到的 f(n) 依赖关系，您最好改变 |a| 并让 |mask| = 0.9*|a|。

编辑: 看起来 python set 确实使用哈希表在 O(1) 中执行查找/插入。