Comments 10
O(1) — это только момент перецепления указателей. До нужного места ещё надо дойти:
А если побенчмаркать вставку в начало (может это самый частый случай в конкретной задаче) ? ;)
Справедливо, этого случая в статье нет. Вставка в начало - как раз то, где у списка обхода нет вообще: голова всегда под рукой, а слайсу нужен memmove всего массива. Тут список должен выигрывать, и заметно.
Добавил замер в модуль, прогоню и вернусь с цифрами. Заодно интересно посмотреть на второй шаг: список, собранный вставками в начало - это ровно тот самый разбросанный список из статьи. Если по нему потом хоть иногда ходят, выигрыш на вставке может съесться на обходе. Вот это и хочу замерить, а не угадать.
Да и заголовок обманчив - вставка по индексу (с получением элемента обходом с начала) в списке это таки O(n), в тексте это всё таки сказано. Если надо вставлять в середину, но элемент списка индентифицируется указателем на него - тогда, как и со вставкой в начало, будет O(1) и опять же ожидается выигрыш от списка.
Принимаю. По индексу у обоих O(n), и массив выигрывает на константах. «O(1)» - учебное утверждение, а не мой замер.
Про указатель - согласен, это и есть вывод статьи: третья колонка, 3.4-3.6 нс против ~19 мкс.
Вставку в начало из соседнего комментария тоже померил: 15.9 мкс против 0.5 нс на 100k.
Одна поправка к полному счёту: указатель надо откуда-то взять, обычно из map плюс её память и lookup. И если по списку иногда ходят, возвращается ×322, потому что после серии вставок узлы разъезжаются.
Пошёл мерить, и вы правы, случай зря пропущен.
100k элементов: слайсу на вставку в начало нужен memmove всего массива, 15.9 мкс. Списку две записи указателя, 0.5 нс, и от размера это не зависит. Аллокацию узла мерю отдельно, там первая версия бенчмарка сама села в лужу: escape analysis утащил узел на стек, и получилось 0.3 нс при 0 allocs/op, то есть аллокация «быстрее» обычного присваивания. Переписал. Но даже десятки наносекунд тут картину не меняют.
Дальше я собирался возразить, что выигрыш съест обход, список-то из вставок в начало это ровно тот самый разбросанный. Померил: не съест. Обход миллиона 1.90 мс, у плотного 1.77 мс, у разбросанного 158 мс. Ведёт себя как плотный. Дошло почему: последовательные аллокации кладут узлы по возрастающим адресам, а обход идёт по убывающим. Шаг регулярный, этого хватает.
Так что возражения нет, вставка в начало - нормальный случай для списка, без оговорок. Узлы разъедутся только если между вставками аллоцируется что-то ещё, вот тогда обход и поедет в сторону тех самых 158 мс.
Замеры добавил в модуль: BenchmarkInsertFront и BenchmarkTraversePrepended.
По поводу аллокаций - нормальные списки делаются поверх массива (вместо указателей используются индексы в массиве). Тогда все элементы списка, хоть и идут не по-порядку, но лежат кучно. Независимо от того, как и что вы там аллоцируете параллельно. Если вы еще и часто по списку проходитесь, то можно его периодически "сортировать" - во время прохода перепешите его в новый массив по порядку и все следующие проходы будут удобны для кэша и сильно быстрее. Эти оптимизации делают список гораздо выгоднее и лучше массива для меньших n и с большим соотношением поиска/вставки.
Померил SoA-вариант, vals []int64 плюс next []int32. Результат интереснее
Обход миллиона по порядку: указатели 1.77 мс, индексы 2.43 мс, то есть индексы на 38% хуже. Обход того же миллиона вразброс: указатели 158.2 мс, индексы 67.9 мс, индексы в 2.3 раза лучше. На ста тысячах то же направление, слабее.
Получается, индексы помогают там, где локальность уже потеряна, и мешают там, где она есть. На упорядоченном обходе узел из 16 байт читается одним потоком, а SoA требует двух независимых чтений плюс проверку границ. На разбросанном выигрывает меньший рабочий набор связей: 4 МБ next против 16 МБ узлов.
Разрыв с массивом при этом сокращается вдвое, но не закрывается - ×138 вместо ×322 на миллионе. И цена случайного порядка обхода падает с ×89 до ×28 относительно упорядоченного варианта, то есть остаётся главным фактором.
Так что представление на индексах работает, но как средство от плохой локальности, а не как способ её получить. Получить её даёт та самая компактизация, про которую вы написали: 1.77 мс против 158 мс - это ×89, и никакая смена представления столько не даёт.
O(1) — это только момент перецепления указателей. До нужного места ещё надо дойти:
Как обычно, грубейшая ошибка в сравнении. Вы сравниваете O(n) в массиве и O(n) в списке и удивляетесь, что список медленный. Поиск в массиве сильно быстрее поиска в списке. Поэтому поиск+вставка в массиве часто выигрывают поиску+вставке в списке.
Бесполезно применять список вот так. Он выигрывает, когда вы уже знаете место, куда вставляете. Это значит, что вставка тут не отдельная абстрактная операция, а часть алгоритма.
Один такой пример - структура данных skip list. Попробуйте реализовать ее поверх массива, она для весьма маленьких n станет медленнее списоков. Даже при учете хорошего для кэшей обращения к памяти.
Другой пример: обратная операция - не вставка, а удаление из середины списка. Тут ассимптотика у списка тоже O(1) против O(n) в массиве. Примером тут будет LRU кэш.
Да недружественность к памяти дает весьма большую константу в этом O(1) и для выигрыша перед массивами нужно n заметно больше, чем люди себе представляют. Но если у вас миллион объектов, то список будет выгоднее.
Померил
Удаление из середины, 100 000 элементов:
массив, сдвиг хвоста - 17.4 мкс
список с обходом - 28.8 мкс
список с готовым указателем - 1.02 нс
×17 000 в пользу списка, и от размера не зависит: 1.04 нс на тысяче, 1.02 нс на ста тысячах. Здесь вы правы полностью, и в статье этой операции действительно не было.
Заодно закрыл аллокацию узла из соседней ветки: вставка в начало через &node{} - 20 нс, 16 B/op, 1 allocs/op. Против 15.9 мкс у сдвига слайса это ×784.
Но средняя строка таблицы - про то, о чём я писал выше: как только за узлом надо идти обходом, список проигрывает массиву даже на удалении, где у него O(1) против O(n). 28.8 против 17.4 мкс.
То есть граница ровно там, где вы её и провели. Указатель в руках - список вне конкуренции. Указатель надо искать - выигрывает массив.
Асимптотика на этой границе не меняется, меняется только то, кто добывает узел
В учебнике написано: вставка в связный список — O(1), в массив — O(n). Вывод как будто очевиден: вставляем часто — берём список.
О-нотация описывает сложность алгоритма - зависимость потребления ресурсов (время работы, потребляемая память) от размера данных: константа, линейная, квадратичная, экспоненциальная.
Она позволяет грубо оценить скорость работы на большом объеме данных по скорости на небольшом тестовом объеме.
В общем случае их нельзя сравнивать, конкретные числа неизвестны: O(1) может быть сутки, O(n) секунда/элемент или час/элемент.
Почему O(1) проигрывает O(n): структуры данных в Go на реальном железе