計數器在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集合包中使用的算法？

回答

相關問題