Как устроены dict, list и NumPy array в Python
Объясни, как работает Python dict и чем обычный list отличается от NumPy array.
Короткий ответ
dict - hash table с average O(1) для lookup/insert/delete. list - динамический массив ссылок на Python objects. NumPy ndarray - однородный typed buffer с shape/strides и векторизованными операциями в низкоуровневом коде.
Полный разбор
Python dict хранит пары key-value в hash table. Для lookup считается hash ключа, затем структура находит слот и сравнивает ключи при коллизиях. В среднем lookup, insert и delete работают за O(1), но это amortized average: бывают resize, collisions и худшие случаи. В современных версиях CPython dict также сохраняет порядок вставки.
Python list - это динамический массив ссылок на Python objects. Он гибкий: можно хранить объекты разных типов, append обычно amortized O(1), index access O(1). Но элементы не лежат как плотный typed numeric buffer; каждый элемент - ссылка на объект, поэтому численные операции в цикле платят overhead интерпретатора и object boxing.
NumPy ndarray хранит данные в однородном typed buffer с shape, strides и dtype. Размер обычно фиксирован логически, а операции над массивами выполняются в оптимизированном низкоуровневом коде и могут использовать contiguous memory, SIMD/BLAS и broadcasting. Поэтому NumPy быстрее для больших численных массивов, но менее гибок по типам и форме.
Теория
Для ML-инженера важна не только асимптотика, но и memory layout: list удобен как контейнер Python-объектов, ndarray - как плотное численное представление.
Типичные ошибки
- Сказать, что list хранит числа подряд как C array значений.
- Не упомянуть hash collisions и resize у dict.
- Описать NumPy array как просто "быстрый list" без dtype, shape и strides.
Как отвечать на собеседовании
- Разделяй average O(1) у dict и memory layout list/ndarray.
- Для NumPy обязательно скажи про однородный dtype и vectorized operations.