Упорядоченные структуры данных в языке Python
Упорядоченные структуры данных: обзор и выбор
В программировании под упорядоченностью понимают сохранение последовательности элементов в том порядке, в котором они были добавлены. Python предоставляет несколько встроенных структур, гарантирующих такое поведение. Выбор подходящей структуры влияет на производительность, читаемость и корректность кода.
Наиболее универсальным решением является использование списка list для изменяемой последовательности и словаря dict (начиная с Python 3.7) для пар ключ-значение с сохранением порядка вставки. Для неизменяемых последовательностей применяется кортеж tuple. Эти структуры встроены в язык и оптимизированы для большинства задач.
# Пример: список сохраняет порядок добавления
elements = []
elements.append('первый')
elements.append('второй')
elements.append('третий')
print(elements) # ['первый', 'второй', 'третий']
# Словарь (Python 3.7+) сохраняет порядок ключей
order = {'a': 1, 'b': 2, 'c': 3}
print(list(order.keys())) # ['a', 'b', 'c']значения списка числа python (итерация по значениям списка чисел в python)
Типичная ошибка: предполагать, что старые версии Python (до 3.7) гарантируют порядок в словаре. В таких случаях следует использовать OrderedDict из модуля collections. Также не стоит полагаться на порядок в множествах set – он не гарантируется.
Как создать неизменяемую упорядоченную последовательность?
Используйте кортеж tuple. Он работает быстрее списка при итерации и может быть ключом в словаре. Кортеж нельзя изменить после создания.
coords = (10, 20)
print(coords[0]) # 10
# coords[0] = 5 # Ошибка: кортеж не поддерживает присваиваниесловарь set python (словарь и set в python)
Ошибка: попытка изменить кортеж вызывает TypeError. Если нужна изменяемая коллекция, выбирайте список.
Как организовать двустороннюю очередь с упорядоченным доступом?
Используйте deque из модуля collections. Она оптимизирована для добавления и удаления элементов с обоих концов.
from collections import deque
q = deque(['a', 'b'])
q.appendleft('z')
q.append('c')
print(q) # deque(['z', 'a', 'b', 'c'])Python dict set (словарь и множество в python)
Если необходим произвольный доступ по индексу, deque менее эффективна, чем список (O(n) против O(1)). В таких случаях лучше подходит list.
Как сохранить порядок вставки для пар ключ-значение в старых версиях Python?
Применяйте OrderedDict. Он гарантирует порядок независимо от версии Python и предоставляет дополнительные методы, например move_to_end().
from collections import OrderedDict
od = OrderedDict()
od['x'] = 1
od['y'] = 2
od['z'] = 3
print(list(od.keys())) # ['x', 'y', 'z']типы структур python (типы структур данных в python)
Ошибка: в Python 3.7+ OrderedDict избыточен, если не нужны дополнительные методы. Его использование может снизить производительность по сравнению с обычным dict.
Как эффективно хранить последовательность однотипных данных?
Используйте array.array для компактного хранения чисел одного типа. Порядок элементов сохраняется, а память расходуется экономнее.
import array
nums = array.array('i', [10, 20, 30])
nums.append(40)
print(nums.tolist()) # [10, 20, 30, 40]Ошибка: попытка вставить элемент несовместимого типа вызывает TypeError. Например, nums.append('строка') не сработает.
Вывод: выбор упорядоченной структуры данных определяется требованиями к изменяемости, типу элементов, частоте операций вставки/удаления и необходимости произвольного доступа. List и dict покрывают большинство сценариев, для специализированных задач существуют tuple, deque, OrderedDict и array.array.
Расширенные примеры и тонкости работы
Сортировка и реверсирование списка
Список предоставляет методы sort() (изменяет исходный список) и встроенную функцию sorted() (возвращает новый).
numbers = [3, 1, 4, 1, 5, 9]
numbers.sort(reverse=True)
print(numbers) # [9, 5, 4, 3, 1, 1]
new_sorted = sorted(numbers)
print(new_sorted) # [1, 1, 3, 4, 5, 9][9, 5, 4, 3, 1, 1] [1, 1, 3, 4, 5, 9]
Срезы строк и кортежей
Упорядоченные последовательности поддерживают операцию среза, которая возвращает новую последовательность того же типа.
text = "Python"
print(text[1:4]) # 'yth'
tup = (10, 20, 30, 40)
print(tup[::2]) # (10, 30)yth (10, 30)
Использование OrderedDict для кэша с ограничением по размеру
Метод move_to_end() позволяет реализовать LRU-кэш.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
cache = LRUCache(3)
cache.put('a', 1)
cache.put('b', 2)
cache.put('c', 3)
cache.get('a') # перемещает 'a' в конец
cache.put('d', 4) # удаляет 'b' (самый старый)
print(list(cache.cache.keys())) # ['c', 'a', 'd']['c', 'a', 'd']
Объединение и повторение кортежей
Кортежи поддерживают конкатенацию и повторение, создавая новые кортежи.
t1 = (1, 2)
t2 = (3, 4)
print(t1 + t2) # (1, 2, 3, 4)
print(t1 * 3) # (1, 2, 1, 2, 1, 2)(1, 2, 3, 4) (1, 2, 1, 2, 1, 2)
Работа с deque как с кольцевым буфером
Метод rotate() сдвигает элементы.
from collections import deque
d = deque(range(5))
d.rotate(2)
print(d) # deque([3, 4, 0, 1, 2])
d.rotate(-1)
print(d) # deque([4, 0, 1, 2, 3])deque([3, 4, 0, 1, 2]) deque([4, 0, 1, 2, 3])
Создание двумерного списка (матрицы) и обход по порядку
Упорядоченность вложенных списков позволяет обращаться к элементам по строкам и столбцам.
matrix = [
[1, 2],
[3, 4],
[5, 6]
]
for row in matrix:
for elem in row:
print(elem, end=' ')
# Вывод: 1 2 3 4 5 61 2 3 4 5 6
Преобразование упорядоченной последовательности в словарь с порядком
Список пар можно превратить в словарь, при этом порядок сохранится (Python 3.7+).
pairs = [('one', 1), ('two', 2), ('three', 3)]
d = dict(pairs)
print(list(d.keys())) # ['one', 'two', 'three']['one', 'two', 'three']