Здраствуйте!

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

Мне тут как-то говорили, что новая priority_queue неплоха, но мне не нужны приоритеты, надо извлекать в том порядке, как положили

спасибо за то что поинтересовались нашей вакансией
всего хорошего!

	Скрытый текст
	вам отказали на этапе первычного скринига до собеседования вы даже не дошли

M>Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?
M>Мне тут как-то говорили, что новая priority_queue неплоха, но мне не нужны приоритеты, надо извлекать в том порядке, как положили
1. Есть стандартная очередь.
2. Проще всего использовать список.
Если очередь не очень интенсивно нагружается, то проблем никаких.

Здравствуйте, Marty, Вы писали:

M> Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?
Ты уже сделал перф-тесты и реально увидел, что у тебя deque является узким местом? Иначе — фигнёй страдаешь. Что значит "оптимальнее"? По памяти? По пропускной способности? По latency? По jitter?

С т.з. алгоритмической сложности — кольцевой буфер с фиксированным размером оптимальнее. Правда размер фиксированный... подойдёт ли тебе, хз. В стандарте нет прямо уж готового, но легко сделать на vector + пара индексов.
Для совсем low latency нужно смотреть в сторону disruptor.

Здравствуйте, LaptevVV, Вы писали:

LVV>1. Есть стандартная очередь.
queue реализован поверх deque

LVV>2. Проще всего использовать список.
проще, но не оптимальнее

Как уже отметили, кольцевой буфер для очереди — самое лучшее. Можно сделать его расщиряющимся (не обязательно фиксированного размера). deque имеет недостаток, что он "плавает" по памяти. При добавлении элементов выделяет новый фрейм, при удалении очищает старый. Для LIFO deque идеален.

Здравствуйте, sergii.p, Вы писали:

SP>Как уже отметили, кольцевой буфер для очереди — самое лучшее.

Ну, тут тоже есть кое-какие вопросы — например, о времени жизни объектов, извлекаемых из очереди. Тут традиционно быстродейиствие выходит против универсальности. Можно реализовать так, а можно эдак.

LVV>>1. Есть стандартная очередь.
SP>queue реализован поверх deque
А то я не знаю...
LVV>>2. Проще всего использовать список.
SP>проще, но не оптимальнее
Оптимальность бывает разная.
Есть оптимальность программы, а есть оптимальность программиста.
Если программа не нуждается в вылизывании шероховатостей, то программисту проще и быстрее (сиречь оптимальнее) просто использовать список.
SP>Как уже отметили, кольцевой буфер для очереди — самое лучшее. Можно сделать его расщиряющимся (не обязательно фиксированного размера). deque имеет недостаток, что он "плавает" по памяти. При добавлении элементов выделяет новый фрейм, при удалении очищает старый. Для LIFO deque идеален.
Смотря как он реализован.
А то я нарвался на реализацию от микрософта лет 10 назад, которая была в 5 раз медленнее реализации в gcc

Здравствуйте, LaptevVV, Вы писали:

LVV>1. Есть стандартная очередь.

Это же какая? std::queue? Это просто адаптер, у которого база по дефолту дека


LVV>2. Проще всего использовать список.

std::list? Что, правда, что ли?


LVV>Если очередь не очень интенсивно нагружается, то проблем никаких.

А если нагружается?

ЗЫ блин, профессор, ваш ответ был максимально бесполезен, и даже вреден

Здравствуйте, rg45, Вы писали:

SP>>Как уже отметили, кольцевой буфер для очереди — самое лучшее.

R>Ну, тут тоже есть кое-какие вопросы — например, о времени жизни объектов, извлекаемых из очереди. Тут традиционно быстродейиствие выходит против универсальности. Можно реализовать так, а можно эдак.

А можно раскрыть мысль? Какие проблемы с объектами в очереди? И как оно влияет на тип очереди, который лучше использовать?

M>ЗЫ блин, профессор, ваш ответ был максимально бесполезен, и даже вреден
При твоих исходных — получил именно то, что спросил.
Написал бы сразу про нагрузку — про кольцевой буфер получил бы ответ
А так твой вопрос сильно похож на вопрос неопытного джуна...

Здравствуйте, LaptevVV, Вы писали:

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

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

Здравствуйте, ·, Вы писали:

M>> Очередь стандартная, FIFO, в хвост кладём, из гривы извлекаем. Обычно deque использую, но чот решил у народу поинтересоваться, может есть что-то пооптимальнее сейчас?
·>Ты уже сделал перф-тесты и реально увидел, что у тебя deque является узким местом?

Нет конечно, ничего я не делал, я ещё ни строчки кода не написал


·>Иначе — фигнёй страдаешь.

Так точно!


·>Что значит "оптимальнее"? По памяти? По пропускной способности? По latency? По jitter?

Оптимальнее в совокупности

Здравствуйте, LaptevVV, Вы писали:

M>>ЗЫ блин, профессор, ваш ответ был максимально бесполезен, и даже вреден
LVV>При твоих исходных — получил именно то, что спросил.

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


LVV>Написал бы сразу про нагрузку — про кольцевой буфер получил бы ответ

А нагрузка всегда подразумевается, не?


LVV>А так твой вопрос сильно похож на вопрос неопытного джуна...

Не важно, какой вопрос, важно, какой ответ. Твой ответ похож на ответ неопытного джуна, вот это и плохо

Здравствуйте, Marty, Вы писали:

M>А можно раскрыть мысль? Какие проблемы с объектами в очереди? И как оно влияет на тип очереди, который лучше использовать?

Ну допустим, у нас очередь объектов с нетривиальным конструированием и разрушением. Что происходит когда мы извлекаем объект такого типа из очереди? Просто передвинуть индекс не вариант, наверное, нужно же еще и корректно завершить время жизни объекта, так ведь? А потом, когда до этого элемента снова по кругу дойдет очередь, создать на его месте новый объект. Наверное, самое простое, что можно придумать — это оборачивать все элементы очереди в std::optional — чтоб не глотать пыль с буферами и с placement new/delete. Такой вариант будет универсальным как для простых, так и для сложных типов. Но как такая реализация повлияет на производительность очередей простых типов? Можно вместо std::optional использовать шаблонную обертку со специализациями, которая для сложных типов будет использовать std::optional, а для простых не будет делать ничего (вырожденная пустышка). Но ведь это же нужно еще делать, это не в одну строчку решение.

LVV>>Написал бы сразу про нагрузку — про кольцевой буфер получил бы ответ
M>А нагрузка всегда подразумевается, не?
Нет. Ситуации бывают самые разные.
LVV>>А так твой вопрос сильно похож на вопрос неопытного джуна...
M>Не важно, какой вопрос, важно, какой ответ. Твой ответ похож на ответ неопытного джуна, вот это и плохо
Я с тебя фигею! Неважно, какой вопрос — А-БАЛ-ДЕТЬ!

Здравствуйте, Marty, Вы писали:

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

https://en.cppreference.com/w/cpp/container/queue

Здравствуйте, Marty, Вы писали:

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

Размер элемента, цена операций перемещения, характерный размер очереди, требования к многопоточности, требования к производительности — это всё, конечно же, никакого значения не имеет?

Если есть гарантии на максимальный размер очереди (или такие гарантии можно волюнтаристски ввести), то boost::circular_buffer, либо самому портировать / скопипастить / наколхозить поверх массива/вектора.
Он несложный, хотя и требует тщательности.

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

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

M>Мне тут как-то говорили, что новая priority_queue неплоха, но мне не нужны приоритеты, надо извлекать в том порядке, как положили

Что значит "неплоха"? Во-первых, это не контейнер, а обёртка (и обычно — над вектором). Во-вторых, она, действительно, делает совсем другое.
Как вообще пришло в голову её вспомнить? Просто потому что ..._queue?

К>Как вообще пришло в голову её вспомнить? Просто потому что ..._queue?

каждый новичек после 20 лет программирования на С++ хочет выйти за границы своего говнокодинга и притянуть что то эдакое в свое поделие

Здравствуйте, rg45, Вы писали:

R>Ну допустим, у нас очередь объектов с нетривиальным конструированием и разрушением. Что происходит когда мы извлекаем объект такого типа из очереди? Просто передвинуть индекс не вариант, наверное, нужно же еще и корректно завершить время жизни объекта, так ведь? А потом, когда до этого элемента снова по кругу дойдет очередь, создать на его месте новый объект. Наверное, самое простое, что можно придумать — это оборачивать все элементы очереди в std::optional — чтоб не глотать пыль с буферами и с placement new/delete.

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

R>Такой вариант будет универсальным как для простых, так и для сложных типов. Но как такая реализация повлияет на производительность очередей простых типов? Можно вместо std::optional использовать шаблонную обертку со специализациями, которая для сложных типов будет использовать std::optional, а для простых не будет делать ничего (вырожденная пустышка). Но ведь это же нужно еще делать, это не в одну строчку решение.

В совсем немножко строчек. Например, так.

template<class T> struct mandatory {
  static_assert(std::is_trivial_v<T>);
  T t_;

  // минимальный апи, общий с std::optional

  auto& constexpr operator*() noexcept { return t_; }
  auto& constexpr operator*() const noexcept { return t_; }

  void reset() noexcept {}
  void reset(auto&& t) { t_ = std::forward<decltype(t)>(t); }
};

template<class T> using buffer_item_t = std::conditional_t<std::is_trivial_v<T>, mandatory<T>, std::optional<T>>;

https://old.reddit.com/r/cpp/comments/18x1mty/can_we_claim_that_stddeque_is_the_most_underrated/

Здравствуйте, Кодт, Вы писали:

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

К>Размер элемента, цена операций перемещения, характерный размер очереди, требования к многопоточности, требования к производительности — это всё, конечно же, никакого значения не имеет?

Размер элемента — не мерял, но там определенно что-то хранится .

Суть в том, что мне надо разобрать JSON в другие иерархиеческие объекты. Использую nlohman json. Тупой подход в лоб — это использовать рекурсию, мне он не очень нравится — если мне подсунут жирный JSON, то у меня может не хватить стека. Для этого я решил сделать всё через очередь — если встречаю обычное поле bool/int/float/string — то разбираю на месте, если object/array, то создаю целевой object/array, и кладу эту пару в очередь для дальнейшего разбора, и в цикле выбираю оттуда и делаю разбор содержимого. Тут если жирный JSON, то у меня конечно может не хватит памяти для создания целевого объекта (или даже не хватит памяти для разбора текста в nlohman::json ноды), но эта ситуация поддаётся контролю, и я могу вернуть ошибку, или кинуть исключение, которое выше поймаю, либо исключение будет кинуто при создании целевого объекта, либо при помещении пары в очередь.


К>Если есть гарантии на максимальный размер очереди (или такие гарантии можно волюнтаристски ввести), то boost::circular_buffer, либо самому портировать / скопипастить / наколхозить поверх массива/вектора.
К>Он несложный, хотя и требует тщательности.

Гарантий никаких нет


К>Если очередь не является узким местом (профилирование наше всё! флеймграф умеешь строить?) — то std::queue и не морочить себе голову.

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


К>Чем более нестандартные вещи применяются, тем труднее поддерживать программу.

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


M>>Мне тут как-то говорили, что новая priority_queue неплоха, но мне не нужны приоритеты, надо извлекать в том порядке, как положили

К>Что значит "неплоха"? Во-первых, это не контейнер, а обёртка (и обычно — над вектором). Во-вторых, она, действительно, делает совсем другое.
К>Как вообще пришло в голову её вспомнить? Просто потому что ..._queue?

Ага

Здравствуйте, Marty, Вы писали:

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

M>·>Иначе — фигнёй страдаешь.
M>Так точно!
Ну тогда std::multimap используй для очереди. Не знаю как, не знаю зачем, но фигня будет знатная.

M>·>Что значит "оптимальнее"? По памяти? По пропускной способности? По latency? По jitter?
M>Оптимальнее в совокупности
Такого не бывает в природе.

Здравствуйте, ·, Вы писали:

·>Потом перф-тесты, поиск узких мест, разные варианты оптимизации и снова замеры перформанса, замеряя эффекты применённых оптимизаций.

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

Здравствуйте, rg45, Вы писали:

R>Ну допустим, у нас очередь объектов с нетривиальным конструированием и разрушением. Что происходит когда мы извлекаем объект такого типа из очереди? Просто передвинуть индекс не вариант, наверное, нужно же еще и корректно завершить время жизни объекта, так ведь? А потом, когда до этого элемента снова по кругу дойдет очередь, создать на его месте новый объект.

проблема не очень понятна. Например перед std::vector аналогичная задача стоит. Но она удовлетворительно решается внутри. При удалении элемента с хвоста индекс не просто сдвигается, а вызывается ещё деструктор. Тоже самое при повторном добавлении. Индекс свдинули, по памяти вызвали placement new.

Здравствуйте, sergii.p, Вы писали:

SP>При удалении элемента с хвоста индекс не просто сдвигается, а вызывается ещё деструктор.

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

P.S. Все сказанное мной в этой ветке актуально только в том случае, если я правильно истолковал исходное предложение

Автор: ·
Дата: 02.01 13:24

"vector + пара индексов". На самом деле, высказыание не очень детализировано и можно понять двояко. Принципиальный момент: вектор ЧЕГО предлагается использовать.

Здравствуйте, reversecode, Вы писали:

R>спасибо за то что поинтересовались нашей вакансией
R>всего хорошего!

ох, попадись ты мне на собеседовании...

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

а вообще это типичные ответы HR
я то причем

Откуда Китай Hong Kong

точно не попадусь

Здравствуйте, Marty, Вы писали:

M>Суть в том, что мне надо разобрать JSON в другие иерархиеческие объекты. Использую nlohman json. Тупой подход в лоб — это использовать рекурсию, мне он не очень нравится — если мне подсунут жирный JSON, то у меня может не хватить стека. Для этого я решил сделать всё через очередь — если встречаю обычное поле bool/int/float/string — то разбираю на месте, если object/array, то создаю целевой object/array, и кладу эту пару в очередь для дальнейшего разбора, и в цикле выбираю оттуда и делаю разбор содержимого. Тут если жирный JSON, то у меня конечно может не хватит памяти для создания целевого объекта (или даже не хватит памяти для разбора текста в nlohman::json ноды), но эта ситуация поддаётся контролю, и я могу вернуть ошибку, или кинуть исключение, которое выше поймаю, либо исключение будет кинуто при создании целевого объекта, либо при помещении пары в очередь.

Искусство задавать правильные вопросы. (И искусство задавать правильные встречные вопросы).

Но я тогда задам второй встречный вопрос.
Почему очередь, если программно тут нужен стек?
Ведь наивный алгоритм — на стеке вызовов. Тогда рефакторинг состоит в замене стека вызовов на стек данных. Разве нет?
Или там "автомат калашникова — устройство, преобразующее магазин в очередь"?

Кстати, парсер — дом или сакс? Нлохман умеет в оба.

Здравствуйте, Кодт, Вы писали:

К>Искусство задавать правильные вопросы. (И искусство задавать правильные встречные вопросы).

Оба два искусства, мало кто владеет хотя бы одним, и лишь немногие владеют обоими


К>Но я тогда задам второй встречный вопрос.
К>Почему очередь, если программно тут нужен стек?

Я не могу знать, какой по жирности JSON мне подсунут на вход. Могут подсунуть такой JSON, на котором вылетит любой стек, даже если я задам кастомный размер (под виндой вместо дефолтных 100Мб — гиг, например).
Преобразовав стек в очередь я имею больший контроль над тем, что происходит. Если на раслабоне, то вылечу по bad_alloc, но могу задавать и свои ограничения.

Плюс, я конвертирую JSON в squirrel объекты (таблицы и массивы), там на VM есть свои ограничения (в тч что я могу задать при старте), она может упасть раньше, но я это поймаю плюсовыми средствами.

Если говорить о том, что использовать — стек или очередь в плюсиках — ну, тут я просто иду по накатанной, задачек на очередь прорешано больше, чем на стек Хотя, после намёков, стек так и просится, но уже лень


К>Ведь наивный алгоритм — на стеке вызовов. Тогда рефакторинг состоит в замене стека вызовов на стек данных. Разве нет?
К>Или там "автомат калашникова — устройство, преобразующее магазин в очередь"?

Типа того

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

К>Кстати, парсер — дом или сакс? Нлохман умеет в оба.

Дом

Со стеком вроде всё понятно — std::stack на базе std::vector в принципе вполне нормас и сто лет назад и сейчас.

А таки, если принять, что для данной задачи нужна именно очередь — какую очередь стоит использовать сейчас?