Должен ли я использовать словарь для тестирования членства? - PullRequest
Новая
       3

Должен ли я использовать словарь для тестирования членства?

2 голосов
/ 28 февраля 2020

Предположим, у меня есть два списка A, B, таких, что A является подмножеством B. Если бы я должен был проанализировать точки B и каждый раз, когда я хочу проверить, является ли элемент членом A, представлял бы A как словарь лучше чем список? Я спрашиваю, потому что у меня сложилось впечатление, что словари имеют худшее время поиска O (1), тогда как для массивов это O (n).

То есть, что из следующего было бы более эффективным с точки зрения сложности времени? 

# Code 1
A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

for i in B:
    if i in A:
        print (i)
    else:
        print (-1)

# Code 2
A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

A_dict = {}
for i in A:
    A_dict[i] = 0

for i in B:
    if i in A_dict:
        print (i)
    else:
        print (-1)

Кажется, что если то, что я сказал о временных сложностях выше, верно, то первый код имеет сложность O (| B | x | A |), тогда как второй имеет сложность O (| B |). Это правильно?

1 Ответ

3 голосов
/ 28 февраля 2020

Для этого следует использовать комплекты . Они имеют поиск O (1), как dicts, но они не являются парами ключ-значение.

Ваш код будет выглядеть так: 

A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

A_set = set(A)

for i in B:
    if i in A_set:
        print (i)
    else:
        print (-1)

или: 

A = {1, 2, 3}
...
...