Комментарии 29
Упрощённая реализация SkipList. :)
Существует мнение, что LinkedList - неудачная коллекция и всегда и везде лучше использовать ArrayList. А LinkedList - это для стеков и очередей, да и то не факт
Во встроенной БД Prometheus связные списки вовсю используются для управления изоляцией транзакций, Это к примеру. Далеко не единственному, кстати.
Правда, это Go. Ваше утверждение только к Java относится? Или разработчик Prometheus пошли по неправильному пути?
Зачем пытаться использовать структуру данных не по назначению? LinkedList не используют там, где нужен ArrayList, и наоборот. Или для вас HashSet и TreeSet тоже взаимозаменяемы?
А в чем вообще отличие arraylist и linkedlist? Где-то array list используется?
ну, во-первых, потому что ArrayList тоже не идеален, во-вторых, применимость LinkedList сильно ограничена теми проблемами что я описал, а именно, O(N) в рандомных операциях.
Почему бы не ускорить коллекцию, не теряя функциональности? Ведь внутри - все тот же двусвязный список со всеми возможностями. только быстрее
Вы тратите дополнительную память улучшая то, что не нуждается в улучшении. Выбирайте правильные структуры для конкретной задачи, а не пытайтесь исправить то, что замечательно работает. Нужны «рандомные» операции — используйте ArrayList, а LinkedList оставьте для других задач. У них даже контракты разные, если уж на то пошло. И как уже сказали выше, можете использовать любую из существующих имплементаций SkipList.
Я так понимаю, эта структура данных позволяет проделывать чтение, запись, вставку и удаление за O(√n), верно?
Но нельзя ли тогда уж использовать дерево, чтобы каждая операция была за O(log n)?
Или же какие свойства св. списка имеются ввиду?
Это структура для накопления и последовательной итерации, в одну сторону.
дерево требует компаратора, что ограничивает область применения.
есть интерфейс List, он очень популярен, но одна из стандартных реализаций неудачная. идея была в том, чтобы проверить, можно ли ее улучшить, сохранив базовые свойства. Оказалось, можно. Это было, для меня, интересное иследование.
По поводу 1. поправьте, если ошибаюсь, но в нашем случае всегда будет компаратор интов (причем можно просто примитивы сравнивать), как как ключом в дереве будут индексы List.
не требует. персистентные векторы (списки) вроде как по такому принципу работают.
например: https://docs.rs/im/latest/im/struct.Vector.html
Или я ошибаюсь?
если что, я имею ввиду самописное дерево, а не map.
То, что LinkedList не подходит для доступа по индексу, очевидно из его устройства. То, что ArrayList не подходит для вставки в начало, также очевидно из его устройства. Единственные интересные тут числа - это что вставка в конец LinkedList медленнее, чем в ArrayList. Видимо, операции с выделением памяти такие дорогие.
Предложенную структуру тоже не очень понимаю, зачем надо было изобретать. Если довести такое кэширование до крайнего состояния, то получится дерево. И не вижу причин, чтобы как раз его и не использовать. Было бы интересно, если бы, например, TreeMap тоже присутствовал в испытаниях.
Если надо добавлять элементы в конец связного списка, то люди обычно его инвертируют, добавляют все, что нужно, в начало, а потом инвертируют обратно. В эрланге, например, массивов вообще 40 лет не было, и это никому не мешало.
идея была - улучшить LinkedList, сделать его пригодным для реального использования.
простестирую и treemap, интересно, что получится
Чем вы меряете производительность? Неужели для микробенчмарков в 2025 кто-то использует не JMH?
Проблема связного списка не в алгоритмической сложности, а в том как устроено современное железо.
Интересно, спасибо за статью.
Добавь, пожалуйста, сравнение по памяти.
Всё-таки самое частое использование List - добавление в конец с последующей итерацией. И в таком кейсе использования ваша структура и LinkedList делают доп нагрузку на хип. К тому же ArrayList можно сразу задать нужного размера.
p.s. а ещё есть стримы)
Странно, почему для add рассмотрели и first/last, и random, а для всех остальных операций - только random?
В целом, что получится, я конечно понимаю. Но все таки в рамках "исследования" такие нюансы выглядят как попытка чего-то там
Обычно при реальном использование добавление происходит именно в конец, поэтому его стоит рассматривать отдельно. А вот удаление, обновление, и получение - это рандомные операции, которые происходят с каким-либо уже существующим объектом.
Впрочем, я мог и ошибиться с методологией. Безусловно, результаты смешанного теста зависят от процентовки операций. Если вы предложите другое распределение, я могу прогнать и его.
Есть мысль, что это съест не мало памяти. Может по этому не заменили ещë arrayList?
Прикольная статья. Мне пришла мысль, что это чем-то похоже на задачку с собеса: вот тебе проблема и решай. Остался только один вопрос: в промышленном коде кто-то такое применял?
Мне кажется есть отличный класс ArrayDeque который умеет все что умеет LinkedList но при этом уделывает его по скорости в разы и по памяти тоже.
Все таки массивы работают намного эффективней, чем созлание инстансов и хранение по 3 указателя на элемен
Можно ли спасти LinkedList? Пишем быстрый List на связном списке