Email or username:

Password:

Forgot your password?
Top-level
Мя :sparkles_lesbian:

@blue а нафига для очереди двусвязный список, если она отлично покрывается кольцевым буфером?

doc.rust-lang.org/std/collecti

10 comments
Blue

@mo нафига для очереди кольцевой буфер если она прекрасно обрабатывается списком?

Мя :sparkles_lesbian:

@blue как минимум тем, что кольцевой буфер не раскидан по памяти как невезучий сапёр, и лучше влезает в кеш процессора

Blue

@mo какая разница как он раскидан?) Обрабатываются элементы друг за другом, пускай где хотят там и хранятся, какой получится такой длины не резервируя в памяти непрерывный блок

Мя :sparkles_lesbian:

@blue если данные лежат рядом, лучше утилизируется кеш

Мя :sparkles_lesbian:

@blue вообще, дока раста по выбору подходящей коллекции говорит следующее

Используйте двусвязный список если..
— вам нужно обрабатывать списки неизвестной длины и амортизация ну прям совсем не вариант
— если надо эффективно резать и склеивать списки
— Если вы АБСОЛЮТНО уверены, что вам НУ НИКАК не обойтись без двусвязного списка
В большинстве случаев Vec/VecDeque будет оптимальнее

Blue

@mo я хз чего такого волшебного в расте, но с точки зрения структур данных ничего для перебора данных друг за другом эффективнее листов нет. Если данные произвольных размеров вектор вообще не вариант, он будет постоянно перерезервироваться в памяти что бы лежать подряд, это копирования и фрагментация. Кольцевой буфер, ну я хз, очередь может быть и 5 событий а может быть и 5 миллионов, держать в памяти блок в несколько десятков мегабайт который 99% времени будет пустым просто потому что иначе я просру пару событий на бёрсте, объемы которого не могу предсказать но "640 должно хватить всем" и все ради кеша процессора - звучит чрезвычайно идиотской затеей. Что за зверь такой векдек я хз, но в сях дек это что то типа связного списка векторов, как бы ни вашим не нашим, что бы и в центре модифицировать можно было не так обидно и что бы по индексу можно было брать.

@mo я хз чего такого волшебного в расте, но с точки зрения структур данных ничего для перебора данных друг за другом эффективнее листов нет. Если данные произвольных размеров вектор вообще не вариант, он будет постоянно перерезервироваться в памяти что бы лежать подряд, это копирования и фрагментация. Кольцевой буфер, ну я хз, очередь может быть и 5 событий а может быть и 5 миллионов, держать в памяти блок в несколько десятков мегабайт который 99% времени будет пустым просто потому что иначе я просру...

Мя :sparkles_lesbian:

@blue VecDeque это собственно кольцевой буффер и есть. Реаллокации не настолько тормознутые, и вот не при сравнении со связными списками говорить о фрагментации.

Мя :sparkles_lesbian:

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

Двусвязный список проиграл, более чем в три раза :blobcatgooglytrash:

Мя :sparkles_lesbian: replied to Мя

@blue а, ещё в процессе тестирования он, в отличие от вектора вылетел в своп

Мя :sparkles_lesbian:

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

Go Up