{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Короткий ответ" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Динамический массив — это массив переменного размера, который хранится в непрерывной области памяти и автоматически увеличивает (а иногда и уменьшает) свою вместимость при добавлениях/удалениях, обеспечивая быстрый доступ по индексу и амортизированно O(1) время для добавления в конец." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Развернутый ответ" }] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Ключевая идея" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Динамический массив сочетает свойства обычного (статического) массива и гибкость изменения размера. Внутри у него есть:" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "буфер фиксированной длины (capacity) в непрерывной памяти;" }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "счетчик фактического числа элементов (size), которое может быть меньше capacity." }] }] } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Когда при добавлении элементов size достигает capacity, создаётся новый буфер большего размера (обычно в 2 раза больше), все элементы копируются в него, а старый освобождается. Такая стратегия даёт амортизированно O(1) на push в конец: дорогие операции расширения случаются редко и «распределяются» на множество дешёвых добавлений." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Сложность операций" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Доступ по индексу: O(1) — прямой адресный доступ." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Добавление в конец (push): амортизированно O(1), в худшем случае O(n) при редком перераспределении и копировании." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Удаление с конца (pop): O(1)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Вставка/удаление в середине или начале: O(n) — требует сдвига элементов." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Поиск по значению: O(n), если нет дополнительной структуры (индекса/хеша)." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Как это работает внутри" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Имеются поля size и capacity. Гарантируется size ≤ capacity." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "При нехватке места буфер перевыделяется с ростом, например, ×2 (иногда ×1.5). Чем больше коэффициент роста, тем реже копирование, но тем выше средний «пустой» запас памяти." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Иногда реализуют «усадку» (shrink) при сильном уменьшении размера (например, если size ≤ capacity/4, уменьшить capacity вдвое), чтобы вернуть память системе." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Элементы лежат последовательно в памяти, что улучшает локальность ссылок и кэш-попадания CPU при линейном обходе." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Плюсы" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Быстрый случайный доступ O(1)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Амортизированно O(1) добавление в конец." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "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": "Вставки/удаления в середине/начале стоят O(n) из-за сдвигов." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Иногда расходует больше памяти, чем необходимо (capacity > size)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "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": "Статический массив: фиксированный размер, нет перераспределений; динамический — меняется, удобнее при неизвестном заранее количестве элементов." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Связный список: дешёвые вставки/удаления в середине, но нет случайного доступа (O(n)) и хуже кэш-локальность." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "В языках: C++ — std::vector, Java — ArrayList, C# — List, Python — list, JavaScript — Array (в JS массивы уже динамические по сути)." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Пример реализации (TypeScript)" }] }, { "type": "codeBlock", "content": [ { "type": "text", "text": "class DynArray {\n private buf: (T | undefined)[];\n private _size = 0;\n private _capacity: number;\n\n constructor(initialCapacity = 0) {\n this._capacity = initialCapacity;\n this.buf = new Array(this._capacity);\n }\n\n size(): number { return this._size; }\n capacity(): number { return this._capacity; }\n isEmpty(): boolean { return this._size === 0; }\n\n get(i: number): T {\n if (i < 0 || i >= this._size) throw new RangeError(\"Index out of bounds\");\n return this.buf[i] as T;\n }\n\n set(i: number, value: T): void {\n if (i < 0 || i >= this._size) throw new RangeError(\"Index out of bounds\");\n this.buf[i] = value;\n }\n\n push(value: T): void {\n if (this._size === this._capacity) this.resizeUp();\n this.buf[this._size++] = value;\n }\n\n pop(): T | undefined {\n if (this._size === 0) return undefined;\n const v = this.buf[--this._size];\n this.buf[this._size] = undefined; // помочь GC\n // Опционально: shrink, если стало слишком пусто\n // if (this._size > 0 && this._size <= this._capacity / 4) this.resizeDown();\n return v as T;\n }\n\n insert(index: number, value: T): void {\n if (index < 0 || index > this._size) throw new RangeError(\"Index out of bounds\");\n if (this._size === this._capacity) this.resizeUp();\n for (let i = this._size; i > index; i--) this.buf[i] = this.buf[i - 1];\n this.buf[index] = value;\n this._size++;\n }\n\n removeAt(index: number): T {\n if (index < 0 || index >= this._size) throw new RangeError(\"Index out of bounds\");\n const v = this.buf[index] as T;\n for (let i = index; i < this._size - 1; i++) this.buf[i] = this.buf[i + 1];\n this.buf[--this._size] = undefined;\n return v;\n }\n\n private resizeUp(): void {\n const newCap = this._capacity === 0 ? 1 : this._capacity * 2;\n const newBuf = new Array(newCap);\n for (let i = 0; i < this._size; i++) newBuf[i] = this.buf[i];\n this.buf = newBuf;\n this._capacity = newCap;\n }\n\n // private resizeDown(): void {\n // const newCap = Math.max(1, Math.floor(this._capacity / 2));\n // if (newCap < this._size) return; // безопасность\n // const newBuf = new Array(newCap);\n // for (let i = 0; i < this._size; i++) newBuf[i] = this.buf[i];\n // this.buf = newBuf;\n // this._capacity = newCap;\n // }\n}\n\n// Использование\nconst a = new DynArray(2);\na.push(10);\na.push(20);\na.push(30); // триггерит расширение буфера\nconsole.log(a.size(), a.capacity()); // 3, 4\nconsole.log(a.get(1)); // 20\na.insert(1, 15); // [10, 15, 20, 30]\na.pop(); // удалит 30\na.removeAt(0); // удалит 10" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Примечание: в JavaScript обычные массивы уже динамические, поэтому пример выше демонстрирует концепцию стратегии роста и сдвигов, а не низкоуровневое управление памятью." } ] }, { "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": "Нужен быстрый случайный доступ по индексу." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "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": "Перераспределение иногда «дорогое»: копирует все элементы; в критичных местах можно предварительно зарезервировать capacity (например, vector::reserve в C++)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Рост на ×2 даёт простое доказательство амортизированного O(1): каждый элемент копируется ограниченное число раз (порядка log n), стоимость копирований раскладывается на множество дешёвых push." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Слишком маленький коэффициент роста (например, +1) делает добавления O(n) в среднем; слишком большой — увеличивает пиковое потребление памяти." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "В некоторых языках при перераспределении старые указатели/итераторы на элементы становятся невалидными (актуально для C++). В управляемых средах ссылки на сами элементы остаются валидными, но указатель на внутренний буфер может меняться." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Итог" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Динамический массив — базовая и эффективная структура данных для последовательностей с быстрым доступом по индексу и частыми добавлениями в конец. Его ключ к производительности — стратегическое управление capacity (обычно удвоение) и непрерывное размещение элементов в памяти." } ] } ] }

Что означает 'динамический массив'?

Комментарии