в🧇
Просто дырявый вектор — вставка
O(n) на поиск NoneНе, фигню сказал, с просто вектором будет простая вставка
Some(_), никакого поискаSize: a a a
2020 September 29
П
А в расте не завезли в стд deque?
EG
А в расте не завезли в стд deque?
Есть LinkedList и ещё VecDeque, но оба не то
в🧇
А в расте не завезли в стд deque?
У меня сейчас
deque, но с удалением из середины как-то тупо его использоватьDF
Тебе можно просто два массива
DF
Как в о(1) шедулере было
DF
В луниксе
П
Я просто вот что вспоминаю
П
Это конечно для стд крестов, но один хрен сложность алгоритмов не меняется
EG
Эта таблица не учитывает, что стандартная реализация linked list в Rust будет жрать по одной аллокации на создание ноды
EG
А аллокация — это дорого
П
Эта таблица не учитывает, что стандартная реализация linked list в Rust будет жрать по одной аллокации на создание ноды
Это да. Но сложность всё равно остается О(1) :D
EG
Это да. Но сложность всё равно остается О(1) :D
Это не факт, кстати. Никто тебе не гарантирует, что сложность аллокации это O(1)
EG
Время выполнения аллокации может зависеть от занятости памяти, в каком случае объём твоих данных косвенно влияет на время аллокации
П
А тут ты прав, не подумал.
в🧇
Btw, мне вообще и
Vec+drain_filter может подойти, если с Cell заморочиться.EG
Кроме того, время аллокации уж точно зависит от размера, который ты запрашиваешь
DF
Каким образом?
EG
Чем больше размер, тем сложнее найти участок памяти такого размера (или собрать его из нескольких участков физической памяти)
DF
Оно ж на slab-ах