Rust и двусвязный список

нужно сначала перестать выдвигать тезисы о том, что O(N) быстрее, чем O(1)

Может быть вполне быстрее. Все зависит от N. По мимо самого N в формуле есть умалчиваемый коэффициент A, который в общем случае отличается в 2 случаях.

Для танкистов есть пример - x > x*x в случае когда x<1 при больших х обычно квадрат всегда больше. Ровно такая же схема и в случае O(N) vs O(1)

Я Вам больше скажу, дети. Даже диод может выпрямлять ток в обратном направлении… Но об этом вы узнаете только в институте…

Дети перестаньте ссорится!

Здесь https://rust-unofficial.github.io/too-many-lists/

есть ответы на все ваши вопросы касательно списков, которые практически 1:1 повторяют то что я написал.

Списки действительно д-мо. И товарищ den73 аж с 5 звёздочками, которые непонятно за что он получил спорит с самим создателем языка C++… когда рассуждает что там быстрее O(1) или O(N)…

Я бы не стал так легко ставить под сомненье мнение Бьёрна, тем более когда он говорит разумные вещи!

Создана исключительно с целью доказать, что раст - говно.

А это как говорят в таких случаях - Вы это сами сказали… Значит сомнения таки есть… И вариант предложенный по созданию двусвязных списков действительно воняет.

И врядли тут проблема в языке. Обычный двусвязный список это проблема в любом языке! Просто RUST эту проблему освечивает и заставляет задуматься. В C/C++ все бы скомпилировалось на ура. Но скорее всего это не победа, а поражение.

Самым правильным решением будет скорее всего отказ от такого рода структуры данных. Тем более, что совершенно непонятно где его можно применить. И где что-то другое не подходит гораздо лучше.

Мне представляется, что практически идеальным вариантом является std::vector, когда почему-то в голове появляется желание сделать список.

Если хотите на этот вопрос ответ даёт std::vector. Т.е. начальное число может быть хоть 0. Но постепенно оно растёт. Используя статистику можно начать с некоторого числа N, которое в 90% случаев будет достаточным, чтобе не выделять память каждый раз.

никто не собирается использовать эту вашу «статистику», потому что лень придумывать какую-то «статистку» для затыкания дыр вашего «вектора». все делают в лоб на списках и живут хорошо, там не нужна никакая статистика и все что надо, список прекрасно обеспечивает.

если готовы прочувствовать отличия списков от массивов - реализуйте на массивах лисп.

для затыкания дыр вашего «вектора»

Это ТОЧНО не мой вектор! Мне он совсем НЕ нужен. Мне нужен массив. Почему его RUST не предлагает мне непонятно.

там не нужна никакая статистика Вектору тоже НЕ нужна никакая статистика. Вы можете начать с 0.

все делают в лоб на списках и живут хорошо

Не все точно.

Что именно Вам нужно от списка? Что не может обеспечить никакой другой тип данных?

И я и по ссылке - все видят проблемы и тормоза со списками. Вы их НЕ видите. Может проблема в Вас?

Если у Вас будет умная мысль - поспорьте с Бьёрном… А мы тут посмеёмся.

Что именно Вам нужно от списка? Что не может обеспечить никакой другой тип данных?

прочитайте последнее предложение моего поста про лисп. и много думайте.

Обычный двусвязный список это проблема в любом языке! Просто RUST эту проблему освечивает и заставляет задуматься.

у вас рустовиков с бошками чевойта. никогда ни двухсвязный, ни односвязный проблемами не были, пока была ручное управление памятью. и возникла эта «проблемища», когда стали делать сборщики мусора(а не руст какой-то), ради экономии применяющие счетчик ссылок. а поскольку на счетчике ссылок взаимные ссылки, даже косвенные приводят, к ложному оптимизму о немусорности обьекта, то одними счетчиками тут не обойтись и GC приходится усложнять всякими пометками и обходами, что долго.

а поскольку руст это попытка «улучшить» медленные языки с GC, то проблема эта перекочевала и в руст. а двусвязный список состоит из именно таких взаимных ссылок друг на друга, от чего растовики массово обьявили ему анафему и пытаются заразить этой шизофренией плюсовиков и прочих.

а плюсах список, это класс с наглухо инкапсуированной реализацией, и чтобы его сломать надо усилий не меньше чем сломать массив. любую пакость, что можно сделать с целостностью списка, можно сделать и целостностью массива. так что аргумент, что мол массив это надежно! а список - нет! - ерунда.

У вас есть элемент списка строк (строки могут быть любого размера). В списке N элементов. Данный элемент Э изначально имеет номер N/3. Предлагаю вам M раз вставить в список ещё один элемент случайной длины перед элементом Э, а потом удалить вновь вставленный элемент. Потом расскажете мне, что такое O(N).

next: Rc<RefCell>

Так можно, но тогда и раст ваш не нужен, подсчёт ссылок прекрасно работает и в других языках.

а плюсах список, это класс с наглухо инкапсуированной реализацией

Так-то да, но это не очень интересно. Интересный случай - это когда объект участвует сразу в нескольких структурах, например, более, чем в одном списке. И тогда возникает вот этот сценарий: поулчил элемент из списка, отдал на сторону, потом снова начал с ним что-то делать, а в это время незаметно элемент уже кем-то был из списка удалён. И вот, прослышав про крутизну Раста, я подумал, а вдруг там и на эту тему что-то умное сделали.

Прихожу сюда и мне начинают объяснять, что список не нужен и что я не понимаю, что такое O(). Исходя из этого, не вникая в дальнейшие детали, можно сразу прийти к выводу, что в Расте ничего особо умного на этот случай нет.

И тогда возникает вот этот сценарий: поулчил элемент из списка, отдал на сторону, потом снова начал с ним что-то делать, а в это время незаметно элемент уже кем-то был из списка удалён. И вот, прослышав про крутизну Раста, я подумал, а вдруг там и на эту тему что-то умное сделали.

А причем тут список? Это проблема общего вида - есть расшареный обьект и над ним производятся несовместимые в данный момент времени операции.

а раз это не проблема списка, а проблема ВООБЩЕ, то и массив и даже одиночный обьект будут ей подвержены.

Так при реализации списка массивом нельзя так просто расшарить элемент - при любой операции его индекс съедет. Или же нужно вести реестр расшаренных элементов и подправлять их индексы. Впрочем, без такого реестра и список не починить. Т.е. да, в чистом виде двусвязный список при условии расшаривания элементов опасен и без его доращивания дополнительной сложностью это не исправить. А список на массиве вообще не даёт возможности расшаривать элементы без доращивания функционала.

Так при реализации списка массивом нельзя так просто расшарить элемент - при любой операции его индекс съедет.

нету дна у растаманского костылестроения! они будут хранить в массиве указатели, и отдавать указатель.

А это как говорят в таких случаях - Вы это сами сказали… Значит сомнения таки есть… И вариант предложенный по созданию двусвязных списков действительно воняет.

Ну или я просто заметил паттерн в поведении Денчика. Вот, снова не удержался

И вот, прослышав про крутизну Раста, я подумал, а вдруг там и на эту тему что-то умное сделали.

Всё, что Rust даст «умного» на эту тему, это он может проконтроллировать в компайл-тайме, что на объект нет иммутабельных ссылок, если мы его собрались мутировать (х). Но это только для переменных на стеке (локальных). Для кучи то же самое делается уже в раетайме через Rc<RefCell>. И это же можно сделать и в С++.

(х) Т.е. если у нас есть какая-то структура данных, и есть указатели в её внутренности (итераторы, например), то эти указатели не протухнут при обновлении коллекции. Потому что обновление при этом будет запрещено.

Так можно, но тогда и раст ваш не нужен, подсчёт ссылок прекрасно работает и в других языках.

И так плавно «ваш раст - говно, в нём не сделать двусвязный список», через «ваш раст - говно, в нём не сделать двусвязный список без unsafe» трансформировался в «ваш раст - говно, в нём двусвязный список можно сделать не лучше чем на другом языке».

Тут вообще большой вопрос как лучше. Дело в том, что, как ты теперь уже знаешь, списки вообще самая всратая структура данных эва. Но при этом у них не отнять одного достоинства, практически уникального, и это не быстрая вставка, это не протухающие при изменении списка итератеры.

Вот посмотрим на ссылку, которую ты привёл в первом сообщении темы, список с курсорами. Как там эти курсоры создаются?

pub fn cursor(&mut self) -> Cursor<T>

Дело в том, что этот прототип функции вводит в заблуждение. Он использует штуку под названием lifetime elision, это когда именование лайфтайма опускается у единственного параметра функции и возвращаемого значения.

На самом деле там есть ’a и у ссылки на self и у курсора. В этом легко убедиться, нужно посмотреть объявление структуры Cursor, она тоже имеет «шаблонный параметр» в виде лайфтайма, а в прототипе функции он не упоминается.

А &mut'a self - это указание на эксклюзивное заимствование. Это значит, что курсор может существовать только один и пока он существует ничего с самим списком делать нельзя. Нельзя с такими курсорами даже quicksort в их списке реализовать, там нужны 2 курсора движущиеся навстречу друг другу.

Я уж не говорю о ситуации, когда бы ты наделал 100500 курсоров на один список, в разные позиции, и забавлялся бы быстрой вставкой по ним.

Вот предложенный мной тупейший двусвязный список на Rc<RefCell<Node>> эту главную и единственную полезную возможность двусвязного списка сохраняет. Итератором в нём может служить любая структура, содержащая Rc<RefCell<Node>>, она может не заимствовать сам список и потому может плодить любое количество итераторов. Если сам список уничтожется, то, в зависимости от реализации, освободятся либо ноды до первого итератора, либо все ноды, на которые не указывает ни один итератор. При этом итераторы при изменении списка выживают. Даже итератор, ссылающийся на удаляемую ноду, после удаления, будет продолжать ссылаться на ноду, только с его точки зрения это будет выглядеть, как будто все другие ноды списка удалились, а эта осталась. В любом случае, можно будет эту «мёртвую» ноду вставить в любое место этого или другого такого же по типу списка.

Главный недостаток такой реализации списка в том, что при каждом переходе итератора на соседнюю ноду будет происходить дрочка счётчиков ссылок и у покидаемой и у новой ноды. Однако, вспоминая тот факт, что итерация по списку и так предельно медленная, тут можно сказать «снявши голову по волосам не плачут». Если уж ты умудрился вляпаться в списки, да ещё и перебираешь их, то деваться некуда, терпи тормоза.

Так-то да, но это не очень интересно. Интересный случай - это когда объект участвует сразу в нескольких структурах, например, более, чем в одном списке.

Ты какую-то мутную тему придумал. Что это за элемент? Ну явно не сама нода списка, в ноде ссылки на соседние элементы, так что её никак в другой список не вставишь, не удалив при этом из предыдущего. Получается это содержимое ноды. А в какой виде? Если вставлено «по значению» то тоже не может, байты внутри одной ноды по определению только ей принадлежат. А если по ссылке, то тут у раста всё строго, Rc/Arc.

И тогда возникает вот этот сценарий: поулчил элемент из списка, отдал на сторону, потом снова начал с ним что-то делать, а в это время незаметно элемент уже кем-то был из списка удалён. И вот, прослышав про крутизну Раста, я подумал, а вдруг там и на эту тему что-то умное сделали.

Так сделали. Причём не так упорото как ты предложил, а сделали по-человечески. Почему тебя волнует только вопрос «удалён/не удалён»? А если он не удалён, а только наполовину изменён? И вот мы вспоминаем тип Rc<RefCell<Node>>. Кстати, я каюсь, обманул тебя, но не специально, а просто забыл что в расте ссылки всегда валидные, так что настоящая матрёшка такая: Option<Rc<RefCell<Node>>>. Мы же хотим предоставить последнему элементу возможность не ссылаться ни на какую ноду. Но сейчас смотри на послендий в списке конверт. RefCell. Знаешь что это такое? Это хранилище с возможностью заимствования. Сам по себе Rc, будучи указателем с разделённым владением, не позволяет изменять указуемое, поэтому внутрь и нужно класть либо Cell (штуку, заменяемую разом), либо RefCell. Т.е. чтоб добраться до содержимого ноды, тебе потребуется этот refcell позаимствовать. А чтоб ещё что-то делать, придётся снова заимствовать. Заимствовать для чтения можно параллельно, а вот для изменения - только эксклюзивно. Так что Раст и тут тебя спас.

Ты какую-то мутную тему придумал. Что это за элемент?

Например, LIRS-кэш.

Что мне даёт slice, чего мне НЕ дает вектор?

slice дает тебе выразить твое намерение, которое вектор не позволяет. Например то намерение, что ты дальше будешь модифицировать только ту часть вектора, что под слайсом.

Но хорошо ли это получилось у дизайнеров раста? Не знаю. Давай запость сюда свой код, который компилятор не принимает.

Слайсы сложно сделать неправильно))

Слайсы сложно сделать неправильно))

Че, правда что ли? Тогда смотри:

Предположим, что вектор — это список заданий, и мы хотим выполнять их двумя нитками. При этом одна нитка идет от начала вектора к концу, а вторая — от конца к началу.

То есть нам нужны два точно непересекающихся слайса, но их граница заранее неизвестна — она только существует (обычное дело в математике, гы-гы-гы). То есть да, конечно, граница лежит в переменной, но эта переменная может двигаться нитками (атомик наверно подойдет?). Или же две переменные, которые атомарно двигаются друг другу навстречу.

В расте так можно?

В плюсах можно че-то такое сделать, хотя и убого, например как-то так:

template<my::atomic_2_ints& slice_bound, my::sliceable_vector> class my::slice
{
  ...
};

меня интересовало не предполагаемое применение, а что вообще под идеей «один элемент в многих списках» понимает.

а что вообще под идеей «один элемент в многих списках» понимает.

Предположим, что у тебя есть коллекция (пусть даже вектор, но можно что-то и поумнее, например дерево) из людей, и вот по ним хочется ходить в направлении:
1. возрастании фамилии
2. возрастании имени
3. возрастании даты рождения
4. возрастания даты приема на работу

Для этого их прошивают 4 интрузивными списками. Получается каждый человек в 4 списках.

UPDATE: но если речь идет о den73, то спрашивать лучше у него

UPDATE: я кажется понял вопрос. Допустим, мы хотим найти самого опытного человека в компании и начинаем итерацию по списку «возрастание даты рождения». Однако мы считаем, что те, кто проработал менее года в компании, вообще не достойны рассмотрения, и удаляем их из списка. Вот и получается, что на каком-то шаге мы удаляем наш итератор.

И да, хотелось бы знать, как тут может помочь раст.

Решение, по-моему: отделять элемент списка от итератора по списку.

Вопрос почти по теме: а вот во всяких декларативных языках с навигацией (типа GraphQL) видимо считают данные иммутабельными, хотя по ним вполне может захотеться проитерироваться, мутировать и даже удалить кое-что. Языки с поддержкой этого есть?

Предположим, что у тебя есть коллекция (пусть даже вектор, но можно что-то и поумнее, например дерево) из людей, и вот по ним хочется ходить в направлении:

Кстати, пример абсолютно валидный. Список – это порядок. Если нам нужна коллекция сразу с несколькими порядками, то несколько (интрузивных) списков – это оно самое.

В расте так можно?

Нет, конечно. Ты наркоман что ли? Раст предназначен чтоб не трогать одно и то же из двух потоков, он специально сделан чтоб предлагаемая тобой срань не могла произойти.

Разделить вектор или слайс на 2 слайса по индексу можно. split_at(). Но как ты будешь менять слайс доступный второму потоку из первого?

Теоретически, ты можешь положить в Mutex слайс, потом в потоках захватывать мьютекс, доставать лежащий там слайс, откусывать от него слева или справа по слайсу, а оставшееся класть обратно. Но это вряд ли то что ты хотел.

Т.е. если алгоритм, который по сути дела требует блокировки (проезд машин через перекрёсток)

Не вижу тут никакой блокировки, вижу очереди — две очереди машин.

Предлагаю от аналогии перейти к чему-то реальному, например сетевой карте. В нее стоит очередь пакетов, причем (чтобы было более похоже на перекресток) — карта смотрит в локалку и пакеты хотят идти ровно к 2 хостам. Допустим (опять чтобы было похожее на перекресток) пакеты маленькие, и объединив их мы получим профит. Ну значит 2 очереди, из которых планировщик выгребает пакеты, объединяет их, и пускает в сеть.

И где тут блокировки?

Раст предназначен чтоб не трогать одно и то же из двух потоков, он специально сделан чтоб предлагаемая тобой срань не могла произойти.

В чем ты видишь проблему моего дизайна? Каким образом многопоток может сломать то, что я предлагаю?

Кстати, пример абсолютно валидный. Список – это порядок. Если нам нужна коллекция сразу с несколькими порядками, то несколько (интрузивных) списков – это оно самое.

Нет, конечно. Вставлять не в 1, а в несколько списков, это вообще лучше сразу вешаться.

Языки с поддержкой этого есть?

В персистентных структурах данных ты можешь итерироваться сколько хочешь, версия иммутабельна. Следующий раз, когда ты запросишь итератор, это будет уже другая версия контейнера (если ты не в снэпшоте).

не-не, я хочу ходить по коллекции и прямо под собой, сзади себя и впереди себя че-то удалять и вставлять; мне это реально надо было

если интересно где: это задача минимизации, где очередное решение получается как комбинация (функция) из имеющихся перспективных кандидатов, лежащих в моей коллекции

практически да, я имел 2 версии коллекции (старую и новую), но это же не то

Ну почему же, вставка в список – одна из самых дешевых (без учета анизотропности памяти) из всех структур данных. Вставка в фиксированное количество списков кратно дороже, но для мультиупорядоченности других структур толком-то и нет. Ну, будет не K списков, а К btree, оно разве быстрее будет?

Ну, будет не K списков, а К btree, оно разве быстрее будет?

Быстрее, если ты там сумеешь итераторы держать валидными. Но это по сути список на стероидах.

В чем ты видишь проблему моего дизайна? Каким образом многопоток сломает то, что я предлагаю?

Ну ты предлагаешь делить слайс динамически. slice1 = [0..k-1], slice2 = [k..N]. Т.е. первый может подвинуть k и поломать слайс второму, slice2[0] вдруг станет указывать на другой элемент, прямо посреди работы.

Если вернуться от слайсов к предложенной идее, то тебе типа нужно просто работать одновременно из 2х потоков с одним массивом. Но раст тебе говорит: нельзя так. Даже если элементами массива у тебя что-то простое, не факт что обновляться они будут атомарно.

Я про вставку. Вставка в btree – медленная в относительных числах, хоть и ограничена логарифмом сверху в худшем случае.

Ну почему же, вставка в список – одна из самых дешевых (без учета анизотропности памяти) из всех структур данных.

Нет, конечно. В начало/конец - да, хотя вектор в конец и дек в любой из концов быстрее. Но тут речь о сортированных списках, а это другое, тут каждая вставка - это сначала медленный линейный поиск места для вставки.

slice2[0] вдруг станет указывать на другой элемент, прямо посреди работы

это проблемы плохо сделанных слайсов, а не мои

slice2 либо должен поддерживать адресацию, синхронизированную с вектором, т.е. slice2[x] = vector[x], либо slice2[x] = vector[N-x] если хочется считать от 0

В ПСД можно делать снэпшоты (в Мемории они есть), когда иммутабельны именно снэпшоты (единица версионирования), а внутри снэпшота данные эфемерны, и там можно коллекцию менять, как хочется. Такие изменения не создают новой версии. Но вот как у этих коллекций будет со стабильностью итераторов при наличии обновлений – зависит от самих коллекций и желания их авторов с этим бодаться. Довольно просто обеспечить стабильность одного итератора, через которого делается обновление. А если хочется 100500 итераторов, то за это придется платить.

Вставка в btree – медленная в относительных числах, хоть и ограничена логарифмом сверху в худшем случае.

Дело может дойти до того, что я забенчу свой аналог btree, который предлагаю вместо списка (со стабильностью итераторов кстати). Мой прогноз: в среднем не хуже чем 2Т, а может даже лучше Т (Т — это время вставки в список). Предлагай ужасный бенч, который безжалостно порушит мои иллюзии, гы-гы-гы.

это проблемы плохо сделанных слайсов, а не мои

Как говорил мой препод по программированию: «это не у меня код с доски не работает, это у вас он не работает». Ты придумал чушь и теперь обвиняешь авторов либы что твоя чушь не работает. Так нельзя. Хочешь - пили свой собственный контейнер на основе слайса, в котором один поток работает с одним концом, а другой с другим. Можешь потоку, работающему с конца, сделать индексацию даже в обратном направлении. Слайс же - это 2 указателя, на начало и на после конца, они для твоей дури принципиально не годятся.

Слайс же - это 2 указателя, на начало и на после конца, они для твоей дури принципиально не годятся.

Годятся. Никто не мешает мне бегать от 2-го указателя к 1-му, а не так, как решили за меня растодизайнеры.

Да, кстати — по безопасности ниток замечания есть?

Довольно просто обеспечить стабильность одного итератора, через которого делается обновление. А если хочется 100500 итераторов, то за это придется платить.

Тут будет полезен список случаев возрастающей тяжести.

Мне например была нужна пара итераторов (хотя может и фиксированное любое число) для итерации, при этом вставка делалась в произвольном месте (не по итератору, а по порядку самой коллекции (ordered_map)), удаление делалось с конца (bulk delete устраивало).

Под это я думаю можно сделать быстро.

Не вижу тут никакой блокировки, вижу очереди — две очереди машин.

А очередь – это разве не блокировка? Если у тебя неблокирующая очередь, то тебе понадобится backpressure. Те же яйца, только в профиль.

Не совсем. Тут надо идти от множества задач. Потому, что структуры данных всегда делаются под алгоритм и его паттерны доступа к памяти. То, что у нас есть библиотеки готовых структур данных, – это просто исторический артефакт, отражающий общие закономерности на широком классе алгоритмов.

То есть да, конечно, граница лежит в переменной, но эта переменная может двигаться нитками (атомик наверно подойдет?). Или же две переменные, которые атомарно двигаются друг другу навстречу.

В расте так можно?

А оно реально нужно? Многопоточное работа с разделяемыми переменными – занятие очень дорогостоящее, и таких дизайнов в высокоуровневом, т.е. повседневном, коде нужно избегать. Низкоуровневые случаи, типа, мы очередь делаем, тут – да. Нужен полный детальный контроль, материализованный в соответствующих базовых структурах данных. Но сколько мы в день очередей разных пишем? Я – ни одной. Разве что если на собеседованиях (было пару раз дело).

Короче, смысл? Делаем низкоуровневый язык для написания очередей?

Оно не столько нужно, сколько недорого. Условия вида «вот тут у нас константа, хотя могла бы быть и переменная, а если ты не согласен, то пиши свою либу» непродуктивны.

Но сколько мы в день очередей разных пишем? Я – ни одной.

А когда-то потребуется. И вот именно тогда язык должен дать это сделать, а не как обычно «сегодня в колбасе очередях потребности нет»

Короче, смысл? Делаем низкоуровневый язык для написания очередей?

Одно время раст заявлялся как системный язык, если чё.

Я не про это. Разумеется, иметь возможность высокоуровнево писать мнопоточный код для простых структур данных, типа той же самой бокировки или различных очередей – это хорошо, и это, действительно, не трудно. Просто эти приемы (базовые структуры данных и алгоритмы) не масштабируются. И твой слайс с атомиком будет уже неэффективным, если ты делаешь какую-то прикладную параллельную обработку данных. Если ты там будешь продолжать думать в терминах атомиков, то умрешь в процессе отладки.

структуры данных всегда делаются под алгоритм ... то, что у нас есть библиотеки готовых структур данных, – это просто исторический артефакт

Для протокола: в эпиграфе мемории указано несколько иное мнение об относительной ценности алгоритмов и структур данных.

На самом деле конечно да, все это в обе стороны работает.

И твой слайс с атомиком будет уже неэффективным, если ты делаешь какую-то прикладную параллельную обработку данных.

Я не про это. Нитка начиналась с того, что «слайсы сложно сделать неправильно». Я по-прежнему считаю, что растодизайнеры все же смогли, несмотря на сложность. Это талант, я считаю.