{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Короткий ответ" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "В низкоуровневой модели массив — это непрерывный (contiguous) блок памяти, где адрес i-го элемента вычисляется как base + i * sizeof(T). В управляемых и динамических языках встречаются вариации: массивы примитивов обычно хранятся плотно, а массивы объектов/ссылок хранят подряд ссылки на объекты, сами объекты — отдельно. Динамические массивы (vector, slice, ArrayList) используют дескриптор {ptr, len, cap} и при росте перевыделяют более крупный блок." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Подробный ответ" }] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Базовая модель хранения" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Непрерывность: элементы массива T[N] лежат подряд без «дыр», шаг (stride) равен sizeof(T). Это даёт пространственную локальность и эффективную работу кэша." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Адресация: адрес i-го элемента = base + i * sizeof(T). Для структур stride равен sizeof(struct), включая внутренние выравнивания, но между элементами массива дополнительных паддингов нет." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Примитивы vs ссылки: массив примитивов хранит значения. Массив ссылок хранит подряд указатели/ссылки одинакового размера; сами объекты могут быть разбросаны в куче." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Выравнивание: базовый адрес и каждый элемент выровнены по требованиям типа T. Это влияет на sizeof(T) и иногда на общий размер массива." } ] } ] } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "#include \n#include \nint main() {\n int a[5] = {10,20,30,40,50};\n printf(\"base=%p\\n\", (void*)a);\n for (int i = 0; i < 5; ++i) {\n printf(\"i=%d &a[i]=%p offset=%td\\n\", i, (void*)&a[i],\n (ptrdiff_t)((char*)&a[i] - (char*)a));\n }\n // offset увеличивается на sizeof(int)\n}\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Многомерные массивы, шаги и порядок обхода" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Row-major vs column-major: в C/C++/Java/JS/Python (NumPy по умолчанию) — row-major (строки подряд). В Fortran/MATLAB по умолчанию — column-major (столбцы подряд). Это определяет формулу адреса." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Адрес элемента [r][c] в row-major 2D-массиве T[R][C]: base + (r * C + c) * sizeof(T). В column-major: base + (c * R + r) * sizeof(T)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Зубчатые (jagged) массивы: это массивы указателей на массивы; строки/столбцы могут иметь разную длину, элементы не гарантированно лежат одним блоком." } ] } ] } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "#include \nint main() {\n int m[2][3] = {{1,2,3},{4,5,6}}; // row-major\n // Элемент [1][2] = 6\n printf(\"%d\\n\", *(*(m + 1) + 2)); // адрес: base + ((1*3 + 2) * sizeof(int))\n}\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Динамические массивы: дескриптор и рост" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Структура: часто представлены как дескриптор {ptr, len, cap}, указывающий на непрерывный буфер. Примеры: C++ std::vector, Go slice, Rust Vec, Java ArrayList." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Рост: при переполнении cap происходит перевыделение более крупного блока (часто ×1.5–×2) и копирование элементов; адреса/итераторы могут инвалидироваться." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Амортизированная стоимость: добавление в конец — амортизированно O(1), но отдельная операция расширения — O(n)." } ] } ] } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "#include \n#include \nint main(){\n std::vector v;\n for (int i = 0; i < 10; ++i) {\n v.push_back(i);\n std::printf(\"size=%zu cap=%zu data=%p\\n\", v.size(), v.capacity(), (void*)v.data());\n }\n}\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Особенности популярных языков" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "C/C++:" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "T a[N] — плотный блок (часто на стеке или в статической памяти)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "new T[N] — блок в куче; адресация идентична." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "std::vector — дескриптор + непрерывный буфер; гарантирует contiguous." }] }] } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Java/C#:" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Массив — объект: заголовок (тип, длина, служебные поля GC) + подряд элементы." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Массив примитивов — плотные значения; массив ссылок — плотные ссылки, объекты отдельно." }] }] } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Python:" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "list — динамический массив указателей на PyObject; элементы — объекты в куче (boxing), адреса объектов не непрерывны." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "numpy.ndarray — плотный буфер чисел с шагами (strides); может быть C- или Fortran-order." }] }] } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "JavaScript:" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Обычные Array — динамические структуры (список/хеш/спарс) с возможным боксингом; плотность не гарантируется." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "TypedArray (Uint8Array, Float64Array и т.д.) — плотный ArrayBuffer, элементы фиксированного размера." }] }] } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Go:" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Array — плотный фиксированный блок; Slice — дескриптор {ptr,len,cap} к массиву." }] }] } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Rust:" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "[T; N] — плотный; Vec — {ptr,len,cap} + буфер; &[T] — срез над плотным участком." }] }] } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Кэш, локальность и производительность" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Локальность: последовательный обход массива максимально использует кэш-линии, предвыборку и SIMD." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "AoS vs SoA: массив структур (AoS) vs структура массивов (SoA). Для векторных операций SoA часто быстрее из‑за плотного доступа к конкретному полю." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Выравнивание: корректное выравнивание предотвращает штрафы; для SIMD массивы часто выравнивают на 16/32 байта." }] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Примеры: Python (NumPy) и JavaScript (TypedArray)" }] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "import numpy as np\n# Плотный буфер с известными strides\nb = np.array([10, 20, 30], dtype=np.int32)\nprint(\"itemsize=\", b.itemsize, \"strides=\", b.strides) # (4,) для int32\nprint(\"data ptr=\", b.__array_interface__['data'][0]) # адрес базового буфера\n\n# Обычный список Python — массив указателей (не плотные значения)\na = [10, 20, 30]\nprint([id(x) for x in a]) # адреса отдельных PyObject, разбросаны в куче\n" } ] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "// JavaScript: разница между Array и TypedArray\nconst a = [1, 2, 3]; // может быть спарс/неплотный, элементы могут быть boxed\nconst t = new Uint32Array(3); // плотный буфер из 3 * 4 байт\nfor (let i = 0; i < t.length; i++) t[i] = i + 1;\nconsole.log(a.length, t.byteLength, t.BYTES_PER_ELEMENT);\n" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Частые вопросы и подводные камни" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Перевыделение: при росте динамического массива старые указатели/итераторы могут стать недействительными." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Jagged vs плотные: зубчатые многомерные массивы не дают одного сплошного блока — это влияет на кэш и формулы адресации." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Endianness: влияет на байтовое представление элементов, но не на принцип непрерывности массива." }] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [{ "type": "text", "text": "Выравнивание и sizeof: у структур возможны внутренние паддинги; stride = sizeof(struct)." }] } ] } ] } ] }

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

Комментарии