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

Здесь есть правила.

Попробуйте начать соблюдать правила форума сами, стучащий вы наш. А то ведь ваши действия с этими самыми правилами вступают в лютое противоречие: Rust и двусвязный список (комментарий)

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

Чисто для протокола отмечу, что aist1 не нарушил правила:

Тексты на иностранных языках (КРОМЕ АНГЛИЙСКОГО) снабжайте комментарием так, чтобы в дискуссии смогли принять участие посетители сайта, не знакомые с этими языками.

Допускается использование других языков ПРИ ЦИТИРОВАНИИ ВНЕШНИХ ИСТОЧНИКОВ, сообщений об ошибках, исходных текстов программ и в других подобных случаях.

Совершенно нормальные правила. В РФ русский язык является государственным вообще-то. Предложение поменять правила так, чтобы снизить обязательность его использования на форуме является атакой на русский язык. Для примера, на реддите можно писать на иврите или по-китайски? Или на StackOverflow? Если нельзя, то почему это не дискриминация?

У меня лично претензий к aist1 нет от слова совсем. И я уже приводил пример фраз, которые можно было бы и на русском употребить, но этого не делают. Как в силу культурных традиций, так и в силу устоявшихся обычаев. Комментарий этот, правда, стараниями ревнителя порядка den73 был удален. Но тем не менее.

Он, конечно, может стриггериться и на уже прочно вошедшие в обиход «premature optimization is…» и «don’t shoot the pianist…»

Но стоит ли из-за одного странного персонажа «руку сбивать»? Как по мне, так нет.

Ну можно же абзац целиком привести, чтобы была видна не только буква, но и дух правил:

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

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

Тут дело обстоит не так. Особенность нашей работы состоит в том, что мы из раза в раз переписываем один и тот же код, с некоторыми вариациями. Мы в своей работе (а вне работы мало у кого есть свои проекты) редко сталкиваемся с алгоритмической новизной. Поэтому мы оттачиваем «искусство программирования» при довольно таки примитивной матчасти.

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

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

Странно что ты начинаешь ответ с «Тут дело обстоит не так», а после этого пишешь ровно то, что я имел в виду :-)

Вот «трансферируются» не звучит по русски. Хотя я часто говорю кальками (приватные и публичные члены-методы класса например), но в случае кривого звучания лучше все же переходить на не-кальку, в твоем случае — «переносятся». Или тогда уж «трансферуются».

Для примера, на реддите можно писать на иврите или по-китайски? Или на StackOverflow? Если нельзя, то почему это не дискриминация?

А с чего ты взял, что нельзя? В США языковой дискриминаци нет. Пишешь на том языке, на котором хочешь. Если это создает дискомфорт для аудитории, то тебя просто не читают и ответов ты не получишь.

Государственный язык обязателен для государственных органов власти. Граждане на нем разговаривать не обязаны. Иногда он является обязательным на рабочем месте. Тогда это прописывается явно в трудовом договоре. Уволить человека за то, что он не говорит по русски, нельзя, если русский язык (конкретный уровень владения: чтение, разговорный) не был требованием при принятии на работу.

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

)))

Ты правишь свои сообщения. И я иногда на этом глючу.

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

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

Покажи ответы на русском на SO (не на спец версии «SO на русском», а на общем SO). Или попробуй такой ответ написать и расскажи о своих впечатлениях.

Государственный язык обязателен для государственных органов власти.

Вообще-то в нашем законе о гос. языке написано не только это (стоит его дочитать). Действительно, граждане не обязаны разговаривать на нём. Но тут есть правила форума, и они предписывают общаться на русском языке. Я правильно понял, что ты это не признаёшь и не собираешься исполнять?

Вот «трансферируются» не звучит по русски.

Ну, извини)) Переводчик из меня «так себе». Мы тут вообще не «рунглише» думаем. А некоторые даже говорят, потому что русских эквивалентов слов даже не знают.

Что касается форумов, то они не могут устанавливать какие-то требования сверх действующего законодательства.

Вообще-то могут. Хотя вопрос, конечно, непраздный. Вряд ли требования могут быть противоречащими закону, но я не знаю, можно ли ограничить языки общения. Давай для начала допустим хотя бы все языки народов РФ, к коим английский не относится. Будут тут все желающие писать по-украински, по-татарски и по-чеченски.

Вообще-то в нашем законе о гос. языке написано не только это (стоит его дочитать).

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

Я правильно понял, что ты это не признаёшь и не собираешься исполнять?

С чего ты взял? Я здесь общаюсь на русском языке. Другие участники не нашли в моих комментариях нарушений правил форума. Цитата, которую я привел, в моей голове звучит на английском языке. Я её не перевожу. И поэтому привел в оригинальной форме.

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

Ты имеешь право не читать то, что пишут другие люди.

Нет, здесь не так. Здесь есть правила и ты должен их соблюдать, если пишешь сюда. Ну в принципе конечно понятно, как будет дальше ситуация развиваться: все на самом деле всё поняли, что ты хотел сказать, правила будут соблюдаться всё хуже и хуже и в итоге форум станет выглядеть как первая страница великого русского романа «Война и Мир». Не знаю, как бы аккуратнее сформулировать, чтобы не попасть под справедливое возмездие, но тот роман рассказывает, как вслед за чужим языком пришли и носители чужого языка, и не только на страницы романа, а и на территорию. Их прогнали, но за это пришлось заплатить каким-то количеством жизней. Хорошее знание того языка никак не помогло уменьшить сумму выплаты. Выживешь ли лично ты в следующем сезоне этого сиквела? Как знать, время покажет. Пока что сила на вашей стороне. Чтобы выразить своё несогласие с этим, отправлю-ка я тебя на какое-то время в список игнорирования.

Ааа, да ты уже сам перелоцировался в метрополию языка. Тогда всё ясно. Рекомендую тогда погуглить фотографии «американо-японские дети в 1942 году»

Пока что сила на вашей стороне.

О, великий ЖГ! Какая еще «наша сторона», какое еще «выживешь ли ты»? Специально для тебя: скользкий путь.

Да, я твои аргументы воспринимаю серьезно, потому что по моей шкале ты «сам ешь свою собачью еду» (eat your own dog food). Ты просто раздул проблему на пустом месте.

Когда я смотрел в сторону реализаций аллокаторов в последний раз (а это было лет 15-17 назад), то продвинутые аллокаторы использовали разные арены для объектов разного размера.

Это скорее ставит под сомнение пользу от использования пулов. По крайней мере одну из полезных фич пула. И никак не помешает ушатать кучу.

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

Если, как в примере, полезная нагрузка ноды составляет 64 байта, + 2 указателя + сколько-то на выравнивание, ну предположим, куски у нас по 128 байт. Это значит список на 10 млн, содержа 640 мегабайт полезных данных, отожрёт 1.28 гига в арене по 128 байт. А когда он освободится, у нас будет в арене 10 млн таких кусков. Много ли будет других желающих на < 128 байт?

Без дефрагментации кучи эту память нормально не использовать и системе не вернуть. Если после этого список из 10 млн структурок по 64 байта будет трансформироваться в список из 2.5 млн по 256 байт, то придётся выделять в другой арене.

В этом плане как раз создание+наполнение+удаление списков (особенно если списки разной емкости) гораздо меньше фрагментирует хип, чем создание+наполнение+удаление векторов.

Не верю. Большие освобождённые куски куда-то да пригодятся. Может возникнуть соблазн заявить, что вот эти куски от предыдущего роста вектора (N/1.7, N/(1.7)^2, …) нужно учитывать как мёртвый груз, но в общем не факт что даже будучи реально мёртвым грузом увеличат потребление памяти больше чем список, в котором к каждой ноде добавляются дополнительные указатели + выравнивание + размер буфера.

Ну и главное, мой поинт не в том, чтоб заполнять вектор 6 гигабайтами данных. Если бы я реально собирался заполнять такие коллекции, то, по результатам моих же измерений, мне следовало бы брать не вектор, а список, он на таких размерах становится быстрее. Нет, мой поинт в том, что проблема реаллокации вектора не влияет на более-менее вменяемых размерах векторов (условно, до 100 мегабайт), и, соответственно, незачем эту реаллокацию бояться. Там, где список догоняет или обгоняет вектор (гигабайт или даже 10), вообще не стоит вот так наивно заполнять простой контейнер в памяти, это будет упорото в любом варианте. Если это будет вектор, то вектор с преаллокацией, или много векторов, если список, то хотя бы развёрнутый. А скорее всего при таких объёмах вообще нужно будет работать напрямую с файлами.

Моё утверждение («списки бесполезны») - это не фактическое утверждение и потому не может быть истинно, а логический вывод, основанный на двух фактических утверждениях (которые, соответственно, могут быть истинны или ложны). Эти утверждения:

1. Списки неэффективны. Даже не в общеизвестных операциях типа выбора элемента по индексу, но и в том, что принято считать удобными операциями для списков, например вставка в начало или последовательный обход.

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

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

Второе утверждение - это утверждение о несуществовании. Доказать такое возможно только в очень редкий случаях. Я вот не могу. Я могу только решать предложенные задачи.

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

У тебя есть id машины. И как ты узнаешь id следующей за ней машины?

Я же уже написал. Ну ок, повторю.

auto segment_index = car_locations[id];
auto car_index = linear_search_car(id, road_segments[segment_index]);
if(car_index < road_segments[segment_index].size() - 1) return road_segments[segment_index][car_index + 1].id;
// дальше возвращаем первый элемент первого непустого сегмента с индексом больше segment_index или фейлимся если такого нет.

Теперь твоя очередь, а то ты халявишь и мои задачи не решаешь. С вертолёта по рации сообщили что тебе нужна 3я по счёту синяя нива. Найди её. Синих нив в твоей симуляции < 1%.

Здесь есть правила и ты должен их соблюдать

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

Перефразируя: не существует реалистичных задач в которых списки были бы эффективнее.

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

1. Список используется совместно с какой-нибудь поисковой структурой. Например, в LRU-кэше есть интрузивный список, задающий «свежесть» записи и хэш-таблица для поиска элементов. Я ни разу не видел, чтобы кто-то хотя бы просто намекал на то, чтобы сделать этот список одним массивом. Список массивов (list of chunks) тут тоже не имеет особого смысла, так как этот список практически никогда не читается. А вставка и удаления в/из него интенсивные.

2. Я приводил ссылку на график своего бенчмарка n-арного поискового дерева, упакованного в массив и std::set<>. Там видно, что когда датасет влезает в L2 (какой-то Core 2 Duo типа Q9300 @3.3HGz), произдодительность обоих структур +/- одинакова. И только когда мы выпадаем в RAM, упакованное дерево вырывается кратно вперед. Сейчас кэши большие (и будут расти). Для моего R9 5950X это 32MB на CCD. А для серверных CPU мы бодро идем к гигабайту. Т.е. твое утверждение нужно, как минимум, поправить условием целевого объема данных (например, «датасет гарантированно не вмещается в кэш»).

Так ты её плохо решил. Это решается за одно обращение к хеш-таблице (константное время) и один переход по ссылке на следующий. Я не могу считать решением то, что ты написал. Если в Расте всегда принято так программировать, то давай не будем зря тратить время.

С вертолёта по рации сообщили что тебе нужна 3я по счёту синяя нива. Найди её. Синих нив в твоей симуляции < 1%.

Буду перебирать список и читать поля. Конечно, это может оказаться медленнее массива, а может и не оказаться. Думаю, что чем больше объём информации о каждой машине, тем менее значима будет укладка какой-либо информации о машинах именно в вектор. Если, допустим, ты хранишь в своём массиве не запись о машине (а её сложно хранить из-за переменного размера), а указатель, то тебе всё равно надо будет подтягивать полную информацию о машине, которая при достаточном количестве машин в кеш не поместится, поэтому потеря от перехода по ссылкам практически исчезнет.

Ну мне так себе цитатку принесли, урезанную под определённую точку зрения. Первую фразу «общайтесь на русском языке» выкинули. Я не стал называть вещи своими именами, но если назвать, то это называется «выдернуть цитату из контекста».

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

Нет, контекст никак не изменяет смысла цитируемого отрывка.

эти правила можно было бы перевести

А процитированный кусок означает, что можно было не переводить. И не надо песен о «нарушении правил».

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

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

Список массивов (list of chunks) тут тоже не имеет особого смысла, так как этот список практически никогда не читается. А вставка и удаления в/из него интенсивные.

1. Если LRU у нас крутит одна нить, то как раз list of chunks у нас будет быстрее и с (почти?) не худшей латентностью, чем double linked list или linked list (при условии что размер чанков равен строке кэша).

2. Если мы хотим делать все это растоугодно, то вместо list of chunks можно взять Btree of chunks; тут варианты:

2А. считать, что, хотя внутри Btree unsafe, но оно все равно правильное (такое в принципе возможно, например при формальном доказательстве)

2Б. сделать растоугодное Btree исключительно на владеющих ссылках и без unsafe

Так вот, я протестую против того, чтобы можно было взять и кусок сообщения написать не на русском языке

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

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

В устной речи другое дело. Там пока вспомнишь, как оно по-русски, можно целое предложение успеть сказать.

А вот в письменной лучше стараться покрасивее.

и принуждает меня читать английский

Странно, что никто еще не сказал, что английский язык по факту международный. Как ты сможешь его не читать и повышать свою грамотность — для меня загадка.

Были попытки сделать другие языки, но они не пошли, Например, Эсперанто — это испорченный испанский. Кроме того, там есть падежи, так что шансов у него было мало. У русского с его падежами и нетранзитивностью где только можно шансов на международный язык еще меньше.

Ну кстати можно попробовать и стукануть.

Но я пытался сделать так, чтобы господин собеседник использовал русский язык из уважения к духу правил, а не к их букве. Это не получилось и он чётко выразил свою позицию, что его свобода ему важнее. Что вся эта ситуация в целом означает? Что позиционирование ресурса как русскоязычного размывается. 好的. Для меня это хуже, чем выступления Хрюнделя, поэтому Хрюндель не попал в игнор, а aist1 - попал.

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

UPDATE: а вот твои иероглифы правила нарушают. Согласно букве правил.

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

Также русский всё ещё является международным на территории бывшего СССР. Отказ от своего языка ведёт нацию к деградации, и это не мой выбор.

Настучи на моё сообщение - мне интересно, что будет. Так-то никакой разницы нет. Что aist1 привёл какой-то текст без оформления цитаты и указания источника, что я. Я могу найти места, где эти иероглифы встречаются и сказать, что я что-то процитировал. Китайский - тоже международный язык, язык ООН и всё такое. Если мы за равноправие, то иероглифы имеют такое же право находиться здесь, как и английские слова. Да, в правилах этого пока нет, но ведь aist1 предлагал их поменять, чтобы не было дискриминации. Я тоже предлагаю это сделать. Необходимо добавить китайский и языки народов РФ. Ыра кун пултар!

международным становится язык доминирующей страны

и как ты это исправишь своими потугами?

слово «потуги» здесь выглядит не совсем уместным. Я в настоящий момент не сру и не рожаю.

Если мы за равноправие, то иероглифы имеют такое же право находиться здесь, как и английские слова.

Нет, я не за равноправие. Я за то, чтобы мне изучать тот язык, который
1. проще
2. содержит больше полезных текстов

И тут английский явно лучше китайских иероглифов.

Т.е. ты готов ущемлять интересы народов РФ ради интересов англо-американского глобализма?

И тут английский явно лучше китайских иероглифов.

Это только твоё субъективное мнение. Когда ты уже выучил китайский, тебе становится проще читать тексты, потому что они плотнее. Monk не даст соврать.

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

слово «потуги» здесь выглядит не совсем уместным. Я в настоящий момент не сру и не рожаю.

Наоборот, оно вполне уместно.

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

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

Т.е. ты готов ущемлять интересы народов РФ ради интересов англо-американского глобализма?

Нет, язык программирования на английском — это не ущемление интересов народов РФ ради интересов англо-американского глобализма.

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

Использование чужого языка - это ущемление интересов всех, кто не учил этот язык с пелёнок.

Причина неуспеха проекта ЯП состоит прежде всего в кратном (стократном) превышении предложения над спросом, а также в приверженности масс ИТ-шников традициям, моде и мнению авторитетов. Однако успешные ЯП на русском существуют, их как минимум два.

То есть ты решил поущемлять интересы нерусскоязычных со своим языком программирования, и теперь возмущаешься, что мы время от времени ущемляем твои интересы?

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

Причина неуспеха проекта ЯП состоит прежде всего в кратном (стократном) превышении предложения над спросом

Все ровно наоборот. Спрос есть, предложения нет.

Тебе не хватает языков программирования?

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

Мы — это айтишники, которые говорят и думают на рунглише.

Само по себе ущемление придумал не я.

Нет, это ты решил поущемлять нас, при этом лицемерно взывая к справедливости.

Если выбирать между «я ущемляю» и «меня ущемляют», я выберу первое, и ты, по всей видимости, тоже.

Ты не угадал. Я попытаюсь разрулить ситуацию, выбрав и не первое, и не второе.