list, set или генератор?

#python #python_3x

Очевидно, что например для проверки наличия в коллекции выгоднее использовать set,
чем list,
то есть a in [i*i for i in range(n)] менее оптимально нежели a in {i*i for i in range(n)}.
Но вот насколько оптимальнее использование генератора a in (i*i for i in range(n))?
Память экономится, а ещё? Либо я не совсем понимаю как происходит проверка наличия
элемента в генераторе.
    

Ответы

Ответ 1

Если проверка будет выполняться один раз, то лучше использовать генератор, т.к. в
этом случае будет проход по последовательности только до искомого элемента (или до
конца последовательности, если элемента в ней нет). Для создания set или list интерпретатору
нужно будет один раз обойти весь набор элементов полностью, а потом уже по нему искать.

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

Для справки:


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




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



Видим, что поиск по списку оказался немного быстрее поиска по генератору. Скорее
всего из-за того, что в генераторе для получения следующего элемента требуется больше
времени, чем в списке.



Чтобы оценить фактическую производительность для поиска с предварительной подготовкой,
пишем такую программу:

n = 10000000
a = (n-1)**2  # худший случай для линейного поиска

s_list = [i*i for i in range(n)]
s_set = {i*i for i in range(n)}
s_gen = (i*i for i in range(n))

def in_list():
    return a in s_list

def in_set():
    return a in s_set

def in_gen():
    return a in s_gen

print(in_list())
print(in_set())
print(in_gen())


Запускаем с профилировщиком:

python3 -m cProfile -s time test.py


Результат:

True
True
True
         10000011 function calls in 3.927 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    1.976    1.976    1.976    1.976 test.py:5()
 10000000    0.768    0.000    0.768    0.000 test.py:6()
        1    0.625    0.625    1.393    1.393 test.py:14(in_gen)
        1    0.489    0.489    0.489    0.489 test.py:4()
        1    0.069    0.069    0.069    0.069 test.py:8(in_list)
        3    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.000    0.000    3.927    3.927 test.py:1()
        1    0.000    0.000    3.927    3.927 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 test.py:11(in_set)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler'
objects}


Видим, что по времени создания медленнее всего создавалось множество (),
потом идет генератор (), потом список ().

По времени поиска - медленнее всего генератор (in_gen), потом список (in_list), потом
множество (in_set). 

Интерпретатор:

Python 3.6.8 (default, Aug 20 2019, 17:12:48) 
[GCC 8.3.0] on linux


Итог:


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