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

Question

我面临的问题是在O(1)复杂度的列表中查找/检查项目.以下具有O(n)的复杂性:

'foo' in list_bar

这具有O(n)的复杂性,因为您in在a 上使用关键字list.(参考Python时间复杂度)

但是,如果in在a上使用关键字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,伪代码或其他语言显示更好的方式来执行该操作,我将很乐意阅读它).

谢谢!

编辑:

为了回应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在恒定时间内找到元素.您可以假设维护a list和a set,但更新操作将花费线性时间.

你提到你的动机是

列表而非集合主要是由于需要考虑列表中的重复项目.集不允许重复.

并要求不要专注于这个例子.如果这是您的动机,您可能希望使用而不是a 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})