Наборы Python против списков

Question

Какая структура данных в Python более эффективна / быстра? Предполагая, что порядок не важен для меня, и я все равно буду проверять наличие дубликатов, является ли набор Python более медленным, чем список Python?

Answer 1

Это зависит от того, что вы собираетесь с ним делать.

Наборы значительно быстрее, когда дело доходит до определения наличия объекта в наборе (как в x in s), но медленнее, чем списки, когда дело доходит до перебора их содержимого.

Вы можете использовать модуль времени , чтобы узнать, что быстрее для вашей ситуации.

Answer 2

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

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

Оказывается, что кортежи работают почти так же, как списки, за исключением их неизменности.

Перебор

>>> def iter_test(iterable):
...     for i in iterable:
...         pass
...
>>> from timeit import timeit
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = set(range(10000))",
...     number=100000)
12.666952133178711
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = list(range(10000))",
...     number=100000)
9.917098999023438
>>> timeit(
...     "iter_test(iterable)",
...     setup="from __main__ import iter_test; iterable = tuple(range(10000))",
...     number=100000)
9.865639209747314

Определить, присутствует ли объект

>>> def in_test(iterable):
...     for i in range(1000):
...         if i in iterable:
...             pass
...
>>> from timeit import timeit
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = set(range(1000))",
...     number=10000)
0.5591847896575928
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = list(range(1000))",
...     number=10000)
50.18339991569519
>>> timeit(
...     "in_test(iterable)",
...     setup="from __main__ import in_test; iterable = tuple(range(1000))",
...     number=10000)
51.597304821014404

Answer 3

Список производительности:

>>> import timeit
>>> timeit.timeit(stmt='10**6 in a', setup='a = range(10**6)', number=100000)
0.008128150348026608

Установить производительность:

>>> timeit.timeit(stmt='10**6 in a', setup='a = set(range(10**6))', number=100000)
0.005674857488571661

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

Наборы также являются структурами последовательностей, но с двумя отличиями от списков и кортежей. Хотя наборы имеют порядок, этот порядок является произвольным и не контролируется программистом. Второе отличие состоит в том, что элементы в наборе должны быть уникальными.

set по определению. [ питон | 1021 * Вики *].

>>> x = set([1, 1, 2, 2, 3, 3])
>>> x
{1, 2, 3}

Answer 4

Set выигрывает из-за почти мгновенных проверок "содержит": https://en.wikipedia.org/wiki/Hash_table

Список реализация: обычно массив, низкий уровень, близкий к металлу, подходит для итерации и произвольного доступа по индексу элемента.

Установить реализацию: https://en.wikipedia.org/wiki/Hash_table, он не выполняет итерации по списку, но находит элемент путем вычисления хеша из ключа, поэтому он зависит от природы из ключевых элементов и хэш-функции. Подобно тому, что используется для dict. Я подозреваю, что list может быть быстрее, если у вас очень мало элементов (<5), чем больше число элементов, тем лучше будет <code>set для проверки содержимого. Это также быстро для добавления и удаления элементов.

ПРИМЕЧАНИЕ : если list уже отсортирован, поиск по list может быть довольно быстрым, но в обычных случаях set быстрее и проще для проверок на наличие.

Answer 5

Я бы порекомендовал реализацию Set, где вариант использования ограничен ссылками или поиском существования, и реализацию Tuple, где сценарий использования требует от вас выполнения итерации. Список является низкоуровневой реализацией и требует значительных затрат памяти.