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

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 定义为袋子或多组。 计数过程在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