python - Counter 在 python 集合包中使用的算法？

Question

例如，我想检查一组单词是否存在于另一组单词中

list1=['Hello','World']
list2=['Hello','World','Good','Bye']

我写了下面的代码来检查 list1 中的单词是否也出现在 list2 中

def check(list1,list2):
 for l in list1:
  if l not in list2:
   return False
 return True

但是这段代码对于大输入是失败的。然后我在网络中找到了以下适用于所有输入的代码

from collections import Counter
def check(list1,list2):
 return not (Counter(list1) - Counter(list2))

任何人都可以告诉我 Counter 使用什么算法或提供任何其他方法，使用这些方法可以在不使用内置函数的情况下实现相同的结果。

Answer 1

Counter的源代码将 Counter 定义为 bag 或 multiset。计数过程在update方法，它不包含任何特殊内容 - 它只是遍历所有元素并计算它们的出现次数。

在你的情况下 set够了:

def check(list1, list2):
    # all items from list1 in list2
    return set(list1) <= set(list2)

如果您也不能使用 set，我建议您执行以下操作:

1. 对两个列表进行排序
2. 遍历 list1 (item1) 的不同项目
3. 遍历 list2 的项目，直到您丰富 item1 或 list2 的末尾，这意味着项目不在 list2 中，结束 list1 循环。

我需要 2nlogn + 2n 时间。

def check(list1, list2):
    j = 0
    prev = None
    for item1 in list1:
        if prev is not None and item1 == prev:
            continue

        while j < len(list2):
            if list2[j] == item1:
                break
            if list2[j] > item1:
                return False
            j += 1
        else:
            return False

        prev = item1
        j += 1

    return True