Otus.ru

Перевод статьи подготовлен в преддверии старта базового курса Разработчик Python.

В Python, наверное, самым популярным контейнером данных будет список (list). Он настолько гибкий, что его можно использовать в проектах почти повсеместно и хранить в нем данные различного типа: целые числа, строки и экземпляры пользовательских классов. Помимо этого, список мутабелен, что позволяет нам добавлять или удалять элементы по мере необходимости. По вышеперечисленным причинам некоторые программисты склонны слишком часто использовать списки и даже не рассматривать жизнеспособные альтернативы.

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

1. Иммутабельность данных и хэширование кортежи

Нам не всегда нужна возможность изменять контейнер данных. Иногда мы наоборот этого не хотим. В этом случае нам понадобится иммутабельный контейнер для хранения наших данных. Допустим, пользователь выбирает 4 цифры в качестве пароля в нашем приложении. Теоретически мы можем использовать объект типа list для хранения этих цифр. Однако иногда случаются непредвиденные обстоятельства и пароль каким-либо образом изменяется. Рассмотрим следующий фрагмент кода.

>>> code_list_saved = [5, 9, 0, 3]>>> code_list_entered = [5, 9, 0, 3]>>> code_list_saved == code_list_enteredTrue>>> code_list_saved[2] = 7>>> code_list_saved == code_list_enteredFalse

Изначально эти два списка расценивались как одинаковые, и пользователь мог с помощью этой комбинации разблокировать защищенную информацию. Однако теперь мы меняем одну цифру в сохраненном пароле, и пользователь теряет доступ. Таким образом, логично, что мы хотим, чтобы сохраненный пароль был неизменяемым.

В таком случае стоит рассмотреть использование кортежей. Как известно, они являются неизменяемыми объектами в Python, что означает, что значения в них нельзя изменить после создания. Альтернативная реализация с помощью кортежей показана ниже.

>>> code_tuple_saved = (5, 9, 0, 3)>>> code_tuple_entered = (5, 9, 0, 3)>>> code_tuple_saved == code_tuple_enteredTrue>>> code_tuple_saved[2] = 7Traceback (most recent call last):  File "<stdin>", line 1, in <module>TypeError: 'tuple' object does not support item assignment

Как видно из кода выше, сохраненный пароль теперь хранится в кортеже (tuple). Попытка изменить одну из цифр вызывает ошибку TypeError, которая предотвратит любое непреднамеренное изменение данных. К тому же, в качестве простенькой меры безопасности, кортеж можно хэшировать прямо в Python. Храня пароли в объекте типа tuple, вы сможете получить хэш-значение для его представления, что сделает ваше приложение чуть более сложным для взлома. Посмотрите на упрощенную реализацию:

>>> 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_attempt1False>>> stored_code == hashed_attempt2True>>> 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 integersTrue>>> 9 in integersFalse

Однако, если в вашем приложении механика проверки принадлежности встречается достаточно часто, то следует рассмотреть возможность использования множеств (set) вместо списков. Множества это еще один важный тип контейнера в Python. Отличительная особенность множества в том, что все элементы в нем уникальные и хэшируемые. Требование к хэшируемости выполняется поскольку под капотом Python реализует множества в виде хэш-таблиц. Одним из наиболее существенных преимуществ использования хэш-таблиц является реализация механизма константного времени поиска конкретных элементов.

Давайте проведем простое сравнение и посмотрим, насколько множества обойдут списки в производительности, когда речь зайдет о миллионах элементов в контейнерах:

>>> # Import needed modules>>> from random import randint>>> from timeit import timeit>>> >>> # Declare a function to measure the time for membership testing>>> 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.013331000      list: 0.1042 | set: 0.0130910000     list: 0.9028 | set: 0.01713100000    list: 8.867 | set: 0.01932

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

3. Поиск значений словари

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

Хэшируемость ключей подразумевает, что данные, хранящиеся в словарях, реализуются под капотом как хэш-таблицы. Как и другие популярные языки (например, Java, Swift, Kotlin), Python работает со словарями с использованием хэш-таблиц. Однако, в отличие от множеств, словари хранят в себе пары ключ-значение, и требование к хэшируемости ключей является фундаментом построения хэш-таблиц.

При использовании механизма хэширования, время, необходимое для извлечение конкретной пары ключ-значение, остается постоянным при временной сложности O(1) в записи в нотации Big-O. Временная сложность O(1) означает, что вне зависимости от того, сколько элементов в словаре, время извлечения конкретного элемента всегда останется одной и той же величиной. Сравнение вы видите ниже:

>>> # Import needed modules>>> from random import randint>>> from timeit import timeit>>> >>> # Declare a function to measure the time for value retrieval>>> 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.013091000      list: 0.07968 | dict: 0.0132210000     list: 0.625 | dict: 0.01565100000    list: 6.223 | dict: 0.01583

Допустим, нам нужно сохранить оценки группы студентов. Если использовать тип list, то у нас будет один список, который будет хранить номера студенческих билетов, и второй оценки, и элементы в этих списках будут располагаться в соответствии друг с другом. Чтобы узнать оценку конкретного студента, нужно будет узнать индекс студента из списка номеров студенческих билетов, а потом достать оценку из второго списка по этому индексу. В подходе со словарями мы просто будем хранить пары student_id-score, где номер студенческого билета будет ключом. Как мы видели выше, в данном случае приоритетнее использовать словарь, а не список, особенно, когда количество записей большое.

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

4. First-In-First-Out двусторонняя очередь

Бывают ситуации, когда нужно часто добавлять и удалять элементы с конца последовательности. То есть подразумевается порядок обработки элементов FIFO (First-in-first-out). Другими словами, первый добавленный элемент будет обработан первым. На списках мы можем реализовать эту конструкцию с помощью функции pop(0). Однако ее выполнение требует больших временных затрат, поскольку элементы должны сдвигаться, что по сложности будет соответствовать O(n).

Тип данных deque, напротив, является двусторонней очередью, которая предназначена для быстрого добавления и удаления элементов с обоих концов последовательности. Чтобы выполнить операцию FIFO, Python может непосредственно удалить элемент в начале очереди без необходимости сдвигать все элементы. Значит, операция FIFO будет выполнена быстро. Обратимся к сравнению ниже:

>>> # Import needed modules>>> from collections import deque>>> from timeit import timeit>>> >>> # Declare a function to measure the time for 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-051000      list: 0.0004852 | deque: 0.000346610000     list: 0.01762 | deque: 0.002618100000    list: 2.059 | deque: 0.02067

5. Большие объемы табличных данных массивы

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

Например, если вам нужно обрабатывать большое количество числовых данных, можно подумать об использовании массивов NumPy, которые являются основным типом данных, реализованном в пакете NumPy. Если вам нужно работать со структурированными данными, где типы данных смешаны (например, строки, даты и числа), вы можете обратить внимание на DataFrame из Pandas, которые также являются основным типом данных для пакета Pandas. Если вы занимаетесь машинным обучением, вам определенно стоит углубиться в тензоры, которые считаются наиболее важными типами данных в популярных фреймворках машинного обучения, таких как TensorFlow и PyTorch.

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

Заключение

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

Мой совет будьте открыты к новому и убедитесь, что знаете свои возможности.

Узнать подробнее о базовом курсе Разработчик Python.