#анализ_данных #домики_для_роботов #кейс

У меня бывают иногда заказы по анализу данных, не слишком часто, но направление интересное, планирую его расширять.
Пару недель назад для одного очень NDA клиента покопался в данных и нашел даже не просто value, а прямо слона в комнате. Увидел, как очень просто уменьшить расходы в 2 раза. Сейчас перепроверяем, а то кажется слишком хорошо, чтобы быть правдой.
Я планировать улучшить процессы на 1-2%, это бы окупило с запасом мои услуги. А ненароком получилось в десятки раз мощнее.

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

Я кстати зимой объявлял про то, что пытаюсь двигаться в сторону создания домиков для роботов. Дата центры очень дорогие, так что идти в эту сторону сложно, а вот лежать получается. И этот проект как раз из этой серии.

#алгоритмы #новости
Пока ИИ наступает, человеки умудрились ускорить незыблемое - алгоритм Дейкстры. 😄

Новый алгоритм поиска кратчайшего пути на графе так называемый «барьер сортировки»

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

🚀 Что предложил новый алгоритм? https://arxiv.org/abs/2504.17033?utm_source=Securitylab.ru
Вместо сортировки границы текущей области, алгоритм разбивает её на кластеры и выбирает по одному узлу из каждого.
Это снижает количество сравнений и устраняет необходимость сортировки.
Работает как для ориентированных, так и для неориентированных графов с произвольными весами.
Вдохновлён идеями Беллмана-Форда, но использует их точечно, чтобы выявить ключевые «узлы-связки».

📈 Почему это важно?
Это первый универсальный алгоритм, который обходит сортировочный барьер без ограничений на тип графа.
Потенциально меняет подход к маршрутизации, логистике, сетевому анализу и многим другим задачам.

Для чего это нужно:
🚗 1. Навигация и транспорт
GPS и карты: Google Maps, Waze и другие используют алгоритмы кратчайшего пути для построения маршрутов.
Логистика: Оптимизация доставки товаров, маршруты грузовиков, дронов и курьеров.
Транспортные сети: Расчёт времени поездки в метро, автобусах, авиаперелётах.
🖥 2. Компьютерные сети
Маршрутизация пакетов: Протоколы типа OSPF и BGP используют кратчайшие пути для передачи данных.
Оптимизация трафика: Балансировка нагрузки между серверами и дата-центрами.
🧬 3. Биология и медицина
Анализ молекулярных сетей: Поиск путей между генами, белками, метаболическими реакциями.
Медицинская диагностика: Сравнение симптомов и заболеваний через графы знаний.
🛒 4. Рекомендательные системы
Поиск связей между пользователями и товарами: Например, в Amazon или Netflix.
Социальные сети: Определение степени близости между людьми (например, «друзья друзей»).
🏙 5. Городское планирование и робототехника
Планирование движения роботов: В складских системах, на заводах.
Оптимизация инфраструктуры: Где строить дороги, мосты, электросети.
🎮 6. Игры и искусственный интеллект
Играющие агенты: Перемещение персонажей по карте.
AI-планирование: Принятие решений в стратегических играх.
На русском https://www.securitylab.ru/news/562195.php

#архитектура #отладка #касдев #системное_мышление

Есть такая классическая головоломка для программистов - Ханойская башня. Нужно переставить блины пирамидки с одного штыря на другой. Но так, чтобы большой блин не лежал на блине меньшего размера. Благодаря дополнительному третьему штырю эта задачка имеет решение. Но её сложность растёт, как степень двойки от числа блинов. Чтобы передвинуть 10 блинов нужно больше тысячи операций, а чтобы 20 - больше миллиона.

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

Блины бывают разные - это разнородные стейкхолдеры. Лебедь, щука и рак - пример проекта с 3 стейкхолдерами и всего с тремя блинами.
Это могут быть компоненты программы. Сейчас делаем систему в одном проекте. Есть IT системы заказчика, которые как-то работают. Есть делает исполнитель, а есть расчетное ядро, которое делаю я как субподрядчик.
Получается комплексная система, в которой данные по разному работают, по разному воспринимаются.
Отладка собственно замедляется, потому что часто проблема даже не внутри кого то а на границе между компонентами.

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

Если ЛП задача работает быстро и дает оптимальный результат, норм. А если дает ответ за разумные сроки это +1 блин.

Блинами являются сложные требования к мат модели, которые могут давать между собой странные сочетания.

Как с этим бороться ? Для начала считать эти блины и контролировать чтобы они не росли просто так.
Внимательно планировать архитектуру, чтобы число блинов было минимально.
Чинить ошибки, которые увеличивают, число блинов.

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

Так же видна цена принятия того или иного архитектурного решения.

На уровне клиентов - подсвечивать сразу будущие проблемные места проекта и вообще формировать проект с учетом этого

#lp #mip #солверы #алгоритмы

highs отличный солвер и быстро развивается.
Весной уперся в производительность scip протестил highs и он сильно лучше работает.
Вчера уперся в производительность highs, поигрался с настройками и задача стала считаться вместо часа минуту. Просто включил вместо симплекс метода (относительно) свежий метод PDLP - прямодвойственное гибридное линейное программирование.

Важно не забывать играться с солверами и настройками хотя бы раз в полгода.
Правда, детские болезни опенсорса тоже никуда не делись. Набор highs+pyomo+pdlp+abs_mip_gap не работает, вчера до ночи ковырялся из-за этого.

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

Нельзя писать посты по горячим следам. Солвер highs работал очень быстро просто потому что считал вещественную задачу.
Нашел вот такую интересную и не очевидную запись в документации.
If "simplex"/"ipm"/"pdlp" is chosen then, for a MIP (QP) the integrality constraint (quadratic term) will be ignored
Догадаться проверить решение сразу не догадался 🙈
В общем pdlp никакая не серебряная пуля.
Солверы конечно с разной скоростью работают, но надо было заподозрить что укорение в 50 раз это перебор.

#мысль #разработка
Метод протаптывания тропинок.

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

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


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

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


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

#бутылочное_горлышко #текучка #отладка #метод_разрыва

Я уже несколько лет периодически катаюсь на серфе на искусственной речной волне. Очень удобно совмещать с работой.
И работаешь активно и отдыхаешь. С созвонами есть определенные проблемы, надо научиться их преодолевать. В целом из-за хорошего настроения получается даже больше и эффективней работать, чем в Москве.

Наблюдал за работой тренеров и пришел к интересным лично для себя выводам.
Работа тренера похожа на отладку ошибок. Любой тренер видит, что у тебя не получается. Хорошие тренер подскажет какое движение надо тренировать.
Но реально крутой тренер может понять причины этого и увидеть главный микроэлемент, который не идет и помочь отладить именно его.
Я видел несколько примеров крутых тренеров, у одного в записной книжечке было 1300 разных тренировок и он мог сходу предложить наиболее подходящий вариант в данный момент. Другой с ходу просто придумывал упражнение под меня и оно реально помогало.

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

Кстати на серфе я катаюсь здесь, место отличное.

#программирование #отладка #метод_деления_пополам
Метод деления пополам (а также метод локализации, и метод разрыва).

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

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

Номер квартиры больше 500? Да. Номер квартиры больше 750. Нет. Номер квартиры больше 625 ?..

В программировании тоже самое. У нас есть программа, которая работает не так как нам хотелось бы.
То есть имеется определенное ожидание, и реальность. Эта формулировка важна, так как иногда оказывается, что в программе баги нет, а есть например недоработка в ТЗ, или какие-то личные предустановки, которые оказываются неверными. Метод локализации, как путеводная нить может вывести и за пределы программного кода.

У нас есть в итоге некоторый разрыв - наше ожидание и реальная работа программы, которая отличается от нашего ожидания.
Начинать надо именно с разрыва, то есть нужны две точки - в одной точно все ок, а в другой точно не ок. Я постоянно вижу, как даже опытные программисты просто блуждают вокруг "не ок" точки. Это как пойти в дремучий лес без компаса и телефона. Может и прокатит, но может и нет.

Идем дальше, как делить пополам?
Сначала надо найти расчет (то есть результат работы на паре входные данные/программа), в котором ожидание совпадает с реальностью.
Часто удобным примером рабочей точки является пустой код и пустые входные данные.

Когда такой расчет есть, надо сближать находить какое-то промежуточный расчет. Вариантов уполовинивания много и они все важны:
1. Можно сближаться по входным данным:
1.1 упростить некорректные входные данные. Например в своей программе расписания самолетов, я сделал параметр время расчетов, который можно выставлять не только по дням но и по времени. Дальше я методом деления пополам нахожу момент времени, когда всё начинает ломаться и это дает мне конкретное единичное изменение входных данных (рейс или ТО) на которые надо внимательно посмотреть. Еще это полезно, так как ускоряет работу программы и значит и отладку.
1 .2 Выкинуть лишнее из "неок" расчета или добавить что-то к "ок" расчету.
2. Ищем точку расхождения в коде.
2.1 Ставим брекпоинты, логи,
2.2 Пишем ассерты,
2.3 сохраняю даже дата-фреймы в некоторых точках чтобы проаналазировать. Все чтобы отловить момент в коде перехода с ок на неок.
2.4 для ускорения работы программы я отрубаю лишнее - могу просто удалить код после точки не ок, чтобы он не мешался или просто ставлю exit()
2.5 Можно так же при запуске функции сохранить входные данные и сделать тест. То есть запуск конкретной функции с конкретными входными данными.
2.6 Упрощаем код. Можно просто выкидывать все лишнее и смотреть ошибка пропадает или нет.

3. Ищем ветку гита когда все сломалось. Тоже очень полезная штука, если бага всплыла не в момент разработки кода, а позже. Да и в момент разработки тоже иногда помогает. Сразу видна часть кода, которая влияет. Кстати, размер коммитов после сквоша я учитываю с учетом последующей отладки. Слишком большие коммиты делать не надо, лучше чтобы каждый коммит был реализацией одной мысли.

4. Локализуем в выходных результатах на то, что смотрим. Если это расписание, то конкретный кривой рейс, если какие-нибудь товарные позиции, то конкретную позицию. Если там такой конкретики нет, то её можно специально создать. Например если каждая позиция сама по себе ок, но их сумма некорректна, то создаем сумму и отслеживаем её как один из результатов. Так же выбор конкретного параметра для отслеживания может позволить делать анализы по коду и удалять лишний код.
( продолжение следует)

#программирование #отладка #метод_деления_пополам

Метод деления пополам, продолжение.

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

Чтобы найти ошибку надо не просто сделать 10-20 итераций по локализации, а сделать их быстро.
Собственно, потому и надо делить примерно пополам, что это самый быстрый способ локализации.
Вот мои способы ускорения:
1. Упрощаем задачу, это не только уполовинивание, но и ускорение.
2. Я делаю простой критерий, по которому я определяю ок/не ок ситуацию. Например, я смотрю на конкретный объект и что с ним происходит. В относительно сложных случаях я пишу простую функцию, которая этот критерий вычисляет и желательно в численном виде.
3. Вообще я стараюсь делать отладку так, чтобы оставались артефакты в виде программного кода, тогда их можно будет повторно использовать в следующий раз и сэкономить время. Это одна из причин почему я очень редко стал пользоваться классическими методами отладки.
4. Помимо написания артефактов, вообще выбор языка программирования, стиля программирования разбиения на функции можно сразу начинать с того как потом отлаживать программу. Например я пишу программы по фичам, так чтобы можно было легко включать/выключать функциональность программы.


5. Можно не только упрощать задачу, но и подбирать параметры, при которых разрыв становится более ярким. В численных случаях я подбирал параметры которые максимизировали функцию ошибки. В максимальном случае ошибка быстро находилась.
6. Делить пополам можно разными способами, я каждый раз выбираю самый простой по времени. Область поиска можно мысленно представить в видео многомерного брусочка, то его удобней делить пополам по самой длинной стороне, так как там проще не промахнуться.
7. Иногда есть возможность поделить не пополам, а сразу на 10 или 100 частей. Например, сделать конкретный ассерт и расставить его в 10 местах. Или внутри цикла.
8. Бывает наоборот сложные ситуации, когда кроме ок/неок есть еще ситуация непонятно. Например, MIP модель может работать быстро – ок, падать по инфизиблу – не ок, или работать медленно. Если она работала медленно мы что-то поправили, и она снова работает медленно, то непонятно. В таких ситуациях тоже можно провести эксперимент, просто он нам даст не 1 бит информации в среднем, а меньше (бит это делимая величина).
Например эксперимент, который в 25% случаях даст не ок (и уполовинит область поиска), в 25% ок (и тоже уполовинит) и в 50% непонятно. То это просто эксперимент, который нам дает полбита информации.

Подитоживая сказанное, отладка для меня это поиск места ошибки и для выбора того или иного шага я использую критерий:

Скорость получения информации о месте ошибки = <мат. ожидание полученной информации>/<время>

Мат ожидания полученной информации это немножко переделанная формула энтропии .
Например если вы проводите эксперимент и он делит ваше пространство поиска как 10% к 90%. То вы получите - 0.1log2(0.1) -0.9*log2(0.9) ~ 0.469 бита информации, что немножно хуже, чем в примере про непонятно.
Понятно, что на практике я эти вещи считаю на глазок и вообще самое главное это время в знаменателе.

Выкатываем постепенно первую версию продукта. Скоро еще сайт обновим

#жизнь #3д #ии
Головоломка адмирала Макарова.

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

Лет 5 назад я попросил друга и он мне выточил набор из 6 головоломок фрезерным станком из дерева. Было прикольно, все собрал. Но я постепенно эти кресты раздарил. Что-то осталось, но полного набора нет. Друг больше не готов эти штуки делать, меньше свободного времени и это было реально долго и сложно. Еще я использовал эти кресты в качестве визиток, и моего первый клиента получил благодаря такой визитке.

А вчера случился новый подход. У меня есть 3д принтер для детей. И я тут собрался и навайбкодил на блендере модель этих крестов. Самое сложно было на вайбкодить люфты и вырезанные надписи, чтобы не путать детальки между разными наборами. Но в общем справился. Блендером я тоже раньше никогда не пользовался. БЯМ это сила и блендер :)
Сделал пока классический вариант, на выходных сделаю полный набор.

Если кому нужен такой набор - обращайтесь )