Потому что выбор правильной структуры данных может спасти вашу программу!
Если вы хотите сохранить пакет данных в Python, вы можете выбрать один из нескольких встроенных повторяющихся типов (в документации они подразделяются на типы последовательность, набор и сопоставление). Большинство из нас знает списки и диктовки, но есть и другие, которые могут оказаться очень эффективными в определенных ситуациях.
Важно знать сильные и слабые стороны этих распространенных типов данных, потому что выбор правильной структуры данных в нужное время может кардинально изменить (в лучшую или в худшую сторону) производительность вашего приложения!
Списки, множества, кортежи, диктовки: что это такое?
Я подробнее расскажу о каждом из этих типов данных и их свойствах в следующем разделе, но в качестве краткого вступления:
- списки - это изменяемые типы последовательностей, обозначенные квадратными скобками
[], и в них хранятся смежные элементы (потенциально разных типов), упорядоченные по целочисленным индексам. - наборы обозначаются скобками
{}и представляют собой неупорядоченный набор уникальных хешируемых элементов - вы можете добавлять или удалять элементы из набора. - frozenset почти идентичен, но после того, как вы его создали, вы больше не можете добавлять или удалять элементы из него; это неизменяемый и, следовательно, хешируемый
- кортежи - это последовательность упорядоченных элементов, обозначенных круглыми скобками
(): элементы имеют целочисленный ключ, и они могут быть разных типов, но результирующая последовательность всегда неизменна и, следовательно, хешируется. - (именованные кортежи являются расширением кортежей, в которых вы также можете получить доступ к элементам с помощью атрибута вместо обычного целочисленного ключа)
- dicts (или словари) - это тип сопоставления Python: они являются эффективным способом создания и доступа к парам "ключ-значение" (где ключ любой хешируемый объект и значение - все, что вы хотите), но они не обеспечивают порядок ключей
Какие свойства они могут иметь?
Когда вы выбираете между структурами данных, вас обычно в первую очередь интересуют одно или несколько из следующих свойств.
Уникальность
Начнем с простого с интуитивно понятного свойства: уникальности элементов. Некоторые итерируемые типы гарантируют, что все элементы, которые они содержат, появляются только один раз (каждый раз, когда вы пытаетесь повторно добавить значение, которое уже присутствует, оно просто игнорируется). Это случай наборов и, в некоторой степени, dicts в Python.
Множества - это математические объекты, имеющие свою теорию. Набор - это неупорядоченный набор отдельных элементов, специально разработанный для вычисления объединения, различия или пересечения двух коллекций.
На рисунке выше описаны 4 основные операции, которые вы можете выполнять с наборами, и показаны связанные с ними диаграммы Венна. Эти операции легко вызвать в Python:
> A = {1, 2, 3}
> B = {3, 4, 5}
> A.union(B)
set([1, 2, 3, 4, 5])
> A.intersection(B)
set([3])
> A.difference(B)
set([1, 2])
> B.difference(A)
set([4, 5])
> A.symmetric_difference(B)
set([1, 2, 4, 5])
Мы даже можем проверить, есть ли у двух наборов ненулевое пересечение с isdisjoint(), и есть ли ярлыки для всех этих операций, как описано в этом руководстве по Datacamp.
Поскольку у них есть только одна копия каждого значения, наборы - это удобный способ удалить дубликаты из списка, если вас не заботит порядок элементов:
> L = [1, 1, 4, 0, 4, 6, 3] > S = set(L) set([0, 1, 3, 4, 6]) > L2 = list(S) [0, 1, 3, 4, 6]
И, конечно же, наборы очень эффективны, если вам нужно проверить, например, есть ли в двух списках слов какие-либо общие записи!
Dicts в некоторой степени разделяют это свойство уникальности, поскольку у вас не может быть двух разных значений для одного и того же ключа: если ключ уже присутствует в dict, и вы устанавливаете для него новое значение, первое значение будет потеряно. Это может быть полезно, если вы специально хотите выполнить мемоизацию и перезаписать значения (например, при вычислении математических последовательностей, таких как Ван Экка). Однако dicts не оптимизированы для всех операций над наборами и поэтому не являются лучшим инструментом для получения элементов, общих для двух коллекций.
порядок
Еще одно простое для понимания свойство итерируемых типов - это то, упорядочены ли они. Упорядоченные коллекции записывают порядок вставки при добавлении элементов, чтобы вы могли позже:
- доступ к элементу по определенному целочисленному ключу (индекс элемента в коллекции)
- нарезать коллекцию и извлечь только ее часть
По умолчанию списки и кортежи упорядочены, поэтому вы можете получить доступ к их элементам с помощью целочисленных индексов. Они индексируются 0 (то есть первый элемент имеет индекс 0) и поддерживают отрицательную индексацию для доступа к элементам, начиная с конца коллекции. Например:
> L = [1, 2, 3] > L[0] 1 > L[-1] 3 > T = (4, 5, 6) > T[-2] 5
Кортежи могут быть расширены с помощью именованных кортежей - это позволяет вам получать доступ к элементам с помощью настраиваемого атрибута:
> from collections import namedtuple
> Point = namedtuple('Point', ['x', 'y'])
> p = Point(1, 2)
> p[0]
1
> p.x
1
Будьте особенно осторожны с dicts: хотя вы обычно получаете ключи в том же порядке, в котором их добавляли изначально, не следует предполагать, что ключи упорядочены! Они могут быть доступны в другом порядке в одном месте программы.
Примечание: здесь я сосредотачиваюсь только на встроенных типах Python, но пакет Python collections полон интересных дополнительных структур данных, таких как OrderedDict, который обеспечивает прохождение ключей в том же порядке, в котором вы их изначально добавляли.
Изменяемость (и хешируемые типы)
Если переменная изменяемая, вы можете обновить ее значение после создания; в противном случае он остается с той ценностью, которую он имел при создании, до конца своей жизни. Например, список является изменяемым, потому что вы можете добавлять или удалять элементы из него в любое время, и вы даже можете пойти и изменить один конкретный элемент после того, как поместите его в список. С другой стороны, кортежи неизменяемы: вы решаете, какое значение будет иметь ваш кортеж, когда вы его впервые создаете, а затем он останется прежним ad vitam aeternam.
Вы можете подумать, что неизменяемые типы бесполезны, потому что они только накладывают ограничения. Но это далеко не так! Большим преимуществом неизменяемых типов является то, что они могут быть связаны с уникальным сжатым представлением, называемым хешем. Следовательно, неизменяемые объекты называются хешируемыми, а это означает, что они могут использоваться в качестве ключей для таких типов сопоставления, как dicts.
Потребление памяти
Итак, почему вам все равно, используете ли вы список или диктовку? Часто речь идет о пространстве, которое ваша коллекция занимает в памяти.
Как общее практическое правило:
- брать меньше памяти лучше
- иметь масштабируемое хранилище данных - лучше
Масштабируемость - это способность системы адаптироваться и обрабатывать более тяжелую рабочую нагрузку, если вы предоставите ей больше ресурсов. В нашем случае речь идет о программе, которая все еще может работать, если мы дадим ей больше входных данных.
Очень распространенный пример - когда вы программируете небольшие видеоигры и хотите сохранить карту 2D-игры на Python (да, я имею в виду примерно половину проблем с Codingame;)). Если вам нужно сохранить каждую отдельную ячейку карты, вы можете создать список, в котором вы преобразуете 2D-координаты в 1D-координаты, или вы даже можете создать список списков, чтобы сохранить вашу 2D-структуру. Но если ваша карта пуста, за исключением нескольких точек интереса, стыдно использовать столько памяти! Вместо списков вы можете использовать dicts и создавать кортежи для ключей.
Допустим, у вас есть карта, подобная приведенной ниже, на которой:
- пробелы являются пустыми ячейками и будут закодированы как
0 - X обозначают стены и будут иметь код
1. - Ps - это бонусы и будут иметь код
2.
XXXXXXXXXXXX X X X P X X X XXXXXXXXXXXX
Наивный подход на основе списков позволит получить следующие данные (с 60 элементами):
[ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ]
В то время как основанный на dict дает нам (с 31 элементом):
{
# top border
(0, 0): 1, (1, 0): 1, (2, 0): 1, (3, 0): 1, (4, 0): 1, (5, 0): 1,
(6, 0): 1, (7, 0): 1, (8, 0): 1, (9, 0): 1, (10, 0): 1, (11, 0): 1,
# left border
(0, 1): 1, (0, 2): 1, (0, 3): 1,
# right border
(11, 1): 1, (11, 2): 1, (11, 3): 1,
# power up
(4, 2): 2,
# bottom border
(0, 4): 1, (1, 4): 1, (2, 4): 1, (3, 4): 1, (4, 4): 1, (5, 4): 1,
(6, 4): 1, (7, 4): 1, (8, 4): 1, (9, 4): 1, (10, 4): 1, (11, 4): 1,
}
Как видите, для «спискового подхода» всегда требуется W x H ячеек, где W - ширина карты, а H - ее высота. Независимо от того, сколько ячеек пусто, в середине у нас целая куча нулей. С другой стороны, с нашим dict у нас ровно столько записей, сколько непустых ячеек. На нашей маленькой карте разница невелика (хотя мы уже разделили количество хранимых элементов на 2). Но подумайте о карте, которая намного больше и совершенно пуста посередине, как эта другая:
XXXXXXXXXXXXXXX X X X X X X X X X X X X X X X X XXXXXXXXXXXXXXX
Теперь «подход диктовки» намного лучше! Для этого нужно всего лишь 46 элементов (для пограничных стен) вместо 150 ячеек при «списковом подходе». Мы могли бы уменьшить это еще больше, используя идеи интеллектуального хранения со сжатием; например, мы могли бы хранить «блоки» смежных ячеек одного и того же типа в одном элементе, используя 4D-кортежи, представляющие маленькие прямоугольники как: (min x, min y, max x, max y).
Примечание: если вас интересуют методы хранения только релевантных данных nD, посмотрите как хранить разреженные матрицы!
Подводить итоги
Вот краткая таблица, в которой суммируются различные свойства структур данных, о которых я говорил в этой статье:
Заключение
Выбор правильного типа данных важен - он определяет, сколько памяти и вычислительной мощности требуется вашей программе, и может даже быть причиной того, что ваше приложение работает или нет. Хорошо известная мантра в кодировании, когда вы работаете над новым проектом: « Сделай это работающим, сделай это правильно, сделай это быстро ». Это хорошая фраза, которая отражает 3 этапа, через которые, вероятно, пройдут многие ваши приложения:
- этап 1: по крайней мере, когда вы можете нажать «компилировать» (или «запустить»), он компилируется (или «запускается»)…
- этап 2: теперь он даже вычисляет правильные результаты, ура!
- этап 3: потрясающе, не все выходные, а всего 2 минуты !!
Часто вам нужно останавливаться на этапе 2. Но этап 3 важен, потому что фрагмент кода, который вычисляет правильные вещи, но не может фактически использоваться в повседневной жизни, действительно теряет ценность. Существует даже целая математическая область, посвященная изучению тех совершенных алгоритмов, которые никогда не могут быть запущены в реальной жизни, так называемая теория вычислительной сложности, которая больше всего известна своей проблемой P против NP. Множество соревнований по кодированию и / или тренировочных упражнений (вроде тех, что я упоминал ранее в Codingame) заставляют вас сделать этот дополнительный шаг, представляя вам тестовые образцы, которые постепенно масштабируются в размере - таким образом, неоптимизированная программа будет бороться или даже вылетать раньше он может выполнить задачу на больших наборах данных. Иногда решение заключается не в самом алгоритме, а в том, как вы храните свои данные и получаете к ним доступ ...
Если вам понравилась эта статья, вы можете найти больше сообщений в блоге о технологиях, искусственном интеллекте и программировании на моем сайте :)
