Быстрая вставка

[Racheengel]

Ну смотрите, вы даете задачку реализовать баннерокрутилку. У вас есть несортированный набор рекламных объявлений с приоритетом. Вам надо показать топ-10 по высшему приоритету. Прикладная задача? Вполне.

Вполне прикладная. Только не на 40 минут.
1. Какую технологию используем для показа баннеров?
2. В каком формате хранятся объявления?
3. С помощью каких средств осуществляется доступ к объявлениям?
4. Показать за какой период времени? Все 10 сразу или по очереди? С какой задержкой?
5. Куда деплоить?
Ну и еще десяток попутных задач.
В общем, новичку на неделю работы (моя грубая оценка, т.к. я по вебу не спец).

PS. Ну и кстати я бы за полную сортировку голосовал.
Пускай все объявления всегда по приоритетам лежат отсортированными.
Так и искать проще, и вставлять, и удалять.

[Igors]

Ну а по теме, действительно, условие по сохранению "порядка" - оно новое. Поэтому и решение меняется.
Код лень писать, но я бы сначала сделал кэш по первичному ключу в виде <имя:<номер:позиция>>  ( QMap<QString, QMap<int, int> >)

Мудрость приходит со старостью, но старость чаще приходит одна

[Авварон]

Вполне прикладная. Только не на 40 минут.

Ну эти все вопросы вам допустим расскажут, все что вам надо это написать алгоритм.
Условно у вас есть с++ сервер который уже до вас написан и вам надо отдать по РЕСТу массив айдишников в жисоне. А точнее просто вектор интов, сериализация в жисон тоже уже написана - все что от кандидата требуется - это сделать это максимально быстро.
Массив не сортирован потому что так "исторически сложилось" (ну или скажем он сортирован по таймстемпу добавления баннера). Но это все детали не нужные в задаче.
Просто именно эта задачка выросла из прикладной - надо было сделать ровно это по тикету и делающий решил ее на собесах спрашивать потому что отлично ложиться на редкий но стандартный алгоритм.

[Igors]

Вполне прикладная. Только не на 40 минут.
1. Какую технологию ...

Кстати да. Дело совсем не в том знает ли человек std::partial_sort, а насколько хорошо он владеет используемыми технологиями. Ну или насколько быстро и охотно он их освоит (бессмертное "быстро учуся"). Столь общие/абстрактные задачки как эта бывают, но редко, макс 5%, остальное завязано на специфику

[Авварон]

Кстати да. Дело совсем не в том знает ли человек std::partial_sort, а насколько хорошо он владеет используемыми технологиями. Ну или насколько быстро и охотно он их освоит (бессмертное "быстро учуся"). Столь общие/абстрактные задачки как эта бывают, но редко, макс 5%, остальное завязано на специфику

Если человек, идущий на сеньора до сих пор не выучил алгоритмы stl, то может он их никогда не выучит=)

[Пантер]

Кстати да. Дело совсем не в том знает ли человек std::partial_sort, а насколько хорошо он владеет используемыми технологиями. Ну или насколько быстро и охотно он их освоит (бессмертное "быстро учуся"). Столь общие/абстрактные задачки как эта бывают, но редко, макс 5%, остальное завязано на специфику

Если человек, идущий на сеньора до сих пор не выучил алгоритмы stl, то может он их никогда не выучит=)

Ибо это нафиг не нужно Я сеньор-помидор и я не знаю алгоритмов stl. Знаю только про sort, юзал его когда-то.

[Igors]

Если человек, идущий на сеньора до сих пор не выучил алгоритмы stl, то может он их никогда не выучит=)

Ничего страшного. Действительно хороших алгоритмов там очень немного, в основном упорное навязывание ФП

[Авварон]

Ибо это нафиг не нужно Я сеньор-помидор и я не знаю алгоритмов stl. Знаю только про sort, юзал его когда-то.

Если ваша работа - перекладывать джисоны то, возможно, не стоит эти гордиться
Но если серьезно, то вон всякие set_intersection и unique весьма полезны. Как удалить дубликаты / из пути? Ну можно написать регэксп о который будет спотыкаться каждый читающий, а можно просто unique сделать - это будет в 100500 раз быстрее.

[Пантер]

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

[Racheengel]

"не барское это дело, синьйорам в stl-ях копаться"

Ну а если серьёзно, многие забивают на производительность, к сожалению. И дело тут даже не в регэкспах (хотя они write only как правило). Электрон и иже с ним развращают. Можно ж больше памяти запихнуть и проц побыстрей, и всё, типа.

PS. Имхо: алгоритмические штуки - это всё-таки middle-level. Синьйор как раз тем и отличается, что может делегировать подобные задачи нужным людям, а не заниматься микроменеджментом и копипастингом.

[Авварон]

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

Значит ты не работал с данными где миллионы строк. Банальное знание алгоритмов и О-нотации позволило мне в яндексе ускорить джобу с 12 часов до 3. Джоба молотила всего какие-то жалкие 30-40 терабайт данных.
Банерокрутилка - хороший пример, у тебя миллионы банеров, а надо только 10. 10^6*log(10^6) это сильно больше чем 10^6*log(10)

[Пантер]

ХЗ, я всего лишь в IoT работаю. Баннеров тут нет...

[Racheengel]

Банерокрутилка - хороший пример, у тебя миллионы банеров, а надо только 10. 10^6*log(10^6) это сильно больше чем 10^6*log(10)

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

[Авварон]

Ну вы же не будете сортировать гигабайтный файл по каждому возможному ключу? Потом такое решение экономит время разработки - вам не надо создавать один еще один файл, тестировать, аплоадить его на кластера... 3 строки кода или два дня работы?
Как я уже говорил - так могло исторически сложиться, может там вообще заммапленный в память файл на каком-нибудь богомерзком MMS и вам еще надо сериализацию написать для сортированной версии.

[RedDog]

Алгоритмами можно оптимизировать, ну процентов на 10% по производительности, самая главная оптимизация в бизнес логике идет, там можно в десятки тысяч раз оптимизировать.
Была задача сначала написана "в лоб" бегала по графу 30-40 млн раз, после оптимизации (предварительной фильтрации) по этому же графу стала бегать 3-5 тыс. раз. Но для этого надо было сначала распарсить бизнес-логику.