Блог

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

Спасибо!

Редактировать:

В ответ на ответ Ами Тавори я узнал, что вы не можете создавать списки быстрее, чем O (n), но предложение collections.Counter() помогло решить приложение, над которым я работал. Я загружаю свое более быстрое решение для переполнения стека, производительность была феноменальной! Если я не ошибаюсь (поправьте меня, если я ошибаюсь), это должно быть 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! Спасибо!

В общем, невозможно найти элементы в a 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})