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

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

Скорее, мне не хватает языкА программирования. Правда, при том, что он будет eDSL-контейнером (чем-то похожем на лисп), условно можно считать, что мне не хватает языкОВ программирования.

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

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

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

Думай дальше.

А я её никак не сдержу ввиду ничтожности своих масштабов. Более того, в РФ есть специальные органы по защите РЯ, и они тоже ничего сделать не могут. Я только ставлю вопрос на повестку дня, больше ничего сделать не могу. Но моё мнение состоит в том, что человек, который легко отказывается от такой части своей личности, как язык - это дефективный человек. Например, Довлатов вот что на эту тему писал:

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

которым английский впился в русский и поедает его

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

из уважения к духу правил

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

Более того, в РФ есть специальные органы по защите РЯ, и они тоже ничего сделать не могут.

Да, потому что у них неверна вся концепция.

Она не настолько уж неверна. Ты вряд ли понимаешь в этом намного больше, чем они. В этом никто ничего не понимает, всё мышление на эту тему у большинства сводится только к набору мемов. Я немного понимаю. Чуть больше, чем они и наверняка намного больше тебя. Но тем не менее, мне легко задать вопросы, на которые мне нечем ответить.

Но моё мнение состоит в том, что человек, который легко отказывается от такой части своей личности, как язык - это дефективный человек.

1. Говоря и на рунглише, и на английском, я не отказываюсь от русского.

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

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

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

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

1. Возможностей выразить мои мысли в той форме, которую я считаю правильной, а не в той, в которой мне ее навязывает автор языка программирования. Если совсем грубо, то мне нужны eDSL.

2. Поддержка eDSL средами программирования.

3. Крайне желательна консистентность eDSL, чтобы не получить вавилонского столпотворения.

4. От компилятора требуется поддержка всех сред в рантайме и максимальная интероперабельность между ними (речь о GC, *malloc, refcounter, ...).

5. От компилятора требуется поддержка всех доступных систем валидации/верификации кода.

6. Куски компилятора в рантайме по моему желанию, а не навязанные и целиком, как в образе лисп-машины.

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

и наверняка намного больше тебя

Весьма забавное мнение.

Первая квалификация программиста: понимать, кто знает больше него в данном кусочке предметной области, а кто — меньше.

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

Он сможет сделать мне partial specialization моего кода (видимо да, если он оптимизирующий компилятор)? А закинуть в рантайм этот его кусок, который делает partial specialization, я смогу?

По «Allegro CL language server protocol» гуглится только «CL language server protocol». То есть похоже там нихрена не сделано для интеграции eDSL с language server protocol.

Вообще, из лисп-подобного в направлении eDSL я слышал только про Racket.

partial specialization

Частичное раскрытие макросов? Скорее всего придётся делать так же как частичное применение функций. Т.е. (lambda (a) (lambda (b) (lambda (c) ... ибо макросы в лиспах императивны.

А закинуть в рантайм этот его кусок, который делает partial specialization, я смогу?

Если тебе нужно частичное раскрытие макросов в рантайме, то зачем тебе вообще именно частичное раскрытие макросов? Это исключительно техника оптимизации, а макросы должны отрабатывать только при вмешательстве девопса (обновить код/конфиги) или админа (обновить конфиги), но точно не при нормальной работе в ответ на обычные действия пользователей. Просто чтобы вырезать из рантайма незначительную часть компилятора (т.к. значительная всё равно занимается оптимизациями и генерацией машинного кода и нужна для абсолютно любых макросов)?

При чём тут LSP? Среды разработки VSCode и ей сочувствующими не ограничиваются.

Ах, да.

Он может и ненужные куски компилятора удалять из рантайма.

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

Хорошо, скажи что тебе нужно, но чего нет LSP. И да, LSP это для всех, а не для VSCode (которая overbloated и дикий тормоз)

Нет, partial specialization это не только для макросов. У тебя есть функция от 2 аргументов, f(x,y) и тебе в рантайме стало известно, что второй аргумент допустим будет 8. Тебе прямо в рантайме нужна оптимизированная функция g(x)=f(x,8). При этом функция f была написана именно как функция, а не макрос — поскольку это компилятор должен подстраиваться под наши хотелки, а не мы под него!

UPDATE: При этом можно иметь в рантайме исходный код f и кусочки другой инфы о ней, но не весь исходный код твоего проекта.

UPDATE2: понятно, что на этапе компиляции мы можем сказать «вот эти функции может потребоваться специализировать в рантайме, а вот эти — точно нет, не трать на них время».

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

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

или админа (обновить конфиги), но точно не при нормальной работе в ответ на обычные действия пользователей

Ну вот админ хочет ALTER TABLE MyTable... в виде команды прямо в рантайме. SQL это позволяет, а у тебя придется сказать «нееет, правь конфиг и перезапускай сервер».

Список используется совместно с какой-нибудь поисковой структурой. Например, в LRU-кэше есть интрузивный список, задающий «свежесть» записи и хэш-таблица для поиска элементов.

Да, пожалуй LRU - самый похожий пример того, где список в тему. Пока он используется только для поддержания LRU и не возникает необходимости, например, выдать 100 последних использованных элементов. Однако к этому примеру у меня вот такая претензия: список тут как бы и не используется как контейнер. Для владения памятью и для поиска достаточно вот той поисковой структуры, а список тут как бы и «случайно» образуется.

Вообще, надо потратить немного времени и забенчить реализацию LRU на массиве.

Там видно, что когда датасет влезает в L2 (какой-то Core 2 Duo типа Q9300 @3.3HGz), произдодительность обоих структур +/- одинакова. И только когда мы выпадаем в RAM, упакованное дерево вырывается кратно вперед. Сейчас кэши большие (и будут расти).

У меня ровно противоположное наблюдение. Давай сравним сейчас и 20+ лет назад. Так как нас интересует эффективность алгоритмов, сравнивать будем задержки не в наносекундах, а в циклах CPU. Тогда у тебя был компьютер в 1 CPU, примерно типа 1 Ггц, с DDR400 памятью размером 64 или 128 мбайт. Сверяемся с таблицей латентности и видим, что латентность памяти в наносекундах в столбце «первое слово» с тех пор не изменилась, но выросла скорость памяти. Чтоб сильно не подыгрывать старым процессорам будем брать латентность 4го слова. 20 нс для DDR. В современной DDR4 3200 такая латентность будет около 10 нс.

Теперь смотрим кэши. Мне лень искать латентности кэшей третьепня или атлонов, давай считать что они примерно не изменились. У атлонов (не тех которые в слотах) было 64 + 64 кб L1, и 256 кб L2.

Согласно нагугленной мной картинке, якобы достанной из док от интела, современные процессоры имеют латентность L1 в 4-5 циклов, L2 - 12 циклов, и L3 - 42, а у памяти латентность как L3 + латентность DDR. Давай для простоты считать что раньше было +/- так же, только вместо L3 был контроллер памяти, добавлявший к задержке L2 ещё 20 циклов. Теперь сравниваем иерархию памяти на одно ядро, RAM будем считать следующим уровнем после последнего кэша было

• 1ГГц, 1 цикл/нс
• L1 128кб 4-5 циклов
• L2 256кб 12 циклов
• L3 64МБ 12 + 20 + 20 = 52 цикла (RAM)

Стало

• 3ГГц, 3 цикл/нс
• L1 64кб 4-5 циклов (зато, вроде, увеличилась ассоциативность)
• L2 256кб 12 циклов
• L3 32МБ 42 цикла
• L4 64GB 42 + 30 = 72 цикла (RAM)

И где тут ты разглядел улучшение? Я вижу заметное ухудшение, L3 уменьшился в 2 раза. Он стал чуток быстрее, однако если вспомнить, что он общий на 8 ядер, в реальности тебе гораздо меньше достанется, пусть даже половину отъешь, 16 мегабайт. И никакие будущие гигабайтные кэши тебе не помогут, они, ввиду своих размеров, чуток добавят латентности себе и RAM и только отчасти скомпенсируют рост частот и количества ядер.

Так что алгоритмически стоимость неуважения к кэшам со временем только растёт.

Однако к этому примеру у меня вот такая претензия: список тут как бы и не используется как контейнер. Для владения памятью и для поиска достаточно вот той поисковой структуры, а список тут как бы и «случайно» образуется.

Довольно близко, а может даже именно так.

И как в расте предполагается разруливать эти вопросы? Ну там lifetime какой всобачить, или как?

Так что алгоритмически стоимость неуважения к кэшам со временем только растёт.

Не факт что прям уж растет, но не снижается точно — за одним исключением: повышается параллельность доступа (как к той же DDR4).

Ну и вообще по моему мнению железо начиная с 2000 года практически стоит на месте по латентности (хотя растет по объему и чуть-чуть по пиковой скорости).

ибо макросы в лиспах императивны

Да, это ключевой момент!

А вот специализация функций, по сути, декларативна.

То есть программист может написать макрос под любую конкретную специализацию любой конкретной функции, но не должен делать это, так как этим должен заниматься компилятор. У него это и лучше получится, кстати.

Так что тут дорожки у меня с лиспом, похоже, расходятся.

Вообще, надо потратить немного времени и забенчить реализацию LRU на массиве.

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

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

2. Поддержка eDSL средами программирования.

по п.2 общелисп не подходит. Была статья про Racket, в котором есть для этого специальный чемоданчик костылей. Может быть, подошло бы подмножество.

3. Крайне желательна консистентность eDSL, чтобы не получить вавилонского столпотворения.

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

От компилятора требуется поддержка всех сред в рантайме и максимальная интероперабельность между ними (речь о GC, *malloc, refcounter, …).

в мире лиспа и такое было сделано, кто-то когда-то comp.lang.lisp мне об этом рассказывал. Сейчас я иду к тому, чтобы сделать rc+gc в Обероне, но вот болтовня на форумах отвлекает. Но это накладывает ограничения на реализацию тех же контейнеров и ввода-вывода. Например, в лиспе read выделяет память на куче. Даже в подсчёт ссылок то, что можно прочитать read-ом, уже не запихать.

5. От компилятора требуется поддержка всех доступных систем валидации/верификации кода.

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

6. Куски компилятора в рантайме по моему желанию, а не навязанные и целиком, как в образе лисп-машины

В лиспе компилятор можно выкинуть.

Он сможет сделать мне partial specialization моего кода (видимо да, если он оптимизирующий компилятор)? А закинуть в рантайм этот его кусок, который делает partial specialization, я смогу?

В SBCL есть примерно 3 вида макросов внутри компилятора, которые раскрываются на разных этапах компиляции. def-ir1-transform - это один из них. В т.ч. они отвечают за оптимизации при наличии конкретных типов. Но так-то многое там в твоих руках.

Я поставил иероглифы в порядке доведения до абсурда исходной позиции aist1 . Это ведь вилы: если дискриминируют английский, то товарищ недоволен. И оказывается, ЛОРу придётся поменять правила. Но если дискриминируют все прочие языки, кроме русского и английского, то это всех устраивает. Тут надо выбрать трусики или крестик: либо мы против языковой дискриминации, и тогда надо разрешить иероглифы. Либо мы против дискриминации только английского. Т.е., мы русскоязычные ИТ-шники, говорящие на рунглише, здесь народ и важна наша точка зрения. А ваша - не важна. Если вы хотите чисто русскоязычное ИТ, или русско-китайское, то просто заткнитесь. Ну в этом случае, если я стучу, то я ничем не хуже вас, просто у меня пока есть молоток, а у вас пока нет.

Тут уместно напомнить, что латынь примерно лет 500 выполняла ту роль, которую сейчас выполняет английский. В отличие от английского, латынь - это чёткий язык, логичный и красивый (во всяком случае, я слышал такие оценки) и в культуре он укоренён гораздо лучше. Однако что-то пошло не так и теперь вряд ли кто-то способен слёту сказать, что означает «ювенес дум сумус». А ещё какие-то 160 лет назад всё было по-другому.

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

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

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

Хрен с ним, пиши иероглифами, а то это ж невозможно.

латынь … и в культуре он укоренён гораздо лучше.

Да ладно?! Где вы латынь слышали за пределами мира медицины?

то просто заткнитесь.

Ну в этом случае, если я стучу

Притом дальнейшей падение русской цивилизации

прикоснувшись к великой западной технической культуре

Господи. Чур меня. Лечитесь, батенька.

ПыСы:

выручки не хватило даже на один толковый язык программирования

Вот оно. Всё ещё за свой недо-язычок топим?

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

Я не вижу никакой концептуальной разницы(х) между chunk_size = 1 и chunks_size = 256 / sizeof(entry_type). При размере записи более 256, список вырождается в обычный связный. 256 = 4х64, 4 размера линии кэша – оптимальный размер чанка для гибридных контейнеров.

(х) У нас всё равно структура на основе указателей. Её «гибридный» характер ограничен сверху. Тогда как пример на монолитном массиве – не ограничен.

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

Эх, Денчик-Денчик. Ну как можно вот так взять и на ровном месте обосраться?

Я предложил решение, за O(1) находим сегмент дороги и потом линейным поиском в массиве ищем машину. Ты, в ответ мог бы написать «за одно обращение к массиву» и получил бы то самое желаемое константное время. Я бы спорил с тобой, писал бы что реальный поиск займёт небольшое время, оно вообще пренебрежимо мало, и структура изначально планировалась под другую задачу, а ты бы отвечал мне «O(1) и не**ёт!».

Но ты вместо этого написал «за одно обращение к хеш-таблице». А ты знаешь как они работают? Так вот так и работают, за O(1) находят начальное место, а потом ищут линейным поиском. Если хэш-функция хорошая и реализация современная, то линейный поиск будет в массиве и искать придётся недолго, среди ~10 элементов, например. Если хэш-функция неудачная и/или реализация плохая и несовременная, то искать придётся внутри связного списка из 100 элементов.

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

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

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

Да, пожалуй LRU - самый похожий пример того, где список в тему. Пока он используется только для поддержания LRU и не возникает необходимости, например, выдать 100 последних использованных элементов.

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

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

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

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

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

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

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

Вернемся к случаю «использование монолитного массива для реализации связного списка». У обычного связанного списка (со статичной аллокацией элементов) могут быть простые и бесплатные итераторы, которые не инвалидируются при изменении контейнера, в отличие от вектора.

Если бы таких итераторов не было, то список на основе вектора был бы лучше в подавляющем большинстве случаев, так как для вставки элемента в такой список нужно было бы сначала найти позицию, а это сразу O(N). Но итераторы есть, и интрузивный список – это просто оптимизация на основе этой возможности, сводящая итератор к просто обертке. Это дает возможность строить комбинированные структуры данных, эксплуатирующие базовые свойства списков. За счет чего и работают LHM и LRU.

Т.е., если вспомнить твое исходное утверждение:

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

То я считаю, что привел два контрпримера (с учетом фактора итераторов).

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

Поскольку den73, как говорит, поместил меня в игнор, я отвечу на исходную тему. Я хочу прояснить и обосновать то, ч чего эта ветка дискуссии началась.

Я расценил его предложение как предложение всегда переводить всё на русский сразу. Возможно, ввиду имелось не это, а просто дать еще и перевод к английскому тексту.

Далее, я попросил его не педалировать тему, так как именно такая интерпретация (писать только на русском) будет противоречить современной практике многоязычности и может послужить основой для обвинений ресурса (LOR) в языковой дискриминации. С моей стороны никаких обвинений ресурса не было и не будет.

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

Если den73 говорит про мою позицию что-то сверх этого, то это – его личная интерпретация событий.

warning! attension! uvaga!

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

крч я вас предупредил.

https://kjellkod.wordpress.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/

Да ладно?! Где вы латынь слышали за пределами мира медицины?

Ты неуч, не знаешь ни черта. Марш учить матчасть.

за O(1) находим сегмент дороги и потом линейным поиском в массиве

Неправда, в общем случае ты не найдёшь его за O(1). Т.к. никто не сказал, что id-ы машин будут от 0 до N. Машины будут появляться и исчезать, поэтому могут возникнуть дыры в id-ах. Либо возникнет утечка памяти, либо понадобится отслеживание дыр, либо нахождение сегмента дороги по машине потребует обращения к чему-то вроде хеш-таблицы или B-дерева.

Если же id-ы машин будут от 0 до N, то я точно так же буду искать их через массив, как и ты.

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

сравнивать надо на языках здорового человека. це или це++.

на джаве пишут только метросексуалы и квир-активисты.

Нда, я-то думал, Хрюндель свои собственные выводы постит, а тут действительно целая секта жуликов. Они для всех замеров используют только тип-значение (value type) размером в одно слово.

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

Интересно, скоро ли у них дойдёт дело до плоской Земли. Но что ж, есть целых два повода для радости:

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

на джаве пишут только метросексуалы и квир-активисты.

Пчелы против меда! В смысле, чувак, ты на ЛОРе. Который, ну, это самое.

выводы однозначны.

LinkedList has its uses. It is not horrible to use LinkedList,. but make no mistake about it. In the area of number crunching there is one who almost always rule. The Array is King.

number crunching

Вот кстати, в такой интерпретации вполне годное заявление, поскольку определяет, когда массивы лучше: когда у вас изначально «табличная» организация данных. Такое заявление, правда, уязвимо к дальнейшей критике. А что, если организация данных древовидная или графовая? Потому, что «number crunching» – это тоже весьма расплывчатая формулировка. Это не всегда матрицы.

Ты неуч, не знаешь ни черта. Марш учить матчасть.

Слушаю и повинуюсь. Ссылки будут?

Неправда, в общем случае ты не найдёшь его за O(1). Т.к. никто не сказал, что id-ы машин будут от 0 до N.

Будут. Я же сам их добавил, суррогатные ключи, после чего ты мне предложил найти машину по id. У тебя память золотой рыбки что ли?

Впрочем, это абсолютно неважно, ну пусть хэштаблица. Обозначим длину «конфликтующих» записей в хэш-таблице n1, а длину сегмента n2. Считаем n2 ~ 10*n1. Сравниваем:

• хэш-таблица + список O(1 + n1)
• массив + сегменты O(1 + n2)
• хэш-таблица + сегменты O(1 + n1 + n2)

И где тут принципиальная разница?

Буду перебирать список и читать поля. Конечно, это может оказаться медленнее массива, а может и не оказаться.

«может оказаться», лол.

Думаю, что чем больше объём информации о каждой машине, тем менее значима будет укладка какой-либо информации о машинах именно в вектор.

Не думай, это не твоё.

Производители процессоров и компиляторов отлично осведомлены о проблемах больших задержек и активно ищут методы преодоления. Надо просто не вставлять им палки в колёса. Дай им нормальный предсказуемый паттерн перебора и не создавай ненужных зависимостей и префетчи всё сделают.

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

Не исчезнет. aist это замерил. Итерирование по buffer[arr[i]] проходит в 4 раза быстрее чем по next += buffer[next]

Ты неуч, не знаешь ни черта. Марш учить матчасть.

Слушаю и повинуюсь. Ссылки будут?

Эйлер (04.04.1707 - 18.09.1783) писал на латыни https://math.ru/history/people/Euler (там внизу даже названия сборников можно посмотреть)

А вот Абель (5 August 1802 – 6 April 1829) хотя бы частично на французском https://abelprize.no/page/handwritten-manuscripts-niels-henrik-abel (и может еще на немецком?)

Впрочем, по мелкоте и бредовости геополитеческого анализа звание «неуч» явно просится к den73.

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

Слышь, умник, я окончил мехмат МГУ > 20 лет назад и я однозначно знаю, что такое O большое.

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

Ну вот пора бы и проверить, остались ли у тебя хоть какие-то знания.

Вот тебе пара простых задач.

1. Доказать что 2х2=4 не на яблоках, а как математик.

2. Пересказать доказательство словами. Тут чуть интереснее:

Далее я привожу широко известное доказательство неравенство Коши-Буняковского.

Твоя задача: ты это доказательство пересказываешь СЛОВАМИ, без единой формулы, но так, чтобы с твоих слов оно однозначно и без раздумий восстанавливалось грамотным студентом. Переформулировки теоремы а-ля «ну это неравенство треугольника» не подходят — тебе нужно словами пересказать именно доказательство. Словами тебе надо пересказать СУТЬ доказательства, а не «открывающая скобка, буква а, запятая, ...».

Задача ясна?

Рассмотрим вектор a+λb, где λ∈R. Найдем скалярное произведение этого вектора на себя. Из свойств скалярного произведения следует, что

(a+λb,a+λb) ≥ 0

Раскроем скобки

(a,a) + λ(a,b) + λ(b,a) + λ²(b,b) ≥ 0

То есть

λ²(b,b) + 2λ(a,b) + (a,a) ≥ 0

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

4(a,b)² - 4(a,a)(b,b) ≤ 0

То есть (a,b)² ≤ (a,a)(b,b) = |a|²|b|²

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