5 достойных альтернатив спискам в Python
В Python наиболее популярным контейнером, вероятно, является list. Благодаря присущей ему гибкости список можно повсеместно использовать в проектах для хранения различных видов данных: целых чисел, строк и экземпляров пользовательского класса. Кроме того, он является изменяемой структурой данных, что позволяет нам добавлять или удалять элементы по мере необходимости. Поэтому вовсе не удивительно, что многие программисты чрезмерно увлекаются списками, пренебрегая не менее достойными альтернативами.
Здесь мне бы хотелось обратить ваше внимание на 5 сценариев, использующих более эффективные альтернативы спискам.
1. Неизменяемость данных и хэширование — кортежи
Потребность в изменении контейнера данных возникает не всегда. Иногда, если честно, мы и вовсе не хотим его менять. В этом случае нам необходимо, чтобы неизменяемый контейнер сохранял данные. Предположим, пользователь выбирает 4 числа в качестве своего кода безопасности в разрабатываемом нами приложении. Теоретически для их хранениямы можем использовать объект списка. Однако могут сложиться нежелательные обстоятельства — код может быть случайно изменен. Рассмотрим следующий пример изменяемости списков:
>>> code_list_saved = [5, 9, 0, 3]
>>> code_list_entered = [5, 9, 0, 3]
>>> code_list_saved == code_list_entered
True
>>> code_list_saved[2] = 7
>>> code_list_saved == code_list_entered
False
Изначально эти два списка расценивались как одинаковые, чтобы пользователь мог разблокировать защищенную информацию. Но если мы изменим одно число в сохраненном коде, то два списка станут неравнозначными, вследствие чего пользователь потеряет доступ к этой информации. Вот почему сохраненный код должен быть неизменяемым.
Применительно к этому случаю мы должны рассмотреть использование кортежей. Как всем хорошо известно, они являются неизменяемыми объектами в Python, т. е. их значения нельзя изменить после создания. Ниже представлена альтернативная реализация с использованием кортежей.
>>> code_tuple_saved = (5, 9, 0, 3)
>>> code_tuple_entered = (5, 9, 0, 3)
>>> code_tuple_saved == code_tuple_entered
True
>>> code_tuple_saved[2] = 7
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
Как следует из этого примера, теперь нужный код сохранен при помощи кортежа. Попытка изменить одно из чисел привела к ошибке TypeError, которая предотвратила непредусмотренное изменение в коде. Кроме того, в качестве примитивной реализации безопасности данных объект кортежа можно хэшировать непосредственно в Python. Сохраняя в нем коды, мы можем получить хэш-значение для представления кода и таким образом ещё больше усложнить процесс взлома приложения хакерами. Взгляните на пример упрощенной реализации:
>>> code_picked = (5, 9, 0, 3)
>>> stored_code = hash(code_picked)
>>> -8016007988208603090
>>>
>>> code_attempt1 = (9, 5, 0, 3)
>>> hashed_attempt1 = hash(code_attempted)
>>> code_attempt2 = (5, 9, 0, 3)
>>> hashed_attempt2 = hash(code_attempt2)
>>> stored_code == hashed_attempt1
False
>>> stored_code == hashed_attempt2
True
>>> code_picked_list = [5, 9, 0, 3]
>>> hash(code_picked_list)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
2. Проверка принадлежности— множества
В зависимости от бизнес-задачи конкретного приложения часто необходимо проверить, содержит ли контейнер данных нужный вам элемент. Конечно, списки обладают требуемыми встроенными методами для проверки принадлежности. Как следует из нижеприведенного примера, с этой целью мы можем просто использовать ключевое слово in, которое вернет логическое значение.
>>> integers = [1, 2, 3, 4, 5]
>>> 5 in integers
True
>>> 9 in integers
False
Однако если ваше приложение требует частой проверки принадлежности, то почему бы вам не использовать множества вместо списков. Множества — еще один важнейший встроенный контейнер в Python. Их отличительная особенность состоит в том, что элементы набора должны бытьуникальными и хэшируемыми. Последнее требование является обязательным, так как на внутреннем уровне Python реализует множества в виде хэш-таблиц. И одним из самых значимых преимуществ их использования в качестве механизма реализации является амортизационное или постоянное время поиска конкретных элементов.
Проведем простое сравнение с целью продемонстрировать, как множества превосходят списки в ситуации, в которой контейнеры содержат миллионы данных.:
>>> # Импорт необходимых модулей
>>> from random import randint
>>> from timeit import timeit
>>>
>>> # Объявление функции для измерения времени, затраченного на проверку членства
>>> def time_membership_testing(n):
... integers_list = list(range(n))
... integers_set = set(range(n))
... t_list = timeit(lambda : randint(0, 2*n) in integers_list, number=10000)
... t_set = timeit(lambda : randint(0, 2*n) in integers_set, number=10000)
... return f"{n: <9} list: {t_list:.4} | set: {t_set:.4}"
...
>>> numbers = (100, 1000, 10000, 100000)
>>> for number in numbers:
... print(time_membership_testing(number))
...
100 list: 0.02304 | set: 0.01333
1000 list: 0.1042 | set: 0.01309
10000 list: 0.9028 | set: 0.01713
100000 list: 8.867 | set: 0.01932
Как вы видите, с увеличением числа элементов в list, линейно увеличивается и время на проверку принадлежности. И наоборот, применительно к set то же самое время остается почти постоянным, и, что более важно, для выполнения операции требуется гораздо меньше, чем в случае с list.
3. Извлечение значения — словари
Другой встроенный тип данных импорта dict, подобно рассмотренным выше множествам set, также требует, чтобы его ключи были хэшируемыми.
Хэшируемость ключей подразумевает, что содержащиеся в dict данные предусматривают реализацию хэш-таблицы, что и происходит на самом деле. Подобно другим ведущим языкам программирования (например, Java, Swift, Kotlin), по своей внутренней логике Python управляет словарями, используя хэш-таблицы. Но в отличие от множеств словари хранят пары ключ-значение, и хэшируемые ключи — это необходимое условие для создания хэш-таблицы.
В результате применения механизма хэширования время, необходимое для извлечения конкретной пары ключ-значение, является постоянным при временной сложности O(1), выраженной с использованием нотации “О” большое. Эта временная сложность O(1) означает, что независимо от количества элементов в dict время, затраченное на извлечение конкретного элемента, всегда остается одним и тем же. Ниже приведен пример быстрого сравнения:
>>> # Импорт необходимых модулей
>>> from random import randint
>>> from timeit import timeit
>>>
>>> # Объявление функции для измерения времени, затраченного на извлечение значения
>>> def time_value_retrieval_testing(n):
... id_list = list(range(n))
... score_list = list(range(n))
... scores_dict = {x: x for x in range(n)}
... t_list = timeit(lambda : score_list[id_list.index(randint(0, n-1))], number=10000)
... t_dict = timeit(lambda : scores_dict[randint(0, n-1)], number=10000)
... return f"{n: <9} list: {t_list:.4} | dict: {t_dict:.4}"
...
>>> numbers = (100, 1000, 10000, 100000)
>>> for number in numbers:
... print(time_value_retrieval_testing(number))
...
100 list: 0.02423 | dict: 0.01309
1000 list: 0.07968 | dict: 0.01322
10000 list: 0.625 | dict: 0.01565
100000 list: 6.223 | dict: 0.01583
Предположим, нам необходимо сохранить оценки группы студентов. Используя списки, мы создадим один для хранения ID-номера студента и другой для оценок в соответствующей позиции. Для поиска оценки конкретного студента сначала нужно определить индекс студента и с его помощью найти интересующую нас оценку. В отличие от этого, используя словари, мы просто сохраним все пары с ID-номерами студентов student_id-score в виде ключей. Как видно из примера, сравнение этих двух подходов показывает, что словари превосходят списки по эффективности, если дело касается больших объемов данных.
Примечание: поскольку словари хранят пары ключ-значения, ваша модель данных должна содержать значимые фрагменты информации для определения значений. Кроме того, ключи в словаре должны быть уникальными, а вот значения могут совпадать.
4. “Первым пришел — первым ушел” — деки
Иногда нужно часто добавлять и удалять элементы из концов последовательностей. С этой целью манипулирование ими должно осуществляться согласно порядку FIFO (“Первым пришел — первым ушел”). Иначе говоря, первый добавленный элемент будет обработан в первую очередь. Используя списки, мы можем реализовать данное условие при помощи функции pop(0). Но выполнение данного действия является весьма времязатратным процессом, поскольку элементы списка должны сдвинуться, а это уже операция O(n).
В то же время существует тип данных deque, называемый двусторонней очередью, который спроектирован для быстрого добавления и удаления с обоих концов последовательности. Для выполнения операции FIFO в Python есть возможность напрямую удалить элемент из начала очереди без необходимости сдвигать все элементы. А это значит, что данная операция осуществляется быстро. Предлагаю провести сравнение:
>>> # Импорт необходимых модулей
>>> from collections import deque
>>> from timeit import timeit
>>>
>>> # Объявление функции для измерения времени, затраченного на операцию FIFO
>>> def time_FIFO_testing(n):
... integer_list = list(range(n))
... integer_deque = deque(range(n))
... t_list = timeit(lambda : integer_list.pop(0), number=n)
... t_deque = timeit(lambda : integer_deque.popleft(), number=n)
... return f"{n: <9} list: {t_list:.4} | deque: {t_deque:.4}"
...
>>> numbers = (100, 1000, 10000, 100000)
>>> for number in numbers:
... print(time_FIFO_testing(number))
...
100 list: 3.41e-05 | deque: 1.645e-05
1000 list: 0.0004852 | deque: 0.0003466
10000 list: 0.01762 | deque: 0.002618
100000 list: 2.059 | deque: 0.02067
5. Большое число табличных данных — массивы
Со временем Pyhton стал широко использоваться в области науки о данных для их обработки, анализа и моделирования. Одна из главных причин этой растущей популярности — разработка различных пакетов с открытым ПО. Важно отметить, что для крупных наборов данных были созданы пользовательские классы. Поэтому вместо использования списков нам следует рассмотреть специально спроектированные альтернативы для решения задач, связанных с вычислениями.
Например, если вам нужно поработать с большими количеством числовых данных, то следует рассмотреть использование массивов NumPy, являющихся ключевым типом данных, реализованным в пакете NumPy. Если речь идет о работе со структурированными данными, включающими смешанные типы (например, строки, даты, числа), можно применить Pandas DataFrame — один из основных типов данных, реализованных в пакете Pandas. Если вы занимаетесь машинным обучением, то вам определенно следует обратить внимание на tensors, которые являются наиболее важными типами данных в главных фреймворках машинного обучения, таких как TensorFlow и PyTorch.
В интернете доступно много обучающих материалов, так что подробное обсуждение этих структур данных выходит за рамки статьи. На мой взгляд, если вы работаете с крупными объемами данных, вам непременно следует рассмотреть эти альтернативы. Они обладают особыми реализациями на более низком уровне, предусмотренными для оптимизации большого числа операций.
Заключение
Итак, мы рассмотрели 5 альтернатив спискам в Python.
Не стоит ограничиваться только использованием списков, поскольку Python и его соответствующие пакеты обеспечили нас другими структурами данных, которые предлагают оптимальные решения наших конкретных бизнес-задач.
Советую вам оставаться открытым всему новому и в полной мере владеть информацией об имеющихся в вашем распоряжении возможностях.
Перевод статьи Yong Cui, Ph.D.: When to Not Use Lists in Python
Комментарии