python - 在具有 O(1) 复杂性的列表中查找/检查项目的大多数 Pythonic 方法？

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) 的复杂度以在列表中查找项目。我将如何通过 Python 方式完成该操作？

(作为额外的奖励，如果您确实想展示用 Python、伪代码或其他语言执行该操作的更好方法，我很乐意阅读它)。

谢谢!

编辑:

在回应 Ami 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 和一个 set，但更新操作将花费线性时间。

你提到你的动力是

a list, and not a set, is largely due to the need to account for duplicate items within the list. Sets do not allow for duplicates.

并要求不要专注于示例。如果这是您的动机，您可能希望使用 dict 而不是 set，将每个元素映射到它出现的次数。

您可能会找到 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})