Структуры данных в python

Списки (list)

      a = [1, 2, 3, 4, 5]
    

        [1, 2, 3, 4, 5]
    

      a.append(6)
    

        [1, 2, 3, 4, 5, 6]
    

      a.pop()
    

      [1, 2, 3, 4, 5]
    

Списки в python являются изменяемой последовательностью, реализованной в виде стека (последний зашел, первый вышел). Вы можете добавить элемент в "хвост" списка (метод append), либо удалить хвостовой элемент (метод pop). Список также может быть использован в качестве очереди (первый зашел, первый вышел). Вы можете добавлять элементы к "концу", и удалять из "головы", однако это является не эффективным методом из-за того, что при удалении из "головы" потребуется сдвинуть все элементы на одну позицию.

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

Из-за этого списки имею некоторые особенности:

1. Порядок вставки элементов сохраняется, коллекция упорядоченная
2. Элементы списка могут иметь разные типы в пределах одного списка
3. Чтобы обеспечить постоянное время добавления элемента в "хвост" (O(1) для append), python выделяет больше памяти для списка, чем изначально требуется. (Примечание: массив должен занимать последовательные ячейки памяти и если последующие заняты, то потребуется поиск нового свободного блока памяти)

Временная сложность операций:

Кортежи (tuple)

Кортеж является неизменяемым типом данных. Это значит, что после инициализации объекта, его нельзя модифицировать, однако в качестве элементов могут быть изменяемые типы данных. Помимо того, что кортежи ведут себя как последовательности, они являются объектами с неименованными полями. Об этой их особенности очень часто забывают. Аналогично списку, на самом низком уровне кортежи представлены в виде массива. Из-за этого кортежи очень похожи на списки и имеют близкую к ним временную сложность операций. Вместе с тем, имеются некоторые отличия, связанные в первую очередь с тем, что кортежи неизменяемы.

1. При попытке присвоить значение по индексу возникнет ошибка

   
           t = (1, 2)
           t[0] = 3
           

   
             TypeError: 'tuple' object does not support item assignment
           

   Однако допустимо следующее

   
           t = ([1, 2], 3)
           t[0].append(3)
           print(t)
           

   
             ([1, 2, 3], 3)
            

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

   
           l_1 = [1]
           l_2 = list(l_1)
           print(f"{id(l_1) == id(l_2)}")
   
           t_1 = (1,)
           t_2 = tuple(t_1)
           print(f"{id(t_1) == id(t_2)}")
           

   
           False
           True
           

3. Кортежи занимают меньше памяти чем списки. Это связанно с тем, что они не изменяемы, и можно сразу выделить память под массив по количеству элементов в нем.

   
           l_1 = [1, 2, 3, 4, 5]
           print(f"{l_1.__sizeof__()}")
   
           t_1 = (1, 2, 3, 4, 5)
           print(f"{t_1.__sizeof__()}")
             

   
           80
           64
           

Множества (set)

Множество – это неупорядоченная, изменяемая последовательность уникальных элементов. Отличительной особенностью множества являются математические операции над ними: объединение, пересечение, разность и симметрическая разность. Помимо уникальности, все объекты множества должны быть хешируемыми (Примечание: т.е. иметь функции __hash__ для вычисления хэша и __eq__ или __cmp__ для сравнения объектов между собой).

На самом низком уровне множества представлены в виде хеш таблицы. Из-за этого множества имею некоторые особенности:

1. Т.к. множества хранят таблицу хешей своих значений, они занимают больший объем памяти чем списки.

   
           l_1 = [1, 2, 3, 4, 5]
           print(f"{l_1.__sizeof__()}")
   
           s_1 = {1, 2, 3, 4, 5}
           print(f"{s_1.__sizeof__()}")
           

   
           80
           712
           

2. Хотя все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время O(1), требуется дополнительное время на вычисление хеш-функции, и если её вычисление будет неэффективным, то и все операции над множеством будут иметь увеличенную временную сложность.

Временная сложность операций:

Операции с множествами

Пересечение

      a = { 1, 2, 3 }
      b = { 2, 3, 4}
      c = a & b
    

      {2, 3}
    

Объединение

      a = { 1, 2, 3 }
      b = { 2, 3, 4}
      c = a | b
    

      {1, 2, 3, 4}
    

Симметрическая разность

      a = { 1, 2, 3 }
      b = { 2, 3, 4}
      c = a ^ b
    

      {1, 4}
    

Разность

      a = { 1, 2, 3 }
      b = { 3, 4 }
      c = a - b
    

      {1, 2}
    

Неизменяемые множества (frozenset)

Неизменяемые множества – это множества, которые не поддерживают изменения коллекции элементов, т.е. не имеют методов add и remove. Сам по себе объект set не хешируемый, а это значит, что данные последовательности не могут содержать в качестве элемента вложенное множество. В противоположность этому объект frozenset является хешируемым, а значит может быть включен в множество:

    fs_1 = frozenset([1.1, 1.2, 1.3])
    s_1 = {fs_1, 2, 3, 4, 5}
    print(s_1)
    

    {2, 3, 4, 5, frozenset({1.1, 1.3, 1.2})}
    

В отличае от списков, set и frozenset занимают одинаковый размер памяти

      fs_1 = frozenset([1.1, 1.2, 1.3])
      s_1 = set([1.1, 1.2, 1.3])
      print(f"{fs_1.__sizeof__()}")
      print(f"{s_1.__sizeof__()}")
    

      200
      200
    

Словари (dict)

Словарь – это изменяемая последовательность элементов, содержащих в себе ключ и сами данные. Если в списках и кортежах мы могли взять значение по индексу, то в словарях используется ключ. Объект dict не хешируемый, однако в качестве ключей можно использовать только хешируемые типы данных. Это связанно с тем, что, как и множества, словари основаны на хеш таблицах.

Временная сложность операций:

Двусторонняя очередь (deque)

Класс, который располагается в модуле collections.

Двусторонняя очередь является обобщением стеков и очередей. Эта последовательность позволяет эффективно добавлять элементы как в конец, так и в начало с временной сложностью O(1). Добавление в середину работает уже не так эффективно. Этот контейнер реализован в виде двусвязного списка. Это означает, что каждый элемент помимо самих данных хранит ссылки на следующий и предыдущий объект в памяти. Отсюда следует, что добавление и удаление элементов не влечет смещение остальных объектов, как это было в случае со списком.

Двусторонняя очередь отлично подходит тогда, когда вам требуется последовательно читать элементы контейнера. Если необходимо получать доступ к случайному элементу последовательности, то следует использовать списки. Представим очередь с 10 элементами. Просто извлечь значение четвертого элемента мы не сможем, потому что не знаем, по какому адресу оно находится. Потребуется последовательно пройти от первого до четвертого элемента, используя ссылки. Поэтому временная сложность доступа по индексу(кроме первого и последнего, там O(1)) к элементу объекта deque равна O(n).

Объект deque имеет атрибут maxlen, который позволяет ограничить размер последовательности. В случае если он не задан, контейнер может иметь любую длину. В противном случае, размер очереди ограничен. При достижении максимального значения maxlen, добавление элемента вызовет отбрасывание другого элемента с противоположного конца.

Временная сложность операций:

Массив (array.array)