TL;DR Очень подробный разбор алгоритмов решения задачи о кратчайшем пути от классики до двунаправленного А* и ALT с кодом и примерами на OSM

Люди пытались найти более быстрые способы передвижения на протяжении всей своей истории. Появление качественной дорожной системы в римской империи в своё время привело к её расцвету, но со временем выяснилось, что и в продуманных дорожных системах бывают забавные изъяны, как например в небезызвестной задаче о кёнигсбергских мостах, считающейся отправной точкой возникновения теории графов. Неудивительно и то, что с развитием вычислительной техники логистические задачи стали одними из первых, над которыми трудились первопроходцы компьютерных наук. Задача о кратчайшем пути -- одна из них, звучит достаточно просто: есть несколько городов и дорог, соединяющих пару городов между собой, мы хотим попасть из города А в город Б пройдя при этом минимальное расстояние. Первый системный подход к этой задаче был описан в работе Эгервари в 1931г., спустя 25 лет Эдсгер Дейкстра придумал алгоритм, который сейчас является частью любого уважающего себя базового курса алгоритмов на графах. На нём же, будем честны, заканчиваются знания о кратчайших путях у большинства профессиональных разработчиков, ибо сценариев, где реализации с википедии/stackoverflow будет не хватать, крайне мало.

Может показаться, что на самом деле просто не было существенного прогресса с 60х годов, так как Дейкстра предоставил почти асимптотически оптимальный алгоритм решения задачи. На самом деле нет, прогресс был и придумали много чего интересного, хоть и действительно с того времени фокус сместился на другие задачи. Приглашаю под кат если интересно узнать что такого напридумывали, что используется в современных логистических системах, почему меня огорчает отсутствие учёта флага единства в HOMM3 при расчёте пути, ну и наконец, что за мужики на картинке выше рядом с Дейкстрой?

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

В общем вас ждет теория, ещё теория, словесные примеры и даже примеры кода (он на С++, но написан понятно).

А еще это полезно знать на собесах :-)

Данные - это важный компонент системы. Приложение может хранить их где угодно, но в результате все сводится к файлам. Файлы - это хорошая абстракция, но она протекает: если не знать того, как работают ОС или гарантии файловой системы, то легко выстрелить себе в ногу.

Меня увлекла тема отказоустойчивости, а конкретно - отказоустойчивой работы с файлами. В этой статье я попытался соединить все полученные знания:

Кто участвует в процессе записи

Ошибки, которые могут произойти

Что от нас зависит, а что нет

И самое главное - как это этого защититься

С релизом Xcode 14.3 Apple убирает поддержку Rosetta и почти прямым текстом говорит разработчикам, что откладывать адаптацию своих проектов под Apple Silicon дальше уже некуда. Сегодня я поделюсь историей про то, с какими сложностями мы столкнулись в нашем основном приложении Циан, и какое стороннее решение помогло нам избавиться от Rosetta.

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

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

Я расскажу о тех книгах, что были мне доступны в 1987–1993 гг., т. е. тогда, когда я совмещал работу инженера с программированием. Конечно, я упомяну только те книги, что мне действительно помогли; полный список литературы слишком обширен и упоминание их всех больше походило бы библиотечный каталог, чего я делать не намерен. Условно эти книги можно отнести к одной из нижеследующих категорий. Итак — вот мой «золотой фонд».

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

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

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

В 2008 году я устроился ведущим инженером в НИИ Физических измерений, г. Пенза.

Для меня работа в этом НИИ была более чем знакома, я там работал с середины 80-х по середину 90-х. НИИФИ с момента своего создания было сосредоточено на создании датчиков и специализированной измерительной аппаратуры для космической отрасли.

Начало 2000-х характеризовалось тем, что цены на нефть поползли вверх, в государстве появились какие-то деньги, но одновременно стала происходить череда ярких и красочных неудач с нашими ракетами. И вопрос – а что же там происходит с нашими ракетами – создал на НИИФИ фокус ощутимого финансового потока.

Поскольку в этой организации работает куча людей, связанных между собой родственными связями, то, помимо официального молчания по всем щепетильным вопросам, организация была пронизана слухами, что у нас общий бюджет НИИ достиг сначала 0,7 (примерно 2008–2009), далее 0,9; потом 1,3; 2,1 и 2,7 (2012) миллиарда рублей.

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

Люди делятся на 2 лагеря: те, кто слышит разницу между lossless и lossy, и те, кто нет. Формат аудио с потерей качества — это интересная тема, но сегодня мы поговорим о звуке в высоком разрешении — это PCM 24/96 и выше, а также DSD во всех его проявлениях. Я не буду рассказывать теорию, чем отличаются эти форматы, такие статьи легко гуглятся. Лишь вскользь упомяну о теореме Котельникова (Найквиста — Шеннона), которая гласит следующее: «Для того, чтобы оцифровать аналоговый сигнал, а потом его БЕЗ ПОТЕРЬ восстановить, необходимо и ДОСТАТОЧНО, чтобы частота дискретизации была в 2 раза СТРОГО больше максимальной частоты полезного сигнала».

Большие числа != большим числам.

Число 100 большое? Зависит от ситуации. Сравниваем ли мы его с 0,001, или с 100000? Как и многое в жизни, понятие «большой» относительно.

В этом посте мы объясним, насколько большим должно быть «большое» и докажем, что вы, скорее всего, ошибаетесь насчёт закона больших чисел.

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

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

Я работаю над созданием Graphite, источником вдохновения для которого стал внутренний инструментарий Facebook. Когда я решил создать стартап с друзьями, то никогда раньше не слышал о Mercurial, хотя всегда страстно любил инструменты разработчика. Мой предыдущий опыт разработки включал в себя личные проекты, домашнюю работу в колледже, разработку для iOS в Google и развитие инфраструктуры в Airbnb. На протяжении всей моей карьеры использование git было таким же естественным, как воздух. Он настолько популярен, что лично я считал его единственным подходящим инструментом для создания изменений в коде и управления ими.

Забавно, что специалист по Mercurial Грегори Gregory Szorc работал рядом со мной в Airbnb, хотя я знал его только как приятного коллегу, но не представлял, что он контрибьютор.

В 2021 году мои коллеги по команде Томас и Ник раскрыли мне глаза. Они пришли из Facebook и, к моему удивлению, едва знали Git. Зато они имели глубокое понимание паттернов Mercurial и рабочего процесса Facebook на основе «многослойных diff» (stacked diff). Со временем они убедили меня в полезности этого паттерна и мы развернули направление развития компании, чтобы реализовать многослойные diff для разработчиков GitHub.

Но пост посвящён не нашему стартапу. Он о важном вопросе, не дававшем мне покоя последние три года. Почему фейсбукеры не пользуются Git? Зачем они выбрали Mercurial и создали на его основе собственные рабочие процессы? Я знаю что Google не пользуется Git, но это логично, культура разработки Google возникла на пять лет раньше Git. Facebook же был основан примерно в то же время, что и создан Git, около 2004 года, и ко времени, когда Facebook начал серьёзно выбирать инструментарий для управления исходниками, Git был старше и популярнее Mercurial. Так почему же Facebook не использует Git?

_{Внимание! Конкурс «Технотекст» открывает железную номинацию.} 

Хабр меняется, периодически меняются популярные темы и авторы, уходят одни, приходят другие. Но есть несколько разделов, статьи в которых стабильно пользуются успехом и приковывают внимание как профильных специалистов, так и тех, кто оказался здесь случайно. В основном, содержание этих хабов укладывается в три тематики: железо, DIY и информационная безопасность. И если с последними двумя всё более или менее просто и очевидно, то железо на Хабре имеет драматичную судьбу. 

Много лет назад, учась computer science на старших курсах, я долго изучал различные вакансии онлайн, надеясь найти подходящую должность стажёра-программиста.

Кроме вакансий для стажёров я иногда случайно нажимал на объявления о вакансиях «сеньор-разработчика». Помню, больше всего меня поражало то, что первой строкой шло требование определённого количества лет работы: «Эта должность требует 5+ лет опыта».

Полному новичку, ни дня не проработавшему в этой отрасли, такие требования к опыту казались избыточными. Но хотя это немного приводило меня в уныние, я не мог не пофантазировать: «Наверно, пять лет работы программистом — это впечатляющее достижение? Должно быть, для таких людей писать код проще пареной репы».

Время летело, не успел моргнуть глазом, как прошло больше десятка лет. Сегодня я с гордостью могу сказать, что работаю программистом уже 14 лет. Спустя годы боёв на фронтах разработки ПО я осознал, что многие её аспекты сильно отличаются от того, что я представлял на старших курсах, а именно:

• С опытом программирование не становится намного проще, о «проще пареной репы» можно только мечтать.

• Написание кода для множества «больших проектов» — это не только неинтересное, но и опасное занятие, гораздо менее увлекательное, чем решение алгоритмических задач в LeetCode.

• Мышление только с технической точки зрения не сделает тебя хорошим программистом, некоторые вещи гораздо важнее технологий.

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

Автор оригинала Скотт Чакон — сооснователь GitHub и основатель нового клиента GitButler. Этот клиент ставит во главу угла рабочий процесс и удобство разработки, в том числе код-ревью, и не является просто очередной обёрткой над CLI git.

Вам хочется использовать ванильный Git, чтобы управлять репозиторием с объёмом 300 ГБ в 3,5 млн файлов, которые без проблем получают пуш каждые 20 секунд от 4000 разработчиков? Тогда читайте дальше!

Вот агенда блога — наша блогенда:

• Предварительное извлечение.
• Граф коммитов.
• Монитор файловой системы.
• Частичное клонирование.
• Разреженный checkout.
• Scalar.

Это продолжение статьи «Информация об информации», где я показал, что информация – физическая величина, не имеющая ничего общего с духом, сознанием, «информационным полем» и другими эзотерическими понятиями. Но среди философов и мистиков бытует мнение, что физическая и метафизическая информация – не одно и то же. Дескать теория информации изучает только цифровые данные, а информация как таковая – это другое. Ведь об информации можно говорить только при наличии источника и приёмника информации, а значит, её объективно не существует без субъекта, который будет её воспринимать и интерпретировать. Кроме того, ни количество информации по Хартли, ни количество энтропии по Шеннону не позволяют оценить смысл сообщения. Но значит ли это, что смысл, глубину или сложность информации нельзя измерить количественно и объективно? Пожалуй, пришло время разобраться, что такое сложность, как её можно измерить, связана ли она с упорядоченностью системы и есть ли у неё объективные критерии. Также мы выясним, насколько наши сообщения универсальны и можно ли прочитать их вне биологического или культурного контекста.

«ООП для меня означает лишь обмен сообщениями, локальные ограничения и защиту, сокрытие состояния процесса и крайне позднее привязывание», — Алан Кэй (человек, придумавший термин «объектно-ориентированное программирование»)¹