Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 25
Что? Массив быстрее при вставках? Но они должны быть O(n) для массивов и O(1) для связанных списков!
Вставки в конец! Вставляли бы там в середину, ситуация бы сильно поменялась. Потому что вставка в конец в массивах все та же O(1) за счет простого трюка: когда место в массиве кончается, его размер удваивается. Можно не обязательно в 2 раза увеличивать, можно и в 1.5 - это позвояет балансировать лишнее использование памяти или более хорошую константу в O(1). Чем больше множитель, тем меньше константа и тем больше расход памяти.
Там у автора все сравнения идут реализаций с одинаковой ассимптотикой. Естественно, там кеш играет огромную роль.
Но вообще, посыл статьи правильный, надо не забывать про кеш. Тем не менее, есть такие сценарии, где списки выгоднее массивов - если у очень много элементов и идет постоянные вставки/удаления из середины. При этом операции идут по ключу, а не индексу, тогда и в массиве и в списке надо за O(n) искать элемент, но в списке можно в какой-нибудь хеш-таблице хранить указатель на каждый элемент. В массиве же так не сделать.
И там никакой кеш не покроет разницу между O(n) и O(1).
Да, граница на n, начиная с которой ассимптотика выигрывает гораздо выше, чем можно было бы подумать. Десятки тысяч, наверное.
Затраты на распределение
Это глупость. Если вам важна производительность, вы не используете указатели, а заводите массив записей и используете индексы в этом массиве вместо указателей. Ну, или используете кастомный аллкатор. Тут все локально и в кеш лучше попадает, и накладных расходов меньше (можно использовать 32-битные индексы, если у вас есть ограничение на размер стурктуры). И malloc-и вызываются столько же раз, как и в массиве.
если у очень много элементов и идет постоянные вставки/удаления из середины. При этом операции идут по ключу, а не индексу
А какое нибудь дерево тогда не лучше?
Нет, дерево тут не подходит. Если дерево по ключу, то что вообще значит "удалить из середины"? У объектов должен быть какой-то дополнительный порядок в задаче. Например, если это LRU кеш, то у нас есть ключи и "время доступа", ищем мы по ключу, а порядок поддерживаем по времени доступа.
Дерево поиска по самим ключам вообще никак этот дополнительный порядок вообще не поддерживает.
Если же делать дерево по неявному ключу, или по дополнительному ключу "порядок", то дерево тут строго хуже списка, ибо искать в нем предется по каким-то лишним с точки зрения ключа данным, во внешней структуре данных. Дерево тут оказывается лишь ненужным усложнением, ибо ничего кроме порядка, вы от дерева не используете. Список тоже поддерживает порядок, но на порядки проще в реализации.
Деревья умеют перебалансироваться при удалении произвольного элемента
У объектов должен быть какой-то дополнительный порядок в задаче
Это уже изменение задачи на ходу )
Деревья умеют перебалансироваться при удалении произвольного элемента
При чем тут это?
Это уже изменение задачи на ходу )
В задаче сказано "вставка в середину". Середину чего? В задаче уже изначально есть какой-то порядок элементов. Но ничего не сказано, что они в массиве/списке упорядочены по возрастанию. Этот второй порядок есть. Ключи вообще могут не иметь порядка.
Можно не обязательно в 2 раза увеличивать, можно и в 1.5 - это позвояет балансировать лишнее использование памяти или более хорошую константу в O(1). Чем больше множитель, тем меньше константа и тем больше расход памяти.
Это неверено. В бинарном мире идеальная плотность информации обычно приближается к числу эйлера, то бишь 2.71... Поэтому в идеальном варианте фактор роста должен равняться этому числу. Если же вы начнёте уменьшать его, то получите больше реаллокаций, чем увеличите аммортизацию. Оно всё ещё будет амортизированно константным, но более худшим чем просто удвоение.
Вообще не согласен. Если каждый раз увеличивать в k раз, то при очередном увеличении при N элементах вы сделаете N + N/k + N/k^2 + N/k^3 + ... ~= Nk/(k-1) суммарных перемещений элементов. Вот при последнем увеличении вы переместили все N элементов. В прошлом увеличении было в k раз меньше элементов, вот и слагаемое N/k. И так далее.
Чем больше k, тем меньше это общее число перемешений (оно стремится к N). При этом вы тратите в k раз больше памяти в худшем случае.
Плотность информации тут вообще не при чем.
Не забывайте, что уменьшение k приводит к большему количеству слагаемых при равных же N, что фактически отражается в финальной константе и при k < 2 "балансировка лишнего использования памяти" наоборот ухудшится вместе с ней.
уменьшение k приводит к большему количеству слагаемых при равных же N
Вы с чем тут спорите? Да, именно поэтому при уменьшении K получается больше копирований. Ровно как я и говорил. Ровно как формула kN/(k-1) и показывает: чем больше k, тем множитель ближе к 1, тем меньше сумма. И наоборот - чем меньше k, тем больше сумма.
что фактически отражается в финальной константе и при k < 2 "балансировка лишнего использования памяти" наоборот ухудшится вместе с ней.
Вы это GPT-чатиком сгенерировали? Я вообще тут не вижу никакой логики и связи с прошлым текстом.
Лишнее использование памяти, потому что вам надо место под N+1 элемент, а вы выделяете kN - примерно в k раз больше. Чем больше k, тем больше лишней памяти у вас будет.
Возвращаясь к сказанному выше: чем меньше k, тем меньше копирований. Т.е. увеличивая k вы уменьшаете потребление памяти и увеличиваете количество копирований. Вот та самая балансировка - вы можете выбирать, что вам важнее и, крутя k, разменивать лишнюю память на скорость.
см табличку ниже.
чем меньше k, тем меньше копирований.
собственнно с этим и спорю. в реалистичных сценариях этого примерно никогда не случится. статистика по копированиям будет расти заметно быстрее. Смотрел на оценки N до миллиона элементов. Может где-то выше и найдётся sweet spot, но я до него так и не добрался.
коротенькая статистика для 100 элеменотов для k=1.5 и k=2
| k | Реаллокации | Копирований | Вместимость | Небаланс памяти|
|-----|-------------|-------------|-------------|----------------|
| 1.5 | 11 | 272 | 140 | 28.57% |
| 2.0 | 7 | 127 | 128 | 21.875% |В итоге меньший k привел почти к вдвое большему количеству обращений к памяти. Да и "сэкономленной" памяти так и не дождались. С ростом N статистика не сказать чтобы хоть как-то принципиально улучшается. Так что если это не какие-то конкретные данные подходящие под асимптотику шансов наэкономить не много.
Что у вас там за "небаланс памяти" и как оно считается?
Соотношение неиспользованной памяти в массиве к выделенному на финальном шаге. 40/140 и 28/128 соотвественно. Думал что когда речь шла о "балансе" памяти оно где-то около этих значений скакало.
В естественном виде ни одна из колонок не будет давать преимущества над стандартным k=2. Если где-то перед этим был сделан reserve, то в такой ситуации ещё можно что-то пошаманить и получить профит. В общем виде - нет.
А вот теперь расмотрите не 100 элементов, а 140. У вас в одном случае будет вообще 0%. А теперь возьмите 128, и у вас в другом будет 0%.
Нельзя смотреть на одно конкретное N, Вам надо считать среднее по всем N. Для больших N можно вывести формулу average wasted space = 1/2-1/2k. Чем больше k, тем больше лишнего места. Не бесконечно, стримиться к 1/2, да, но все-же растет.
Собственно, сопоставьте aws c количеством копирований и получится, что для k=1.5 цифры примерно в два-три раза хуже стандарта, то есть если это примерный фактор замедления алгоритма и увеличения размера memory footprint. Сдаётся мне, что некоторый константный прирост памяти даст заметно более приятную асимптотику, если уж очень хочется поменьше памяти использовать.
Нет. Для 1.5 там больше копирований (Почти в 2 раза), но меньше неиспользованной памяти (почти в 2 раза):
2.0 1048575 40.39%
1.5 2099719 22.60%Код
import math
def Test(k):
n = 1000000
total_moves = 0
total_memory = 0
capacity = 1
for i in range(1, n+1):
if i > capacity:
total_moves += capacity
capacity = math.ceil(capacity * k)
total_memory += (capacity - i)/i
total_memory /= n
total_memory *= 100
print(f"{k:10}{total_moves:10} {total_memory:10.2f}%")
Test(2.0)
Test(1.5)
Спасибо, было интересно
Удивлённо тру глаза и кручу текст вверх и вниз много раз.
Где код того что мы измеряем? Где вставка элемента в конец списка? Даже наивный realloc оптимизирован так что это не копирование массива каждый раз.
Для C/C++ и Rust (unmanaged куча) аллокатор расширит блок in-place, если за ним есть свободная память, а для больших кусков ОС перемапит виртуальные страницы без физического копирования. Для C# несколько по другому, но мы сейчас не про него.
Добавлю ещё частый случай. Строка.
В C# (и Python) string неизменяем. Любое добавление (s += "text") это всегда выделение новой памяти под всю длину и полное копирование обеих частей. В цикле это даст O(N^2).
Для частых добавлений используют StringBuilder. В современном .NET это не единый удваивающийся массив (как List), а связный список чанков (массивов). Когда чанк заполняется, выделяется новый. Это сделано, чтобы большие строки не требовали огромных непрерывных кусков памяти и не забивали LOH (Large Object Heap).
В Rust иначе: String мутабелен. Под капотом это вектор Vec, он работает по правилам Capacity и realloc, которые я написал выше.
В C++ std::string изменяемый, как и в Rust. Под капотом работает аналогично вектору: удваивает capacity при нехватке места.
Ключевая архитектурная фишка: SSO (Small String Optimization). Короткие строки (обычно до 15-22 символов) вообще не выделяют память в куче. Данные лежат прямо внутри самого объекта на стеке.
Почему мутабелен: в C++ по умолчанию семантика значений (value semantics). При передаче куда-либо строка полностью копируется.
Если вы передаете ее по ссылке для скорости, компилятор не защитит вас от проблем с конкурентным доступом или инвалидацией ключей словаря (в отличие от Rust). Вся ответственность за использование const std::string& и синхронизацию висит на программисте.
Кажется, я написал комментарий лучше чем статья
И мимоходом поправили перевод: действительно, в русском языке более принят термин "связные списки". Связанные – это что-то из BDSM :).
Хотел отправить это сообщение автору приватно, чтоб не засорять информационное пространство, но оказывается, что для этого требуется пройти капчу, что для такого ничтожного повода "ту мач" :).
Если максимальное число элементов влезает во что-то меньшее указателя, можно использовать индекс в пуле (по сути массиве), вместо указателей. Например два указателя по 8 байт или два индекса по 2 байта, если число элементов меньше 2^16-1.
Такое впечатление, что автор - новичок в программировании.
И переводчик только зря тратит байты на перевод "откровений"
Что там у него написано в профиле на Линкедин - 20 лет или больше?
С XOR ведь проблема, что с точки зрения стандарта оно не обязано работать:
2.3.5 Q11. Is the XOR linked list idiom supported?
Our reading of C11 and proposal for C2x: C11: the text does not clearly specify. C2x proposal: no. C2x proposal (no-provenance option): yes
— N2263 (2018)
Хоть вроде передумали и планируют дать гарантии:
So the overall conclusion was not to ban such usage of pointers through integers.
https://gustedt.wordpress.com/2025/06/30/the-provenance-memory-model-for-c/
Если вспомнить отношение комитета к оптимизациям и alias analysis - это была не пустая угроза. В предыдущий раз его увлечение оптимизациями здесь привело к расхождению со стандартом операционных систем и браузеров (в C89 появился strict aliasing, который в рамках стандарта решили сделать неотключаемым; против стандарта идти несложно (-fno-strict-aliasing), но до этого не надо было доводить).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Структуры данных на практике. Глава 5: Связанные списки — убийцы кэша