计数器在python集合包中使用的算法？

我要检查，如果一组单词出现在另一组单词，例如计数器在python集合包中使用的算法？

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

我写了下面的代码，以检查是否出现在列表1的话也出现在列表2

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

但这代码失败的大input.Then我发现下面的代码在其净值适用于所有的输入

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

谁能告诉我什么algorit hm不会使用或提供任何其他方法，使用相同的结果可以在不使用内置函数的情况下实现。

来源

2016-11-28 Manel

您可以检查出的[代码]（HTTPS：//hg.python。 org/cpython/file/3.6/Lib/collections/__ init__.py）。虽然毫无疑问的一些实现是在C中。它提到'multiset'并给出了一些参考链接。 –

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

在你的情况set足够：

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

如果您不能使用set过我建议如下：

排序两个列表
叠代列表1的不同项目（ item1）
遍历list2中的项目，直到您拥有丰富的item1或list2的结尾，这意味着items不在list2，end 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

来源

2016-11-28 10:28:33

的Python 2.7.12 去到你的Python安装和Lib文件，你会发现一个名为线之间的书面collections.py

一切555-563是算法，用于填充单词字典及其相应的计数。基本上，Counter（list1）的输出是一个字典，其中的字作为关键字并计为值。

，让你减去的是存在于同一个文件 - 线652-669（粘贴以下）

def __sub__(self, other): 
     ''' Subtract count, but keep only results with positive counts. 

     >>> Counter('abbbc') - Counter('bccd') 
     Counter({'b': 2, 'a': 1}) 

     ''' 
     if not isinstance(other, Counter): 
      return NotImplemented 
     result = Counter() 
     for elem, count in self.items(): 
      newcount = count - other[elem] 
      if newcount > 0: 
       result[elem] = newcount 
     for elem, count in other.items(): 
      if elem not in self and count < 0: 
       result[elem] = 0 - count 
     return result

来源

2016-11-28 10:34:27

计数器在python集合包中使用的算法？

回答

相关问题