Что быстрее и почему? Установить или список?

Question

Допустим, у меня есть график, и я хочу посмотреть, если b in N[a].Какая реализация быстрее и почему?

a, b = range(2)
N = [set([b]), set([a,b])]

ИЛИ

N= [[b],[a,b]]

Это явно упрощено, но представьте, что график действительно плотный.

Answer 1

Тестирование членства в наборе значительно быстрее, особенно для больших наборов.Это связано с тем, что набор использует хэш-функцию для отображения в корзину.Поскольку реализации Python автоматически изменяют размер этой хеш-таблицы, скорость может быть постоянной (O(1)) независимо от размера набора (при условии, что хеш-функция достаточно хороша).

В отличие от этогоЧтобы оценить, является ли объект членом списка, Python должен сравнить каждый отдельный элемент на равенство, то есть тест равен O(n).

Answer 2

Все зависит от того, чего вы пытаетесь достичь. Используя ваш пример дословно, быстрее использовать списки, так как вам не нужно проходить через накладные расходы при создании наборов:

import timeit

def use_sets(a, b):
    return [set([b]), set([a, b])]

def use_lists(a, b):
    return [[b], [a, b]]

t=timeit.Timer("use_sets(a, b)", """from __main__ import use_sets
a, b = range(2)""")
print "use_sets()", t.timeit(number=1000000)

t=timeit.Timer("use_lists(a, b)", """from __main__ import use_lists
a, b = range(2)""")
print "use_lists()", t.timeit(number=1000000)

Производит:

use_sets() 1.57522511482
use_lists() 0.783344984055

Однако по причинам, уже упомянутым здесь, вы выигрываете от использования наборов, когда вы ищете больших наборов. По твоему примеру невозможно определить, для кого эта точка перегиба, и увидишь ли ты выгоду.

Я предлагаю вам протестировать его в обоих направлениях и использовать то, что быстрее для вашего конкретного варианта использования.

Answer 3

Set (я имею в виду набор на основе хеша, такой как HashSet) намного быстрее, чем List для поиска значения. Список должен идти последовательно, чтобы узнать, существует ли значение. HashSet может напрямую прыгать и определять местонахождение корзины и искать значение почти в постоянное время.