大多數Pythonic方法來查找/檢查列表中的項目與O（1）的複雜性？

Question

我面臨的問題是在O（1）複雜度的列表中查找/檢查項目。下面有一個爲O（n）的複雜性：

'foo' in list_bar 

此度爲O（n）的複雜性，因爲你正在使用一個list的in關鍵字。 （請參考Python Time Complexity）

但是，如果在set上使用in關鍵字，則其複雜度爲O（1）。

我之所以要弄清楚O（1）複雜的列表，而不是一組，主要是由於需要考慮到在列表中重複的項目。套件不允許重複。一個體面的例子是：

chars_available = ['h', 'e', 'l', 'o', 'o', 'z'] 
chars_needed = ['h', 'e', 'l', 'l', 'o'] 

def foo(chars_available, chars_needed): 
    cpy_needed = list(chars_needed) 
    for char in cpy_needed: 
     if char in chars_available: 
      chars_available.remove(char) 
      chars_needed.remove(char) 
     if not chars_needed: return True # if chars_needed == [] 
    return False 

foo(chars_available, chars_needed) 

該示例不是重點在這裏，所以請儘量不要讓它側過去。重點仍然在試圖找到O（1）複雜度來查找列表中的項目。我將如何完成pythonically？ （作爲額外的功勞，如果你確實想展示一種更好的方式來執行Python，僞代碼或其他語言的操作，我很樂意閱讀它）。

謝謝！

編輯：

針對阿米Tavory的答案，我學到了你不能讓列出的不是O（n）的速度更快，但collections.Counter()的建議幫助解決我工作中的應用。我正在上傳Stack Overflow的快速解決方案，性能非常好！如果我沒有弄錯（糾正我，如果我錯了），它應該是O（1），因爲它只涉及可哈希值並且沒有循環迭代。

from collections import Counter 
chars_available = ['h', 'e', 'l', 'o', 'o', 'z'] 
chars_needed = ['h', 'e', 'l', 'l', 'o'] 

def foo(chars_available, chars_needed): 
    counter_available = Counter(chars_available) 
    counter_needed = Counter(chars_needed) 
    out = counter_needed - counter_available 
    if not list(out.elements()): return True 
    else: return False 

foo(chars_available, chars_needed) 

非常快，非常pythonic！謝謝！

Answer 1

在一般情況下，這是不可能找到固定的時間在list元素。您可以假設維護list和set，但更新操作需要線性時間。

你提到你的動機是

列表，而不是一組，主要是由於需要考慮到在列表中重複的項目。套件不允許重複。

並要求不要關注該示例。如果這是您的動機，您可能需要使用set，dict來映射每個元素的出現次數。

您可能會發現collections.Counter有用的，特別是：

In [1]: from collections import Counter 

In [2]: Counter(['h', 'e', 'l', 'o', 'o', 'z']) 
Out[2]: Counter({'e': 1, 'h': 1, 'l': 1, 'o': 2, 'z': 1})