@Antoshkka Добрый вечер. Я пытался выяснить для себя какой-то реальный

Question

@Antoshkka Добрый вечер. Я пытался выяснить для себя какой-то реальный

пример использования кучи в проде, а именно, в каких случаях люди осознанно использовали именно этот АТД как лучший выбор, и один из инсайдеров Яндекса мне написал, что priority_queue встречается в коде Яндекс Такси 5 раз.
Антон, если есть возможность, пожалуйста, напишите пару кейсов, почему выбирали именно кучу? Именно, какие особенности решаемой задачи продиктовали такой выбор?
Надеюсь, просьба не обременительная.
PS Участникам сообщества, которые захотят предложить мне использовать Гугл - пожалуйста, не беспокойтесь. С академическими примерами использования кучи я знаком, я ищу примера использования в бизнес-приложении.

#c++ #embedded #programming #russian

0

29.06.2021

9 ответов

15 просмотров

Egor Pugin

Egor Suvorov
Про бизнес не скажу, но могу поделиться опытом с о...

какая стдлиба и компилятор?

0

29.06.2021

Egor Suvorov

Egor Pugin
какая стдлиба и компилятор?

Обычно gcc, stdlibc++

0

29.06.2021

Kelbon

Egor Suvorov
Про бизнес не скажу, но могу поделиться опытом с о...

в олимпиадах наверное лучше всё в хеш умещается)) задачи то обычно небольшие

0

29.06.2021

Egor Suvorov

Kelbon
в олимпиадах наверное лучше всё в хеш умещается)) ...

Там обычно 10^5 элементов pair<int, int>, это почти мегабайт. Так что в L3 влезть может, а вот в L1/L2 — уже нет.

0

29.06.2021

Kelbon

Egor Suvorov
Там обычно 10^5 элементов pair<int, int>, это почт...

прямо во всех задачах pair<int int> 10^5?)

0

29.06.2021

Egor Suvorov

Kelbon
прямо во всех задачах pair<int int> 10^5?)

priority_queue обычно возникает в районе алгоритма Дейкстры. Там 10^5 — стандартное ограничение для графов, для Дейкстры в куче обычно хранится расстояние до вершины и её номер — отсюда пара.

0

29.06.2021

Ignat Loskutov

Да хоть банальные таймеры доставать на каждой итерации main loop нужна приоритетная очередь

0

29.06.2021

Dmitry Sokolov

Ignat Loskutov
Да хоть банальные таймеры доставать на каждой итер...

Приоритетная очередь это ж не обязательно heap.

0

29.06.2021

Egor Suvorov · Accepted Answer

Egor Suvorov

Про бизнес не скажу, но могу поделиться опытом с олимпиад: priority_queue регулярно работает тупо в полтора-два раза быстрее set. Возможно, за счёт меньшего выделения памяти, возможно, за счёт более простой структуры, а может всё вместе.

0

29.06.2021

170 похожих чатов

@Antoshkka Добрый вечер. Я пытался выяснить для себя какой-то реальный

9 ответов

Похожие вопросы