时间戳

首页 > 解决方案 > 删除序列中的重复项集

python - 删除序列中的重复项集

问题描述

例如data = [0, 4, 4, 2, 5, 8, 5, 8, 7, 1, 5, 6, 1, 5, 6]，我有一个列表，我需要从中删除项目集（最大长度 set k = 3），但前提是这些集彼此跟随。data包括三个这样的情况：[4, 4]、[5, 8, 5, 8]和[1, 5, 6, 1, 5, 6]，所以清理后的列表应该看起来像[0, 4, 2, 5, 8, 7, 1, 5, 6]。

我尝试了这段代码，它可以工作：

data = np.array([0, 4, 4, 2, 5, 8, 5, 8, 7, 1, 5, 6, 1, 5, 6])
for k in range(1, 3):
    kth_difference = data[k:] - data[:-k]
    ids = np.where(kth_difference)
    data = data[ids]

但是，如果我将输入列表更改为data = [0, 4, 4, 2, 5, 8, 5, 8, 7, 1, 5, 6, 1, 5]（打破最后一组），新的输出列表是[0, 4, 2, 5, 8, 7, 1, 5]，最后丢失6。

这个任务有什么解决方案？如何使此解决方案适用于任何人k？

标签： pythonlistalgorithmnumpy

解决方案

你添加了一个 numpy 标签，所以让我们利用它来发挥我们的优势。从数组开始：

data = np.array([0, 4, 4, 2, 5, 8, 5, 8, 7, 1, 5, 6, 1, 5, 6])

可以很容易地制作一个元素的掩码，直到n它们彼此跟随：

mask_1 = data[1:] == data[:-1]
mask_2 = data[2:] == data[:-2]
mask_3 = data[3:] == data[:-3]

第一个掩码在下一个元素相同的每个位置都有一个掩码。第二个掩码将有一个元素与前面两个元素相同的元素，因此您需要一次查找 2 个元素的运行。这同样适用于第三个掩码。掩码的过滤需要考虑到您希望在最后包含部分匹配的可能性。k-1您可以使用元素有效地扩展掩码来完成此操作：

delta = np.diff(np.r_[False, mask_3, np.ones(2, dtype=bool), False].view(np.int8))
edges = np.flatnonzero(delta).reshape(-1, 2)
lengths = edges[:, 1] - edges[:, 0]
delta[edges[lengths < 3, :]] = 0
mask = delta[-k:].cumsum(dtype=np.int8).view(bool)

在这种排列中，mask屏蔽构成重复组的重复的三个元素。如果复制的部分被截断，它可能包含少于三个元素。这可确保您保留部分重复的所有元素。

对于本练习，我将假设您在不同级别之间没有奇怪的重叠。即，属于重复段的数组的每一部分恰好属于一个可能的重复段。否则，掩模处理会变得复杂得多。

这是一个将所有这些包装在一起的函数：

def clean_mask(mask, k):
    delta = np.diff(np.r_[False, mask, np.ones(k - 1, bool), False].view(np.int8))
    edges = np.flatnonzero(delta).reshape(-1, 2)
    lengths = edges[:, 1] - edges[:, 0]
    delta[edges[lengths < k, :]] = 0
    return delta[:-k].cumsum(dtype=np.int8).view(bool)

def dedup(data, kmax):
    data = np.asarray(data)
    kmax = min(kmax, data.size // 2)

    remove = np.zeros(data.shape, dtype=np.bool)
    for k in range(kmax, 0, -1):
        remove[k:] |= clean_mask(data[k:] == data[:-k], k)
    return data[~remove]

您在问题中显示的两个测试用例的输出：

>>> dedup([0, 4, 4, 2, 5, 8, 5, 8, 7, 1, 5, 6, 1, 5, 6], 3)
array([0, 4, 2, 5, 8, 7, 1, 5, 6])

>>> dedup([0, 4, 4, 2, 5, 8, 5, 8, 7, 1, 5, 6, 1, 5], 3)
array([0, 4, 2, 5, 8, 7, 1, 5, 6])

定时

一个快速的基准测试表明，numpy 解决方案也比纯 python 快得多：

for n in range(2, 7):
    x = np.random.randint(0, 10, 10**n)
    y = list(x)
    %timeit dedup(x, 3)
    %timeit remdup(y)

结果：

# 100 elements
 dedup: 332 µs ± 5.01 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
remdup: 36.9 ms ± 152 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

# 1000 elements
 dedup: 412 µs ± 5.88 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
remdup: > 1 minute

注意事项

此解决方案不尝试涵盖极端情况。例如：data = [2, 2, 2, 2, 2, 2, 2]或类似的，其中多个级别k可以重叠。

推荐阅读