Что быстрее и почему? Set или List?

Ответ 1

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

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

Ответ 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

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

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

Ответ 3

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