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

我有一个长度为a的numpy数组n，其数字0到n-1以某种方式混排。我还有一个长度mask的numpy数组n，以不同顺序包含a元素的某些子集。

我要计算的查询是“，请按照它们在中出现的顺序，也将a的元素也包含在mask中。”

我有一个类似的问题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()

产生了以下结果:



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

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

最佳答案

我完全同意二进制掩码方法是最快的方法。我也不认为就计算复杂度而言，有什么更好的方法可以满足您的需求。

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

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

第二种方法是使用设置。 Set是执行O(log(n))中的插入/查找操作的数据结构，其中n是集合中的多个元素。因为存在| mask |，所以s = set(mask)需要O(| mask | * log(| mask |))来完成。插入操作。
x in s是一个查找操作。因此第二行在O(| a | * log(| mask |))中运行

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

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

时间复杂度为O(| a | + | mask |)，这是 T = O(n)并且是最好的。您观察到对图的常量依赖性。算法只是简单地对a和mask数组进行两次迭代。

事实是，如果必须输出n个项目，则已经具有 T = O(n)复杂度。因此，该方法4算法是最佳的。

P.S.为了观察提到的 f(n)依赖性，最好改变| a |。并让| mask | = 0.9 * | a |。

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

关于python - 两个数组的交集，在较大数组中保留顺序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42989384/