Как списки хранятся в памяти?

Как списки хранятся в памяти?

Список в Python — это динамический массив переменной длины. Его память управляется особым образом для обеспечения эффективности операций добавления, удаления и доступа к элементам. Давайте разберёмся во всех деталях.

Внутренняя структура списка

1. Основные компоненты

import sys

# Список — это объект с несколькими компонентами
my_list = [1, 2, 3]

# 1. Размер объекта в памяти
print(sys.getsizeof(my_list))  # ~56 байт (только сам объект списка)

# 2. Размер элементов
print(sys.getsizeof(1))  # ~28 байт (целое число в Python)

# 3. Полный размер списка со всеми элементами
total = sys.getsizeof(my_list) + sum(sys.getsizeof(x) for x in my_list)
print(total)  # ~140 байт

# Структура объекта список в памяти:
"""
PyObject header (ref count, type)   (16 байт)
size (текущее количество элементов) (8 байт)
allocated (зарезервировано памяти)  (8 байт)
data -> [address, address, ...]     (8 байт указатель)
"""

Динамическое расширение памяти

2. Как растёт список при добавлении элементов

import sys

def show_list_capacity():
    """Показать, как растёт зарезервированная память"""
    my_list = []
    
    print("Empty list:")
    print(f"  Size: {len(my_list)}")
    print(f"  Allocated: {my_list.__sizeof__()} bytes")
    print()
    
    for i in range(10):
        my_list.append(i)
        print(f"After append({i}):")
        print(f"  Elements: {len(my_list)}")
        print(f"  Memory allocated: {my_list.__sizeof__()} bytes")
        print()

show_list_capacity()

"""
Пример вывода:
Empty list:
  Size: 0
  Allocated: 56 bytes

After append(0):
  Elements: 1
  Memory allocated: 88 bytes  (зарезервировано для 4)

After append(1):
  Elements: 2
  Memory allocated: 88 bytes  (уже есть место)

After append(2):
  Elements: 3
  Memory allocated: 88 bytes

After append(3):
  Elements: 4
  Memory allocated: 88 bytes

After append(4):
  Elements: 5
  Memory allocated: 120 bytes  (переаллокация! зарезервировано для 8)
"""

# Стратегия роста: (примерно)
# Новое выделение = текущее * 1.125 + 3
# Это оптимизирует баланс между использованием памяти и переаллокациями

Указатели и адреса памяти

3. Как хранятся элементы

import sys
import ctypes

# Список хранит указатели на объекты, а не сами объекты
my_list = [10, "hello", 3.14, [1, 2, 3]]

# Получить адреса элементов в памяти
for i, element in enumerate(my_list):
    obj_id = id(element)
    print(f"Element {i}: {element}")
    print(f"  Type: {type(element).__name__}")
    print(f"  Memory address (id): {obj_id}")
    print(f"  Address in hex: {hex(obj_id)}")
    print()

# Визуализация:
"""
PAMATЬ:

Stack (Список):
PyListObject
├─ size: 4
├─ allocated: 8
└─ data: 0x7fff5fbff8c0

Heap (Массив указателей):
[0x7fbd02d50c70,  (адрес int 10)
 0x7fbd02d50ce0,  (адрес str hello)
 0x7fbd02d50cf0,  (адрес float 3.14)
 0x7fbd02d50d00]  (адрес list [1,2,3])
"""

Сложность операций

4. Big O анализ

import timeit

def analyze_list_operations():
    """Анализ сложности операций"""
    
    # Создание списка
    my_list = []
    
    # 1. APPEND - O(1) amortized
    # Обычно O(1), но иногда O(n) при переаллокации
    timeit.timeit(lambda: my_list.append(1), number=1)
    # Результат: очень быстро для большинства операций
    
    # 2. ACCESS - O(1)
    # Прямой доступ по индексу - константное время
    my_list = list(range(1000000))
    timeit.timeit(lambda: my_list[500000], number=100000)
    # Результат: одинаковое время для любого индекса
    
    # 3. INSERT в начало - O(n)
    # Нужно сдвинуть все элементы
    my_list = list(range(1000))
    timeit.timeit(lambda: my_list.insert(0, 0), number=100)
    # Результат: медленнее, чем append
    
    # 4. DELETE - O(n)
    # Нужно сдвинуть элементы после удаляемого
    my_list = list(range(1000))
    timeit.timeit(lambda: my_list.pop(0), number=100)
    # Результат: медленнее, чем pop()
    
    # 5. SEARCH - O(n)
    my_list = list(range(10000))
    timeit.timeit(lambda: 5000 in my_list, number=1000)
    # Результат: линейный поиск

"""
СЛОЖНОСТЬ ОПЕРАЦИЙ:

Operation       Best    Average  Worst
Append          O(1)    O(1)     O(n)  (при переаллокации)
Pop (end)       O(1)    O(1)     O(1)
Pop (start)     O(n)    O(n)     O(n)
Insert          O(n)    O(n)     O(n)
Delete          O(n)    O(n)     O(n)
Get (index)     O(1)    O(1)     O(1)
Search (in)     O(n)    O(n)     O(n)
Copy            O(n)    O(n)     O(n)
"""

Копирование списков

5. Поверхностное vs. Глубокое копирование

import copy

# 1. ПОВЕРХНОСТНОЕ КОПИРОВАНИЕ (Shallow copy)
original = [[1, 2], [3, 4], [5, 6]]
shallow = original.copy()  # или list(original)

print(f"original is shallow: {original is shallow}")  # False - разные объекты
print(f"original[0] is shallow[0]: {original[0] is shallow[0]}")  # True - один объект!

# Изменение вложенного списка влияет на оба
shallow[0][0] = 999
print(f"original: {original}")  # [[999, 2], [3, 4], [5, 6]]
print(f"shallow: {shallow}")   # [[999, 2], [3, 4], [5, 6]]

# 2. ГЛУБОКОЕ КОПИРОВАНИЕ (Deep copy)
original = [[1, 2], [3, 4], [5, 6]]
deep = copy.deepcopy(original)

print(f"original[0] is deep[0]: {original[0] is deep[0]}")  # False - разные объекты

# Изменение только в одном списке
deep[0][0] = 999
print(f"original: {original}")  # [[1, 2], [3, 4], [5, 6]] - без изменений
print(f"deep:     {deep}")     # [[999, 2], [3, 4], [5, 6]]

# СОВЕТ: Когда использовать что?
my_list = [{"name": "Alice"}, {"name": "Bob"}]

# Если нужно независимо изменять элементы
independent = copy.deepcopy(my_list)
independent[0]["name"] = "Charlie"  # Не влияет на original

# Если нужна быстрая копия верхнего уровня
quick = my_list.copy()
quick.append({"name": "David"})  # Не влияет на original

Когда список переаллоцируется

6. Процесс переаллокации

def visualize_reallocation():
    """Показать процесс переаллокации памяти"""
    my_list = []
    
    steps = [
        (1, "First append"),
        (5, "After several appends"),
        (9, "Before reallocation"),
        (10, "Force reallocation"),
    ]
    
    for target_size, description in steps:
        while len(my_list) < target_size:
            old_allocated = my_list.__sizeof__()
            my_list.append(len(my_list))
            new_allocated = my_list.__sizeof__()
            
            if old_allocated != new_allocated:
                print(f"REALLOCATION! {description}")
                print(f"  Old: {old_allocated} bytes, New: {new_allocated} bytes")
                print(f"  Growth: {(new_allocated - old_allocated) / 8} new slots")

visualize_reallocation()

"""
Процесс переаллокации:

1. Создаём новый больший буфер в памяти
2. Копируем все текущие элементы в новый буфер
3. Удаляем старый буфер
4. Обновляем указатель данных

ВРЕМЕННАЯ ЛИНИЯ:

t=0: [1, 2, 3, 4] (allocated: 8 slots)
     [1, 2, 3, 4][empty][empty][empty][empty]
     
t=1: Попытка добавить элемент 5
     Буфер полон! Нужна переаллокация
     
t=2: Новый буфер выделен (12 slots)
     Новая память: [empty]*12
     
t=3: Копируем элементы
     Новая память: [1, 2, 3, 4][empty]*8
     
t=4: Добавляем элемент 5
     Новая память: [1, 2, 3, 4, 5][empty]*7
     
t=5: Старый буфер освобождается
     Garbage collector удаляет старую память
"""

Оптимизация использования памяти

7. Практические советы

import sys

# 1. PREALLOCATION - выделить место заранее
# ПЛОХО: много переаллокаций
slow_list = []
for i in range(1000):
    slow_list.append(i)

# ХОРОШО: выделить место один раз
fast_list = [None] * 1000
for i in range(1000):
    fast_list[i] = i

# 2. ИСПОЛЬЗОВАТЬ GENERATOR вместо списка для больших данных
# ПЛОХО: весь список в памяти
big_list = [x ** 2 for x in range(1000000)]
print(f"List size: {sys.getsizeof(big_list) / 1024 / 1024:.2f} MB")  # ~8 MB

# ХОРОШО: итератор практически без памяти
big_gen = (x ** 2 for x in range(1000000))
print(f"Generator size: {sys.getsizeof(big_gen)} bytes")  # ~120 bytes

# 3. УДАЛЯТЬ ненужные элементы явно
my_list = [1, 2, 3] * 1000000
del my_list  # Освободить память явно

# 4. ИСПОЛЬЗОВАТЬ ARRAY для примитивных типов
import array
# ПЛОХО: список целых чисел много памяти
list_of_ints = [1, 2, 3, 4, 5] * 1000
print(f"List: {sys.getsizeof(list_of_ints)} bytes")

# ХОРОШО: array экономит память
array_of_ints = array.array('i', range(5000))
print(f"Array: {sys.getsizeof(array_of_ints)} bytes")

Таким образом, список в Python — это динамический массив указателей на объекты, которые хранятся отдельно в памяти. Список динамически расширяет свою ёмкость при добавлении элементов, используя стратегию амортизированного расширения для оптимизации производительности.