Большинство Pythonic способ найти/проверить элементы в списке с O (1) сложностью?

Question

Проблема, с которой я столкнулся, заключается в поиске/проверке элементов в списке с сложностью O (1). Ниже имеет сложность O (N):

'foo' in list_bar 

Это имеет сложность O (N), потому что вы используете ключевое слово in на list. (Обратитесь к Python Time Complexity)

Однако, если вы используете ключевое слово in на set, оно имеет сложность 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) для поиска элементов в списке. Как я мог бы выполнить это на питоническом уровне?

(В качестве дополнительного кредита, если вы хотите показать лучший способ выполнения этой операции в Python, псевдокоде или другом языке, я был бы рад прочитать его).

Спасибо!

Edit:

В ответ на ответ Ами 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})