Ужасы нашего городка

[elglin]

Мне несколько раз с интервалом от месяцев до лет снился сон на одну и ту же тему, что я второй раз учусь у себя на факе. При этом я осознаю, что учусь второй раз, и, вроде как, непонятно, зачем, но вот учусь. Ну и мысли (все во сне), что как же я сессию сдавать буду, у меня же работа, отпрашиваться надо будет и все такое.
Это я, собственно, к чему. Есть некая девочка, назовем ее Х. (нет, не Хуанита). Девочка учится на программистском факультете. Девочке я до того пытался нести в мозг матан и алгебру, их она сдала.
А вот теперь она попросила помочь с пересдачей по погромированию. Я сначала машинально (девочка позвонила аккурат между двумя нервными совещаниями) попросил прислать все задачи и вопросы, и только потом отметил, что на дворе не то, что февраль, а середина его, и сессия закончилась не только сама, но и вместе с пересдачами. Сталбыть, девочка не то, что с хвостом, а в одном шаге от пресловутого компота.
Ну ладно, слава яйцам, у нее не Паскаль, который я бы без методички не вспомнил (хотя у меня на нем написан один курсач - не мой, и одна лаба - не моя), а старый добрый Це. Ну на Це мы могем, и у нас, естественно, есть муха гэцеце (прольем скупую слезу над безвременно почившим ваткомом, а какой был в свои годы компилятор, какой был слон, какой был слон).
Понятное дело, что ничего эпичного там не было - немного очень простой строковой работы, набившие оскомину фибоначчи и немного работы со связным списком и деревьями (рекурсия, омномном). Ну, короче, один вечер после реально упоротой трудовой недели - могу, значит, еще, на первом курсе учиться.
Девочка то ли гнет дерево не по себе, то ли не познала мантру, что ИТ - это ноулайферство, но в консерватории надо что-то менять. Не мое, впрочем, дело ее жизни учить.

Но фиг с ней, с девочкой, там был интересный вопрос, который я в полубессознанке сделал через жопу, а хотелось красиво. Есть у нас два отсортированных бинарных дерева, нам надо найти мощность пересечения, и нам даже гарантируют, что элементы внутри каждого дерева уникальны.
Вариант через жопу - это пройти одно дерево насквозь и поискать каждый элемент в другом. Были бы это два массива, я бы параллельно по ним прошелся и за один проход все нашел.
Но это деревья, и по условиям задачи (структура данных задана жестко) указателя вверх у нас нет, только налево и направо. В этой ситуации я знаю, как сделать параллельный обход, имея два стека. Но у меня не плюсы, где я взял бы стек из STL и горя не знал, а голая сишка. Писать на автопилоте динамический стек поверх связного списка - ну, это так себе затея в первом часу ночи.
А есть ли более кошерный вариант? Теория-то уверенно говорит, что дерево в глубину без стека не обходится.

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

Comments

[juan_gandhi]

А что, рекурсия запрещена, что ли?

На скале это (правда, не эффективно):

def isin[A](tree: Tree[A], value: A) = tree != null && (tree.head == head || isin(tree.left, value) || isin(tree.right, value))

def count[A](tree1: Tree[A], tree2: Tree[A]) = if (tree2 == null) 0 else ((if (isin(tree1, tree2.head)) 1 else 0) + 
count(tree1, tree2.left) + count(tree1, tree2.right))

[elglin]

И если мы присмотримся к этому алгоритму, то он проходит полностью tree2 и для каждого элемента ищет его в tree1. M * logN, те же яйца, только в профиль.
Такой алгоритм существенно использует тот факт, что одно дерево является деревом поиска, и никак не задействует свойства другого дерева. А вот если бы у нас оба дерева были бы реализованы так, чтобы позволяли независимый упорядоченный обход за интегральное O(N), то на той же идее, на какой работает mergesort, мы бы мощность пересечения нашли за O(N+M).

[juan_gandhi]

О, кстати да, по принципу mergesort. У меня только не получилось забацать такой алгоритм.

[elglin]

runner1 = tree1.first(); runner2 = tree2.first();
while(runner1 && runner2){
if(runner1->x == runner2->x) count++;
if(runner1->x <= runner2->x) runner1 = tree1.next(runner1); else runner2 = tree2.next(runner2);
}
Все сводится к реализации метода next(). Алгоритмически он тривиален: если можем уйти направо, идем направо один шаг, потом налево до упора; если не можем, идем вверх, пока не появляется поворот направо; если дошли до корня, а поворота все нет, то уходим на NULL. Если у нас в структуре дерева есть указатель вверх, это решается без стека.
Если нет, то для похода вверх нам нужна вся история текущего пути от корня дерева в стеке. Для обхода двух деревьев параллельно нужно два стека. Естественный обход дерева через рекурсию держит стек обхода дерева в стеке вызовов.
Эмуляция, которую я придумал на идеологическом уровне, следующая:
1) В каждый рекурсивный вызов мы прокидываем два указателя на элемент дерева, один из которых может быть NULL. Так мы строим два параллельных стека.
2) Дополнительно мы по ссылке передаем указатель на указатель из предыдушего вызова. По сути у нас связный список (который годно эмулирует стек) - который весь лежит в стеке вызовов.
3) Дополнительно у нас есть "глобальные" указатели на голову каждого списка (=вершину стека) и, скорее всего, еще сколько-то глобального состояния, которые мы все по указателю таскаем между вызовами.
4) Если нам надо пойти вниз в дереве, куда мы погрузились глубже, мы проваливаемся на еще один уровень рекурсии. Если надо пойти вниз в другом дереве, манипулируем вторым связным списком (все элементы уже есть).
5) Аналогично, если надо всплыть в более глубоком дереве, мы всплываем на один уровень, сохранив что-то при необходимости в глобальном состоянии; если надо всплыть в более мелком, то манипулируем вторым списком.

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

[juan_gandhi]

Было бы мило написать все это рекурсивно. Держать пару, ((t1, state1), (t2, state2)), и вычислять, что передать вглубь.

[scif_yar]

Где то что то списано неправильно, или задача на каком-то тупом примере из учебника построена - как надо.

И сдается мне, это может оказаться тупая задача "конвертируем дерево в массив путем обхода и потом селект вхере
https://habr.com/ru/post/267855/

[elglin]

Тебе неизвестна мощность дерева, то есть если ты хочешь конвертировать в массив, тебе нужен динамический массив. Амортизированно O(N) и потом mergesort, да.
Я бы сказал, что наивная реализация динамического стека проще, чем динамического массива, во втором случае ты с realloc-ами напляшешься.
Короче, с STL задача не стоит вообще, без STL в исходной структуре данных требует реализации структуры из STL - либо если в структуре данных разрешается проставлять указатель на родителя, то решается бесстеково, потому что в этой реализации ты можешь корректно отработать next() на дереве без дополнительной памяти.

[juan_gandhi]

Да, если оба дерева превратить в стеки, то и вопросов нет.

[scif_yar]

>> Амортизированно O(N)
-
А мы это еще не проходили!
---
>>Короче, с STL задача не стоит вообще,
-
STC )))) кругом STC и вместо пузырька у нас sort-object

[scif_yar]

(чот заржав) compair-tree | select-power )))

[elglin]

Да не смешно ни разу. В питоне ты тоже легко можешь родить однострочник вроде len(set(t1) & set(t2)). Можно написать любой код и говнокод тоже, и, пока ему не встретится дофигищевый объем данных, все будет чики-поки.
Вопрос в том, что если программиста не учить сложности, структурам данных и вот этим всем - он будет производить только и исключительно говнокод. А закон Мура уже сломался, халява-то кончилась, и энергопотребление датацентров уже измеряется в процентах от мирового.
Я своими глазами видел копирование объекта как:
$foo = $bar | convertto-json | convertfrom-json # fuck efficiency
Но зачем быть говнокодером, если можно им не быть?

[scif_yar]

>> и, пока ему не встретится дофигищевый объем данных, все будет чики-поки.
-
У нас целый отдел, который кивает на инфру.

[elglin]

Абсолютно реальный диалог. Терки за перспективы унести базу за 15 миллисекунд от аппликухи.
Я: Мужики, тут есть такой аспект. Если приклад дергает базу кучей мелких запросов, то эти 15 мс на них умножатся, и все начнет адски тормозить.
Неловкое молчание. Потом вступает один из разрабов:
Р: А по ходу так и есть, у нас на страницу полсотни вызовов в базу.
Так никуда и не перенесли в итоге, потому что без субмиллисекундной задержки до базы оно не работает. Ну то есть работает, но как будто на 80386.

[scif_yar]

Я вторую неделю пытаюсь собраться с силами и начать хотя бы читать про архитектуру того, что у нас есть, почему оно вот так и что в итоге. И фоновых попыток обьяснить, что любые их идеи размазать говно на N+1 дисков не дадут ничего - потому что у них очереди и задерки сейчас - в пределах 1-2 мс. Не дает их приклад нагрузки. А значит что? а значит разворачивать тесты и делать нормальный QA. А я не хочу, я хочу спать дома и заниматься своим куском.

[elglin]

Ну здесь я могу высказать несколько офигенно ценных гипотез.
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 с железа из говна и палок. Но нет.

[scif_yar]

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

[drraug]

очень классными и интересными вопросами ты занимаешься. Жалко только, что программисты уже кажется совсем перестали ими интересоваться.

[elglin]

Да я ими всерьез не занимаюсь, я не алгоритмист и никогда не был. Это ближе к хобби. Другой вопрос, что пока я задаюсь такими вопросами и тренирую мозги, я еще на что-то годен, а вот когда перестану - вот тогда будет пора на выход из профессии.
Зато с листа нашел девочке красно-черное дерево, не являющееся АВЛ-деревом, и с листа же дал идею конструктивного доказательства того, что каждое АВЛ-дерево можно покрасить в красно-черное. Годное фундаментальное образование не пропьешь, особенно если оно дает умение пользоваться источниками и достаточно быстро в них въезжать.
Печальна та ситуация, когда люди не могут пользоваться источниками несмотря на то, что нужные ссылки - это не только первая страница, но и первые 3-4 ссылки выдачи Гугла.