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

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

Один момент, который еще не учитывают, это то, что хэш-функция – это O(|K|), что при больших размерах ключа влетает в копеечку.

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

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

если уж и укорачивать ключ, то брать не префикс, а некую выборку из всего ключа типа key[(i * big_prime)% lenght(key)] - то есть выборку с псевдорандомным индексом. типа из 64 символьной строки выбрать 16 символов с псевдорандомным индексом. подобрать естессно длину выборки, чтобы не было сильных коллизий

Модуль числа - дорогая операция даже на распальцованных OoOE процессорах. Это же деление. Умножение тоже не везде дешёвое. Такая выборка тоже в копеечку влетит.

Тут вот https://en.wikipedia.org/wiki/Dynamic_perfect_hashing якобы смогли сделать О(1) даже в худшем случае и даже при заранее неизвестных данных.

Правда search в хэше неполноценный в том смысле, что выдает 1 бит (есть ключ / нет ключа), а я неявно имел в виду полноценный ответ «равный мне или следующий за мной ключ это ...» что будет |K| бит.

Причем их О(1) это не знаю что от длины ключа.

Модуль числа - дорогая операция даже на распальцованных OoOE процессорах. Это же деление. Умножение тоже не везде дешёвое. Такая выборка тоже в копеечку влетит.

Это все можно статически посчитать.

Такая выборка тоже в копеечку влетит.

табличкой заменяется, как во многих хеш функциях.

Ладно, уговорили)

Вот в примере с таймерами подумал, и сделал через deque.

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

Тогда как timer-list простой как две копейки и надежный как танк.

Зачем менять простое и надежное решение на что-то непонятное не имея никаких замеров на руках мне не понятно.

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

б дерево - все равно дерево! это списочная структура, а не массив.

Ага, а вектор - это тоже такой вырожденный список, в котором всего одна нода и все данные хранятся в ней.

Бро, я привёл тебе пример б-дерева не для того чтоб выдать его за особый вид вектора, нет. Я продемонстрировал, что теоретически быстрое O(ln(N)) бинарного дерева оказалось в глубокой жопе из-за связей и поэтому умные люди решили, что лучше вот просто брать и использовать массивы и поиск в них. Чтоб во время поиска элемента проходить по как можно меньшему числу связей.

и какое там дерево - совершенно неважно в оспаривании вздорного утверждения что списки не нужны.

Бро, я уже доказал что списки не нужны. Вы просто никак не можете принять реальность.

графы нужны? значит нужны списки.

Графы на указателях делают только полные дауны.

приоритетные очереди нужны? значит нужны списки.

Их вообще-то на хипе делают. А знаешь что такое хип? Ну, в честь которого хипсорт назван, алгоритм, который сортирует содержимое массива на месте создавая виртуальное дерево внутри массива? Правильно, хип - это массив. В котором просто имплицитно подразумевается дерево, считается, что у элемента с индексом i N потомков с индексами iN+1, iN+2,…i*N+N

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

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

Вот тебе ссылочка для самообразования: https://www.youtube.com/watch?v=M2fKMP47slQ

Тебе будет любопытно узнать, что при размере ассоциативного массива int->int до 40 примерно обычный несортированный массив с линейным поиском ищет быстрее любых других реализаций, хоть бинарного дерева (std::map), хоть хэш-таблицы на списках (std::unordered_map), хоть сортированного массива с двоичным поиском (boost::flatmap).

Примерно начиная с 400 бинарное дерево уходит в задницу, вместе с сортированным массивом, однако массив выходит потом на более пологую кривую начиная с 1500 примерно, а на 150 тысячах элементов становится эффективнее std::unordered_map.

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

я же не утверждаю, что массивы не нужны. массивы нужны там, где существенен доступ по рандомному индексу

лицоладонь.jpg

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

кстати реализуй лисп на массивах.

Зачем мне реализовывать мёртвый язык, да ещё и заточенный под списки?

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

А в чём проблемы? Есть сомнения, что deque с ролью очереди справится лучше списков? Или что зная сквозной индекс первого элемента в очереди, при условии монотонного их возрастания, легко узнать индекс в очереди по сквозному?

Тогда как timer-list простой как две копейки и надежный как танк.

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

Остаток от деления нацело. Выполняется долго даже на Х86.

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

Вставка в таблицу – амортизированное O(1), как и в конец массива.

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

Есть сомнения, что deque с ролью очереди справится лучше списков?

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

Я даже код приводил:

if (timers_deque.size() > 0)
{
    int64_t index = timer_id - timers_deque[0].timer_id;
    if (index >= 0)
        deque[index].canceled = true;
}

Отменяет таймер с айди timer_id

Т.е. если я создал 1000 таймеров, а затем отменил 998 штук оставив только первый и последний, то у меня в памяти все равно останется дек на 1000 элементов, в котором действительными будут лишь первый и последний элементы?

в котором действительными будут лишь первый и последний элементы?

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

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

Берем ordered_map (который в плюсах назвали map) на основе B-tree. В качестве ключа используем время таймера (с миллисекундами, никаких целых timer_id). Вставка в середину быстрая, удаление сработавших таймеров с конца еще быстрее (если у тебя Тип 1), удаление сработавших таймеров по порядку из середины тоже быстрое (если у тебя Тип 2).

Если ты таймеры двигаешь по времени, то будет некоторый оверхед, но все равно поиск-удаление-поиск-вставка в B-tree быстрые. Не думаю что от прошивки таймеров насквозь указателями этот оверхед уменьшится. Скорее наоборот, увеличится.

UPDATE: можно B+, можно В-

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

Зачем мне реализовывать мёртвый язык, да ещё и заточенный под списки?

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

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

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

ты обыгрываешь то свойство массива, что это единый кусок памяти в который можно и положить ВСЕ что угодно, при одном условии - оно должно состоять из элементов ОДНОГО ТИПА. а это совершенно частный случай общих ссылочных структур.

ты причепился к таймерам, явно ни разу их не программируя на плюсах!!!, потому что сразу увидел бы, что таймер это класс!!!, и его использование в ООП предполагает НАСЛЕДОВАНИЕ!!! и возможно изменение размера этого класса. и нельзя потому сделать «очередь из таймеров» на массиве, еклмн! пользоательские таймеры имеют неспецифмцированный размер, и потому твой код потому полностью мусорный. максимум ты можешь выжать из массива тут - массив указателей на базовый таймер… после чего твоя логика неиспользования указателей, ибо медленно, кеш и все такое - летит к черту. поскольку ты сделал косорукий список, и у тебя вместо перехода по указателю в поле next (как у нормального списка), стал переход по указателю в поле массива array[i+1]…ты создал лютейшую жопу, которая по всем параметрам хуже просто списка, даже по скорости итерации и кеш хитам(потому что у тебя обьекты отдельно, указатели отдельно).

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

Берем ordered_map (который в плюсах назвали map) на основе B-tree.

Если у вас относительно небольшое количество таймеров, то реализация на основе binary heap будет эффективнее (ценой хранения непрерывного буфера для этого самого binary heap). Если таймеров много, то эффективнее будет timer_wheel, правда ценой гранулярности таймера (правда, когда таймеров реально много, то точность все равно будет страдать).

В качестве ключа используем время таймера (с миллисекундами, никаких целых timer_id).

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

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

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

Это да, я прозевал, нужен ordered_multimap, но внутри там все равно то же дерево.

Если таймеров много, то эффективнее будет timer_wheel, правда ценой гранулярности таймера

Если мы подсунем нашему контейнеру (ordered_multimap) другой оператор сравнения таймеров, который будет выдавать равенство таймеров для приблизительно равных времен срабатывания, то получим timer_wheel, не?

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

А еще абстрактный timer_id крайне полезен для периодических таймеров.

Это совсем другие таймеры. Их можно делать в другой структуре данных.

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

Можно все таймеры (и периодические, и одноразовые) сложить в unorderered_multimap<refcounted<timer>>, который я называю контейнером. Вместо timer_id используем refcounted<timer>. Сработавший одноразовый таймер сразу удаляем из контейнера. Сработавший периодический таймер удаляем, меняем время следующей отработки на новое, вставляем заново. Таймер, который надо канселнуть, тоже удаляем из контейнера.

Я ничего не забыл что надо делать?

Тут важный момент, что таймеры сортируются по времени ближайшей отработки (которую можно и округлить в операторе сравнения), но все же различаются по реальному адресу timer. Нормально сделанная unorderered_multimap должна позволять сравнивать элементы с возможностью получения дубликатов по равенству, но удалять элементы точно — т.е. именно тот из дубликатов, который был запрошен (т.е. либо по адресу timer, либо по адресу refcounted<timer>).

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

unorderered_multimap<refcounted<timer>>

Я не понял как вы в unordered_multimap будете упорядочивать элементы по времени срабатывания. Ну да и не важно. Если вам потребуется делать таймеры самостоятельно, то разберетесь.

Расскажу лишь кратко о своем опыте. Когда-то давным-давно я сделал таймеры на базе C++ного multimap-а (или multiset-а, уже не помню). Потом переделал на базе heap-а, т.к. heap в моих условиях оказался эффективнее. Потом вообще перешел на использование таймеров из ACE. Потом, когда от ACE нужно было отказываться, посмотрел что там к чему, почитал материалы, на которые были ссылки в исходниках ACE и остановился на трех механизмах: timer_wheel, timer_heap и timer_list. Мне этого хватает. Ссылка выше была, кому интересно, можно посмотреть.

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

Я не понял как вы в unordered_multimap будете упорядочивать элементы по времени срабатывания.

Это полный ляп. Конечно, там везде ordered_multimap.

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

А мне понравилось подумать над задачей.

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

Если увижу конкретную реализацию ordered_multimap, буду проверять ее на это.

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

Берем ordered_map (который в плюсах назвали map) на основе B-tree. В качестве ключа используем время таймера (с миллисекундами, никаких целых timer_id). Вставка в середину быстрая, удаление сработавших таймеров с конца еще быстрее (если у тебя Тип 1), удаление сработавших таймеров по порядку из середины тоже быстрое (если у тебя Тип 2).

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

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

Ещё раз: зачем мне реализовывать мёртвый игрушечный язык? Тем более завязанный на списки.

У тебя странная логика, ты не решаешь задачи, ты предлагаешь эмулировать плохое решение хорошими средствами. Зачем?

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

Нормальной разработкой софта. В которой, естественно, никто про эти дурацкие списки даже не заикнётся.

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

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

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

Всё-таки вынужден тебе кое-что напомнить. Твою цитату:

заполни списки/массивы свои 10 тыс элементов(это время не мерить), и мерь время мильона вставок/удалений например первого элемента списка и массива. список брать std:list.

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

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

ты обыгрываешь то свойство массива, что это единый кусок памяти в который можно и положить ВСЕ что угодно, при одном условии - оно должно состоять из элементов ОДНОГО ТИПА. а это совершенно частный случай общих ссылочных структур.

Это совершенно надуманная проблема. В контейнерах почти всегда лежат объекты одного типа, даже в ссылочных, повёрнутых на ООП языках, типа той же java. Необходимость смешивать типы в контейнере - это скорее исключение. Но тоже решаемое. В расте подобные вещи можно сделать тем же tagged union, не нравится такой подход - ну сделай массив владеющих указателей. Или, лучше, массив кортежей ключ + владеющий указатель, чтоб число рандомных обращений к памяти снизить.

ты причепился к таймерам,

У тебя с головкой как, нормально? Мне предложили пример задачи, решаемой списком, я предложил решение на деке.

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

Вот ты тупой. Речь, вообще-то, о некотором объекте «очередь таймеров», который предоставляет открытое API в стиле «создать таймер и вернуть его идентификатор, вот функция для вызова по таймауту» и «отбой, таймер с идентификатором таким-то не должен сработать». Внутри очереди лежат айтемы внутреннего типа, так что нет никакого смысла городить тут виртуальность и наследование. Даже если этот айтем объявлен словом class.

Так что ты снова обосрался, поздравляю.

Кстати, ты так и не ответил на прямой вопрос. Вот тебе нужен стек. Лимит размера тебе неизвестен. Индексация не нужна. Пишешь на плюсах. Что будешь использовать, std::list или std::vector? Я всё-таки предпочёл увидеть твой ответ. Хочется посмотреть либо как ты окончательно сядешь в лужу, либо как резко сдашь назад, а я буду кидать тебе твои цитаты про свойства этих контейнеров и спрашивать, как же так :)

Это полный ляп. Конечно, там везде ordered_multimap.

Если бы эта идея работала, можно было бы и без мультимапа, типа в старших битах идентификатора хранить время срабатывания, а в младших - порядковый номер таймера, среди записанных на это время. При добавлении - map.lower_bound((target_time + 1)<<INDEX_BITS). Уменьшаем итератор, берём ключ (key), если старшие биты == target_time - new_timer_id = (target_time<<INDEX_BITS)|((key&INDEX_MASK) + 1;, иначе просто new_timer_id = (target_time<<INDEX_BITS). Плюсом данного решения были бы нормальные целочисленные идентификаторы, по которым можно было бы искать таймер для отмены.

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

Вот ты тупой. Речь, вообще-то, о некотором объекте «очередь таймеров», который предоставляет открытое API в стиле «создать таймер и вернуть его идентификатор, вот функция для вызова по таймауту» и «отбой, таймер с идентификатором таким-то не должен сработать». Внутри очереди лежат айтемы внутреннего типа, так что нет никакого смысла городить тут виртуальность и наследование. Даже если этот айтем объявлен словом class.

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

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

мне спорить надоело, книжки читай.

ты так и не предложил как на массивах в рамках с++ реализовать пользовательские таймеры с виртуальным методом. лисп оказался «зелен». о чем спорить тут вообще?

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

Я же с самого начала предлагал Б-деревья. Вот например https://github.com/Kronuz/cpp-btree

Similar to the STL std::map, std::set, std::multimap, and std::multiset templates, this library provides btree::map, btree::set, btree::multimap and btree::multiset.

Смотря на что делить, например, на 2^n.

тупой тут ты. такой дизайн для с++ неверен в принципе.

Давай кто угодно будет говорить о C++, но только не ты. Ты уже столько глупостей понаписал, что весь кредит доверия исчерпал раза на 3.

в такой парадигме ты тупо забудешь убить таймер.

Что такое «убить таймер»? Отменить?

в такой парадигме ты не можешь переопределить класс таймер в свой свой класс

Естественно. Никто не будет переопределять класс таймер, что за бред. Что ты в нём собрался переопределять вообще?

где нет наследования и где из массивов не вылезают, программируя микроконтроллеры. вот ты видимо в этом и погряз.

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

про лисп особенно смешно.

Да не смешно. Язык жил исключительно потому что в одном из лучших ВУЗов по тематике на нём учили студентов-первокурсников. Синдром утёнка. Недавно вроде и там отменили, так что лет через десять отправится туда же, где сейчас оберон или D. Ну и клоуны типа тебя с культом карго тоже вообразили чего-то этакого.

вся ветка про ненужность списка напоминает басню эзопа «лиса и виноград» где лиса уверяла

Блин, ты специально что ли? То ты рассказывал про то что такое списки и массивы, сейчас начал лису и виноград пересказывать… Это насколько надо иметь самомнение, чтоб думать, что и это только тебе ведомая тайна?

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

мне спорить надоело, книжки читай.

Оно и видно, ты плюсы только в книжках видел.

ты так и не предложил как на массивах в рамках с++ реализовать пользовательские таймеры с виртуальным методом

Зачем тебе, дураку, пользовательские таймеры с виртуальным методом? Ты C++ только в книжках из 80х видел что ли? Сейчас (ну, лет 10+ как) от этого уходят, поддержку замыканий народу подавай. Ты вот как замыкание в свой виртуальный метод запихаешь? Будешь под каждое место использования таймера отдельный класс-наследник городить, с захватом правильных полей?

Но я по прежнему жду твоей мощной аналитики по теме гораздо более простого вопроса: что брать в качестве стека, std::list или std::vector. Уже третий раз спрашиваю. Неужели до тебя дошло что ты полную дичь тут вещал и ты поэтому решил съехать?

Я же с самого начала предлагал Б-деревья. Вот например https://github.com/Kronuz/cpp-btree

The C++ B-tree containers are not without drawbacks, however. Unlike the standard STL containers, modifying a C++ B-tree container invalidates all outstanding iterators on that container.

Я вижу в этом сообщении жирный намёк на возможность ребалансировки.

Я вижу в этом сообщении жирный намёк на возможность ребалансировки.

Конечно. А в расте как-то не так?

Для эффективного выполнения/завершения таймеров можно скопировать к себе пачку refcounted<timer> и затем удалить ее из Б-дерева. Можно ли это сделать за один шаг с помощью std::ranges::move я не знаю.

После этого дерево может перебалансироваться, ну и пусть. Б-деревья делают это очень быстро.

Само собой. Но там человек давал пример, где остаток от деления берется по размеру ключа. А это переменная величина. Понятное дело, что это всё можно аппроксимировать.

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

Но все это не столь интересно, как гарантированное О(1) у хешей. Припоминаю, я около 2000 года читал их доказательство, но как-то не пошло, и я бросил. У них там че-то сложно, или изложено как-то неудобоваримо было.

Скорее это просто слишком муторно – поддерживать интераторы при меняющемся дереве. Тут кстати, растовская система типов отлично подходит – дерево можно менять только если открытых итераторов нет.

Я вот смотрю на все это и думаю: они просто не умеют их готовить! Если идеи раста правильно приготовить, то получилось бы вкусно.

Растоманы не умеют готовить раст?

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

Они стараются.

Хренушки, язык уже фиксирован. Хотя в принципе возможность все исправить, по-моему, есть. Я подумаю.

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

Я пока одного не понимаю, почему он такой тормозной при компиляции.

Я так полагаю что под длиной ключа он понимал максимальную длину

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

то есть берем константу - максимум символов в хеше, ну там… 16.

если ключ длиной меньше или равен 16 - просто итерируем. если ключ длинней - делаем выборку 16 символов из него по псевдослучайному индексу, считая их хеш. если парит модуль - строим таблицу для 17, 18, 19,…..64 символов…тут вопрос где остановиться. если не хочется забивать память таблицами(хотя тут все компактно - это массивы по 16 байт - нам же надо 16 индлексов), для совсем длинных ключей считать опять через модуль… короче если б у меня была такая задача, я бы решил ее в лоб таким образом, и забыл.

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

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

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

Скорее это просто слишком муторно – поддерживать интераторы при меняющемся дереве.

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

Понятно что делается это через дополнительную косвенность. Но их реализацию надо пропатчить.

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

Инвалидировать итераторы – тоже лишняя работа при чтении (проверка на валидность при каждом обращении). Проще в рантайме проверять счетчик открытых итераторов, и отказываться обновлять дерево, если он >1.

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

Не читал, но осужаю! Я хотел бы вот так:

for( auto a: my_ordered_map )
{
  for( auto b: my_ordered_map )
  {
    my_ordered_map.insert(f(a,b));
    my_ordered_map.erase(h(a,b));
  }
}

И чтобы без лишнего оверхеда (примерно как обычно при вставке-удалении).

И вроде так можно сделать.

Почему идеи, а не идея? Разве их там больше одной? (слайсы не считаем)

Хотя бы borrow checker раз, traits два, оператор ? три.

Но borrow checker сводить к одной идее — это как-то совсем не соответствует действительности.