O(n) 列表减法

Question

当working on an AoC puzzle时，我发现我想减去列表（保留顺序）：

def bag_sub(list_big, sublist):
    result = list_big[:]
    for n in sublist:
        result.remove(n)
    return result

我不喜欢 list.remove 调用（它本身就是 O(n)）包含在循环中的方式，这似乎不必要地低效。所以我试图重写它以避免这种情况：

def bag_sub(list_big, sublist):
    c = Counter(sublist)
    result = []
    for k in list_big:
        if k in c:
            c -= Counter({k: 1})
        else:
            result.append(k)
    return result

现在是 O(n)，还是 Counter.__isub__ 用法仍然搞砸了？
这种方法要求元素必须是可散列的，这是原始方法没有的限制。是否有 O(n) 解决方案可以避免创建此附加限制？ Python 有比 collections.Counter 更好的 "bag" 数据类型吗？

您可以假设 sublist 是 list_big 长度的一半。

Answer 1

如果列表是无序的，从长度为 N 的列表中删除一个项目是 O(N)，因为您必须找到它。
因此，如果我们关注 "reasonable" k << N 的情况，从长度为 N 的列表中删除 k 项是 O(kN)。

所以我不明白你怎么能把它降到 O(N)。

简洁的写法：

new_list = [x for x in list_big if x not in sublist]

但这仍然是 O(kN)。

Answer 2

我会使用计数器，但我可能会略有不同，而且我可能会反复执行此操作...

def bag_sub(big_list, sublist):
    sublist_counts = Counter(sublist)
    result = []
    for item in big_list:
        if sublist_counts[item] > 0:
            sublist_counts[item] -= 1
        else:
            result.append(item)
    return result

这与您的解决方案非常相似，但每次您想减少某项计数时都创建一个全新的计数器可能效率不高。¹

此外，如果您不需要 return 列表，则考虑生成器函数...

只要 list_big 和 sublist 中的所有元素都可以散列，这就有效。此解决方案是 O(N + M)，其中 N 和 M 分别是 list_big 和 sublist 的长度。

如果不能对元素进行哈希处理，除非有其他约束（例如，输入使用相同的标准排序），否则你就不走运了。如果您的输入已排序，您可以执行类似于合并排序的合并阶段的操作来确定 bag_sub 中的哪些元素在 sublist.

中

^{¹请注意，Counters 的行为也很像 defaultdict(int)，因此在一个不存在的计数器。}

Answer 3

Is this now O(n), or does the Counter.__isub__ usage still screw things up?

这将是 O(n) 的预期情况，除了当 Counter.__isub__ 丢弃非正值时，它会通过 每个键 来这样做。你最好只用 "usual" 的方式从键值中减去 1 并检查 c[k] 而不是 k in c。（c[k] 对于 k not in c 是 0，因此您不需要 in 检查。）

if c[k]:
    c[k] -= 1
else:
    result.append(k)

Is there an O(n) solution which avoids creating this additional restriction?

仅当输入已排序时，在这种情况下，合并排序合并的标准变体可以做到。

Does Python have any better "bag" datatype than collections.Counter?

collections.Counter是Python的包。

O(n) 列表减法

O(n) list subtraction

python

bag