Ужасы нашего городка
Feb. 13th, 2021 12:23 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
elglinМне несколько раз с интервалом от месяцев до лет снился сон на одну и ту же тему, что я второй раз учусь у себя на факе. При этом я осознаю, что учусь второй раз, и, вроде как, непонятно, зачем, но вот учусь. Ну и мысли (все во сне), что как же я сессию сдавать буду, у меня же работа, отпрашиваться надо будет и все такое.
Это я, собственно, к чему. Есть некая девочка, назовем ее Х. (нет, не Хуанита). Девочка учится на программистском факультете. Девочке я до того пытался нести в мозг матан и алгебру, их она сдала.
А вот теперь она попросила помочь с пересдачей по погромированию. Я сначала машинально (девочка позвонила аккурат между двумя нервными совещаниями) попросил прислать все задачи и вопросы, и только потом отметил, что на дворе не то, что февраль, а середина его, и сессия закончилась не только сама, но и вместе с пересдачами. Сталбыть, девочка не то, что с хвостом, а в одном шаге от пресловутого компота.
Ну ладно, слава яйцам, у нее не Паскаль, который я бы без методички не вспомнил (хотя у меня на нем написан один курсач - не мой, и одна лаба - не моя), а старый добрый Це. Ну на Це мы могем, и у нас, естественно, есть муха гэцеце (прольем скупую слезу над безвременно почившим ваткомом, а какой был в свои годы компилятор, какой был слон, какой был слон).
Понятное дело, что ничего эпичного там не было - немного очень простой строковой работы, набившие оскомину фибоначчи и немного работы со связным списком и деревьями (рекурсия, омномном). Ну, короче, один вечер после реально упоротой трудовой недели - могу, значит, еще, на первом курсе учиться.
Девочка то ли гнет дерево не по себе, то ли не познала мантру, что ИТ - это ноулайферство, но в консерватории надо что-то менять. Не мое, впрочем, дело ее жизни учить.
Но фиг с ней, с девочкой, там был интересный вопрос, который я в полубессознанке сделал через жопу, а хотелось красиво. Есть у нас два отсортированных бинарных дерева, нам надо найти мощность пересечения, и нам даже гарантируют, что элементы внутри каждого дерева уникальны.
Вариант через жопу - это пройти одно дерево насквозь и поискать каждый элемент в другом. Были бы это два массива, я бы параллельно по ним прошелся и за один проход все нашел.
Но это деревья, и по условиям задачи (структура данных задана жестко) указателя вверх у нас нет, только налево и направо. В этой ситуации я знаю, как сделать параллельный обход, имея два стека. Но у меня не плюсы, где я взял бы стек из STL и горя не знал, а голая сишка. Писать на автопилоте динамический стек поверх связного списка - ну, это так себе затея в первом часу ночи.
А есть ли более кошерный вариант? Теория-то уверенно говорит, что дерево в глубину без стека не обходится.
Надумал я сейчас только извращенный вариант провязывать стек вызовов указателями (чтобы невозбранно ходить в предыдущие стекфреймы), глубину стека держать как максимум глубин погружения в оба дерева - по сути, эмулируя второй стек на стеке вызовов. При этом что при погружении, что при разматывании то и дело придется "переключать" реальный и эмулируемый стеки. Как-то слишком сложно и кулхацкерски.
Это я, собственно, к чему. Есть некая девочка, назовем ее Х. (нет, не Хуанита). Девочка учится на программистском факультете. Девочке я до того пытался нести в мозг матан и алгебру, их она сдала.
А вот теперь она попросила помочь с пересдачей по погромированию. Я сначала машинально (девочка позвонила аккурат между двумя нервными совещаниями) попросил прислать все задачи и вопросы, и только потом отметил, что на дворе не то, что февраль, а середина его, и сессия закончилась не только сама, но и вместе с пересдачами. Сталбыть, девочка не то, что с хвостом, а в одном шаге от пресловутого компота.
Ну ладно, слава яйцам, у нее не Паскаль, который я бы без методички не вспомнил (хотя у меня на нем написан один курсач - не мой, и одна лаба - не моя), а старый добрый Це. Ну на Це мы могем, и у нас, естественно, есть муха гэцеце (прольем скупую слезу над безвременно почившим ваткомом, а какой был в свои годы компилятор, какой был слон, какой был слон).
Понятное дело, что ничего эпичного там не было - немного очень простой строковой работы, набившие оскомину фибоначчи и немного работы со связным списком и деревьями (рекурсия, омномном). Ну, короче, один вечер после реально упоротой трудовой недели - могу, значит, еще, на первом курсе учиться.
Девочка то ли гнет дерево не по себе, то ли не познала мантру, что ИТ - это ноулайферство, но в консерватории надо что-то менять. Не мое, впрочем, дело ее жизни учить.
Но фиг с ней, с девочкой, там был интересный вопрос, который я в полубессознанке сделал через жопу, а хотелось красиво. Есть у нас два отсортированных бинарных дерева, нам надо найти мощность пересечения, и нам даже гарантируют, что элементы внутри каждого дерева уникальны.
Вариант через жопу - это пройти одно дерево насквозь и поискать каждый элемент в другом. Были бы это два массива, я бы параллельно по ним прошелся и за один проход все нашел.
Но это деревья, и по условиям задачи (структура данных задана жестко) указателя вверх у нас нет, только налево и направо. В этой ситуации я знаю, как сделать параллельный обход, имея два стека. Но у меня не плюсы, где я взял бы стек из STL и горя не знал, а голая сишка. Писать на автопилоте динамический стек поверх связного списка - ну, это так себе затея в первом часу ночи.
А есть ли более кошерный вариант? Теория-то уверенно говорит, что дерево в глубину без стека не обходится.
Надумал я сейчас только извращенный вариант провязывать стек вызовов указателями (чтобы невозбранно ходить в предыдущие стекфреймы), глубину стека держать как максимум глубин погружения в оба дерева - по сути, эмулируя второй стек на стеке вызовов. При этом что при погружении, что при разматывании то и дело придется "переключать" реальный и эмулируемый стеки. Как-то слишком сложно и кулхацкерски.
(no subject)
Date: 2021-02-13 09:15 pm (UTC)1) Говно в дизайне базы. Не, серьезно, говно в организации доступа к данным - это самое вонючее говно. Нет нужного индекса - и у тебя летают full table scan-ы. Индекс есть, но запрос сделан черезжопно, так что в execution plan (explain analyze) он не попадает в индекс, и летит в тот же full table scan. Кто-то переусердствовал с 3НФ, и у вас 100500 таблиц, поэтому любая внятная инфа собирается только десятком join-ов, и что-то опять мимо индекса. И инсерты в какую-нибудь таблицу идут с проверком referential integrity на полтаблицы. А еще у нас нет партиционирования/архивирования, поэтому запросы летают в базу, содержащую заказы за последние 100500 лет, а не за последний месяц. И так далее и тому подобное - короче, реально годные ДБА очень не за красивые глаза имеют сказочные зарплаты.
2) Говно с частыми мелкими запросами. Это люди с инфраструктурным бэком понимают, что любой API-вызов по сети - это дорага, да и с диска почитать, в целом, тоже небесплатно, а среди разрабов я сплошь и рядом вижу неприятие проблем распределенного программирования. Сюда же нежелание реюзать соединения, в запущенном случае приводящие к 100500 TCP или, хуже того, SSL handshakes. Иногда выгоднее дать большой запрос и выкинуть половину в мусор, чем много мелких, потому что гнать данные по установленному соединению, в целом, быстро.
3) Есть еще специфические способы выгонять вычисления на фронт. В 90-х так часто делали: все вычисления на клиенте, потому что он один фиг процессор юзает на 5-10%, а сервер один. Сейчас таж фигня: вот ты высосал что-то из базы и пережевываешь, так ты-то жуешь в памяти, а если пережевываемого пара сотен килобайт, то и вовсе в кэше, и скорость у тебя просто бешеная, а базе надо иногда на диск сходить. Ну и старая фигня, что отмасштабировать stateless или почти stateless фронт, в целом, говно вопрос, лоадбалансеры не вчера придумали, так что горизонтально ты можешь умасштабироваться - а базы... ну, каэшна, есть федерация, есть шардинг, есть селекты к ведомым репликам, только это все начинает, зараза, глючить и валиться, причем последнее иногда с невыразимым грохотом.
Да вообще, когда почитаешь про все эти кафки, редисы, корутины и прочее новомодное дерьмо, то понимаешь, что пряморукий архитектор и годные разрабы могут снимать немыслимые rps с железа из говна и палок. Но нет.
(no subject)
Date: 2021-02-13 10:30 pm (UTC)-
Пргоблема в том что я это в теории понимаю, а в практике я нихааааачу сидеть в профайлере!!!
а придется.