[Из песочницы] О команде ракетчиков, которые смогут

Немного о себе

Так случилось, что я после школы поступил учиться в Московский авиационный институт (МАИ) на 601 кафедру, аэрокосмический факультет. Учился я проектированию космических аппаратов и разгонных блоков. С 2004 года я пошёл работать в проектный отдел КБ «Салют» (ФГУП «ГКНПЦ им. М.В.Хруничева»). Попал я в сектор, который занимался проектированием Ангары и модернизацией Протона. С 2008 года я работал в должности заместителя руководителя Проектно-исследовательского центра ФГУП «ГКНПЦ им. М.В.Хруничева», а в 2014 году я основал свою частную компанию «КосмоКурс», куда и ушёл работать с головой. Данная статья является обобщением моего опыта в области создания ракет-носителей и формирования команды, которая эти ракеты должна создавать.

Сама статья

Мне часто задают вопрос – почему ты скептически относишься к заявлениям коллективов о создании ракет? Обычно я отвечаю парой фраз или слов в стиле закона сохранения нормо-часов в природе. Но мне в ответ «прилетает», что это всё голословно. Ну чтобы не быть голословными, давайте рассмотрим условно классический пример жидкостной сверхлёгкой ракеты для выведения спутников. Примем, что конструкция её достаточно классическая и стандартная, без многоразовости и прочих модных штуковин. А количество ступеней может быть от двух до трёх.
Попробую вам рассказать какая-же минимальная команда нужна, чтобы создать свою собственную ракету, кто нужен для того, чтобы эту ракету спроектировать. Самый первый секрет в том, что надо проектировать не ракету, а комплекс, который помимо ракеты включает в себя вопросы наземной инфраструктуры (космодром + ЦУП), а также вопросы организации производства и испытаний. Ну начнём.

• Специалисты по общему проектированию. Которые ведут увязку всего комплекса в целом. По ракете задают основную концепцию, курируют весовую сводку и параметры всех систем, отслеживают соответствие друг другу всех систем ракеты и комплекса. Тут должно работать минимум 3 специалиста.
• Компоновщики. Это такие продвинутые специалисты по конструкции, которые прорабатывают (прорисовывают) и увязывают всю ракету. Они также определяют взаимодействие ракеты с наземным оборудованием, рассчитывают все массово-центровочные и инерционные характеристики. Предварительные расчёты на прочность тоже делают они. Тут должно работать минимум 4 специалиста.
• Баллистики. Эти специалисты совместно с проектантами проводят проектно-баллистический анализ и определяют все характеристики ракеты. Потом они постоянно сопровождают проект, проводя поверочные расчёты. Они учитывают все требования по назначению (тип орбиты, масса и т.п.) и ограничения. В качестве ограничений в основном выступают поля падения, скоростной и тепловые потоки при сбросе головного обтекателя и при отделении ускорителя первой ступени, допустимые перегрузки и прочие динамические ограничения. Некоторые из ограничений известны сразу, некоторые появляются в ходе проектирования, а некоторые в ходе аж лётных испытаний. Тут должен работать минимум 1 специалист.
• Динамики полёта. Это такие более глубокие баллистики, которые рассматривают ракету уже не как материальную точку, а как тело, которое может вращаться под действием внешних сил и управляющий воздействий. Правда потом должны учитываться реальные жёсткости ракеты, колебания топлива в баках, резонансы и неточности системы управления. Их основная работа – это подбор законов управления ракетой и стохастический анализ, который показывает реальные точности, отклонения и потребности в управлении с заданной вероятностью. У них в качестве ограничений выступает множество отклонений всех параметров и систем ракеты, а также вероятностный характер внешних воздействий. Тут должно работать не менее 3 специалистов.
• Аэродинамики. Специалисты по взаимодействию ракеты с атмосферой. От них нужны круговые продувки ракеты и её отделяющихся частей, а потом подтверждение и уточнение этих характеристик на испытаниях в аэродинамических трубах. Тут должно работать минимум 2 специалиста, им же ещё испытания организовывать.
• Тепловики. Они рассчитывают внешнее тепловое воздействие на конструкцию, распределение тепла по ракете, определяют потребные параметры теплозащиты, теплоизоляции и термостатирования. При этом проверять они должны всё, от корпуса, до приборов. Тут должен работать минимум 1 специалист.
• Прочнисты. В первую очередь прочнисты должны определить все нагрузки, действующие на ракету на всех этапах её эксплуатации, в том числе при хранении и транспортировке. Потом они выполняют поверочные расчёты всей конструкции. Также они определяют собственные частоты колебаний, жёсткости, податливости и распределение ударных нагрузок. Тут должно работать минимум 2 специалиста.
• Технологи. Они работают в тесном контакте с компоновщиками и прорабатывают конструкцию на технологичность. Они определяют типовые технологические процессы производства. Потом они прорабатывают вопросы организации производства. По сути это должен быть план всего завода со штатным расписанием и требованиям по квалификации работников. Тут должно работать минимум 2 специалиста.
• Специалисты по надёжности. Название говорит само за себя. Они рассчитывают надёжность, дают рекомендации по резервированию и определяют требования к проведению испытаний для подтверждения требований надёжности и безопасности. Они курируют такой страшный документ как анализ видов, последствий и критичности отказов. Тут должен работать минимум 1 специалист.
• Специалисты по наземной эксплуатации. Они формируют все требования к наземной инфраструктуре и формируют технологию работы с ракетой при наземной эксплуатации. Это по сути специалисты по общему проектированию, но в области наземного оборудования и эксплуатации. Также эти специалисты совместно с проектантами курируют вопросы оценки воздействия комплекса на окружающую среду, проводя все необходимые расчёты. Тут должен работать минимум 1 специалист если потом заказывать работу по проектированию наземных систем кооперации. Если проектирование наземных систем оставить себе, то тут нужно ещё минимум 5 специалистов.
• Специалисты по системам управления. Это по сути специалисты по общему проектированию, но в области систем управления. Они формируют основные требования к системам управления и телеметрии, обеспечивая взаимную увязку со смежными системами. Также они формируют перечень всех датчиков, потребителей электроэнергии и т.п. Тут должен работать минимум 1 специалист если потом заказывать работу по системам управления и телеметрии кооперации. Если проектирование систем управления и телеметрии оставить себе, то тут нужно ещё минимум 8 специалистов.
• Специалисты по пневмогидравлическим системам. Эти специалисты проектируют всё, что связано с трубопроводами и клапанами. Это гидравлические, прочностные, тепловые и прочие сопутствующие расчёты. Тут должно работать минимум 4 специалиста.
• Специалисты по двигателям. Это проектанты по двигателям. В случае, если они выполняют только функции общего проектирования по двигателям, а дальше передают работу кооперации, то достаточно 2 специалистов. Если они сами разрабатывают двигатели, то на один двигатель надо минимум 5 специалистов, на два — 7 специалистов, на три — 8 специалистов.

Итого мы видим, что если вы ходите ориентироваться на команду высококлассных специалистов, которые обладают значительным опытом, прекрасной работоспособностью и умеют работать друг с другом, то надо минимум 27 специалистов только, чтобы спроектировать ракету (комплекс). А если учесть, что мы живём в реальном мире, то нужно минимум 35 специалистов, которые знают, что делать. Если ориентироваться на свои силы, как SpaceX, то в идеальном мире нужно минимум 47 специалистов, а в реальном минимум 55-60 специалистов. Многие заметят, что я не учёл кучу вспомогательных специалистов, рабочих, да и вообще конструкторов для выпуска КД маловато. Но моей целью было показать прям минимум-минимум.
Теперь про заявления и желания. Мечты, что можно работать удалённо и на пол ставки, а также брать перечисленных мной работников на аутсорс, так и остаются мечтами. Я таких успешных примеров не знаю. Да и работа этих специалистов в ходе проекта ведётся без передышки и с большим напрягом, идут постоянные уточнения, переделки и доработки. Исключение составляет организация собственного проектного офиса численностью до 10 специалистов. А все работы по комплексу отдаются на аутсорс, например, в Роскосмос. По такой схеме вроде сейчас идут S7 Space. Следующая проблема — часто проектом называют презентации на 20 или аж целых 100 листиков. Действительно, для формирования предварительного облика ракеты достаточно 2-3 «натасканных» специалистов. И они в течении недели сформируют облик ракеты и ещё в течении недели-двух оформят это всё в красивый документ. Так вот это не проект, а ориентировочные предложения. Далее всё это перепроверять и пересчитывать года три минимум (итерации + стадии проектирования). Иногда предлагают после такой «прикидочной» работы сразу переходить к изготовлению опытного образца. Это всё предлагается от того, что перечисленных мной специалистов на горизонте не видно или кажется, что они не нужны. Так вот выпустить КД на опытный образец ракеты проще простого, если проработку и уточнения не проводить. Но весь результат можно сразу выкинуть на помойку, ну или на полочку поставить.
Вот получилась такая неплохая памятка, сколько нужно специалистов и зачем. Надеюсь это многим поможет более правильно провести оценку своих идей и предложений в области создания ракет. Я не показал, как распределён наём этих специалистов по времени. Но могу подсказать, что если вы правильно подберёте данное количество именно этих специалистов, то через три года у вас очень вероятно полетит ваша ракета. Правда для этого вам нужно будет ещё организовать производство и возвести всю необходимую наземную инфраструктуру. Но это уже совсем другая история.

Let's block ads! (Why?)

[Из песочницы] Почему психоанализ так популярен в России и как обманывают пациентов

Когда я был студентом в Питерском IT Вузе, я долгие годы вынашивал идею изучить некоторые разделы в медицине, чтобы лучше понять мои проблемы со здоровьем, и изучать медицину сразу на английском языке. Эта идея выстрелила очень сильно (не смотря на трудности с языком в самом начале), и уже через пару лет я гуглил исключительно на английском, читал webmd и medicalnewstoday, решал задачки из американского аналога ЕГЭ (Advanced Placement Psychology и Biology), использовал Амазон как отправную точку при выборе книг, а также заглядывал в справочник The Merck Manual.

У меня сложилось впечатление, что в западной медицине психотерапия основана на КПТ (CBT), а психоанализ уже давно ушел в узкую частную практику. Опытный врач НИКОГДА не будет рекомендовать психоанализ как лечение. Однако, когда я начал общаться с моими знакомыми из СПБ (все они — достаточно хорошо образованные и занимаются интеллектуальным трудом), то оказалось, что 4 из 4 (100%) считают, что психоанализ — это основа (фундамент) психотерапии. У меня случился очень большой разрыв шаблона, и я попытался разобраться…
Сразу прощу прощения за большое количество грамматических и орфографических ошибок в моем тексте. Я пожертвовал русским языком в пользу английского, чтобы получить доступ к огромному объему знаний и перевести их для вас.

Психология — наука или нет?

А это зависит от того, какой язык вы используете. Русское слово «психология» несет в себе негативную коннотацию и обычно ассоциируется с манипуляцией и обманом, а также с треш-книгами «ни о чем». А на западе, psychology — это полноценная наука, основанная на математике (статистике), использующая экспериментальный подход и две доминирующие школы (поведенческая и когнитивная).

Ещё в школе я начал глубоко задумываться, что не так с психологией. У меня была депрессия с сезонным паттерном, и я надеялся самостоятельно освоить психологию и по всем сам разобраться. Я очень много рефлексировал над своими мыслями и замечал, что если думать по-разному, то можно успешно регулировать свое настроение. А ещё можно измерять настроение в численном виде (по шкале от 0 до 10), производить измерения ДО и ПОСЛЕ некоторой активности, а потом математически обработать эти результаты и на основе средних значений делать выводы об эффективности подходов. Я изобрел что-то типа примитивного КПТ, когда я каждое утро прохожусь по специальному листочку с вопросами, вспоминаю негативные мысли и переформулирую их в позитивные. Это было в 2013, и я помню, как мое качество жизни выросло. Я поставил цель когда-нибудь изучить английский и найти область психологии, в которой есть упражнения с мыслями.

Психология как предмет в универе

В 2019 я решил попробовать изучить психологию более подробно и нашел канадский курс "Introduction to Psychology" на курсере. Очень хороший и качественный курс, объемный и при этом интересный. Мне было интересно, как психология может быть «предметом» в универе. Я прошел курс примерно за полтора месяца, и узнал очень и очень многое, от клинической и когнитивной психологии, до введения в нейронауку и принципов работы памяти. В моем сознании сформировалась очень четкая и ясная картина того, что из себя представляет психология. Очень рекомендую этот курс, т.к. он отлично расставляет свои точки над i.

А что касается психоанализа, то он есть только в главе «История». Стив Джордан (лектор) сначала приводит фундаментальные концепции психоанализа, которые кажутся весьма забавными, вроде анально удерживающей и анально выталкивающей типов личности или Эдипов комплекс. Потом Стив сказал набор враз, которую я запомнил на всю жизнь:

А что касается эффективности психоанализа, то ЛЮБАЯ терапия будет эффективнее, чем отсутствие терапии. Особенно для пациентов с большими кошельками.

Получается, что нет смысла платить 3000 руб в час за «специалиста»-психоаналитика. Можно с той же эффективностью взять поддерживающего психолога за меньшие деньги, а ещё можно найти на авито людей, которые готовы с вами общаться и поддержать в трудное время за довольно скромную сумму. Это, если у вас нет друзей.

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

В моем кругу общения

Собственно, я стал спрашивать знакомых, что они думают о психологии в целом. Оказалось, что среди всех моих знакомых нет ни одного сторонника КПТ (!!!). Мне удалось обратить 2х из 4х знакомых в Сторону КПТ и теперь они у меня есть, но тогда это казалось каким-то безумием. Я начал чувствовать себя сектантом КПТ, которое чудесно себя проявляет на практике и позволяет мне повышать качество жизни. Я регулярно проходил тест Бека на депрессию и увидел, что настроение можно измерить в численном виде. Я начал практиковать упражнения из книгу Дэвида Бьерна Терапия настроения. Клинически доказанный способ победить депрессию без таблеток. На тот момент её ещё не перевели нормально на русский язык, и я читал её на английском, да и упражнения делал тоже на нем и это отлично заходило. Я также разработал андроид приложение, чтобы делать эти упражнения на смартфоне и трекать их. У меня было 3 мощных КПТ серии по несколько месяцев (конец 2018, начало 2019 и конец 2019). К концу 2019 мне удалось научиться жить даже лучше, чем мои здоровые знакомые. Я измерял их индекс Депресси и мой, который был опущен до нуля на коротком промежутке времени. Правда, если их не делать, то он обычно возвращается на уровень лёгкой депрессии, но все равно эти упражнения оставляют мощный отпечаток в сознании и в некоторых аспектах «переключают» работу мозга.

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

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

В 2018 году одна знакомая (которую я впоследствии обратил в КПТ) тоже имела проблемы с настроением и активно рекомендовала мне психоаналитика, который «хороший», «милый», «опытный» и «эмпатичный», а ещё за прием берёт 4000 руб в час. Я ещё тогда знал про КПТ, но решил сходить на прием. На приеме я описал мои проблемы и сказал, что слышал про научный подход и измерения, про доминирование КПТ в западной медицине. Я сказал ему, что хочу, чтобы он меня анализировал по канонам психоанализа (или психодинамики), и что я буду проверять все концепции и идеи, которые он выдвигает, читая литературу на английском языке. И тут он начал давать заднюю. Это была моя первая и последняя психоаналитическая сессия.

Ситуация с КПТ в СПБ

Клиника скандинавия, одна из самых крупных многопрофильных клиник СПБ, ставит КПТ на первое место. Да, порядок имеет значение.

А теперь посмотрим, что предлагает нам клиника Майо (Mayo Clinic) — один из крупнейших частных медицинских и исследовательских центров мира (находится в США).

Первые три вида психотерапии — это подвиды КПТ (CBT, DBT и ACT). Т.е. КПТ настолько популярно, что даже его подвиды упомянуты, как отдельные направления!

Тут надо отметить, что обе клиники поступают довольно «хитро», с целью не упустить прибыль с психоанализа, но при этом не навязывать неэффективные подходы. Поэтому, они упоминают психоанализ после КПТ, ведь врач-психоаналитик в клинике в случае обнаружения у пациентов серьезных проблем направит его в КПТ. А если проблемы не серьезные и пациент хочет психоанализ потому, что видел его в сериалах и фильмах много а ещё подруге помогло, то пускай приносит прибыль клинике. Очень тонкая медицинская манипуляция такая, и волки сыты и овцы целы. Но, опять же, если вы почитаете специализированную медицинскую литературу по конкретным проблемам (Депрессия, Тревога), то отсылок к психоанализу НЕ БУДЕТ. Я ещё читал книгу по сезонной депрессии от доктора Розенталя, там психоанализ вообще не рекомендуется, а про КПТ целая глава.

Один из оплотов КПТ в Санкт-Петербурге — это центр beCBT. Я задавал вопросы Алисе Ковпак (Она и Дмитрий Ковпак являются основателями центра и придерживаются западных канонов, проходили обучение у Бека в США). Вот что она ответила про психоанализ в России:

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

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

Откуда корни

Я долго пытался выяснить, почему же психоанализ так популярен. Один знакомый сказал, что его родители — ярые сторонники психоанализа, потому что на социологическом факультете СПБГУ в 90-е годы психоанализ преподавался как предмет (может и сейчас он есть), его внедрили в образовательную программу. В СПБ есть даже целый институт психоанализа (угадайте, в каком году он основан). Я могу простить нашему образованию многое. Я могу простить устаревание программы на IT-специальностях. НО, нельзя простить чиновников, которые за деньги (скорее всего) пропихнули в ТОП-вузы устаревшую школу психологии, которая не базируется на исследованиях (в нормальных странах её бы отсекли по этой причине) и используется в частной клинической практике для выкачивания денег.

Я полагаю, что в 90-е годы (да и сейчас) психоанализ был очень удобен по трем причинам:

1. Психоанализ предполагает много сессий и отсутствие гарантии результата, а также отсутствие ответственности. Население России верило в гадалок и заряжало воду по телевизору в то время, и очень хорошо подходило для окучивания
2. Само слово «психоанализ» созвучно со словом «матанализ» и кажется, что это некоторый систематизированный подход к изучению сознания человека, по аналогии с математикой, которую используют для описания явлений в науке и довольно успешно
3. Приход «всего» западного заключался в основном в развлекательном контенте, в котором много отсылок к психоанализу из-за его мементичности. А вот годные подходы из западной медицины приходят намного медленнее
4. Развал и разруха в медицине. Средний россиянин не доверяет среднему врачу (и вполне обоснованно). По своему опыту, я даже в современной медицине в СПБ видел огромное количество косяков (включая очень грубые косяки, про них отдельные статьи будут). Врач в РФ — не авторитет для россиянина. Если он направит на КПТ, россиянин все равно может пойти к психоаналитику

Хотя, это мои догадки. Если среди читателей будут те, кто работал в этой сфере в 90-е, пусть более подробно раскроют эту тему.

Как изучать КПТ

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

На Хабре очень популярна тема искусственного интеллекта, и у читателя может возникнуть вопрос — а существует ли бот-психотерапевт? Конечно, есть работающие прототипы, но они крайне низкого качества. В лучшем случае, они измеряют только индекс Бека и дают методику трех колонок (ABC модель), а все остальное — это обучающие видео по медитационным практикам, которые могут дополнять, но не заменять КПТ. Я общался с WoeBot и Wysa в течении недели, и был не удовлетворен. Кажется, что они дают в лучшем случае 20% от книги Дэвида, хотя можно было бы сделать крутую кастомизацию по главам и намного больше КПТ упражнений и различных тестов-измерений-графиков, вместо говновидосиков.

Если у вас есть интересные и захватывающие истории из личного опыта, затрагивающие тему КПТ или Психоанализа, можете прислать их на jandorwizard@gmail.com.

Let's block ads! (Why?)

Интерактивная визуализация алгоритмов на базе Jupyter

Jupyter уже давно зарекомендовал себя как удобную платформу для работы в различных областях на стыке программирования, анализа данных, машинного обучения, математики и других. Вот например очень известная книга по анализу данных, состоящая из Jupyter блокнотов. Поддержка $$, markdown, html дает возможность использовать использовать Jupyter в качестве платформы для удобного оформления научного-технического материала. Преимущество таких блокнотов заключается в интерактивности, возможности сопровождать сухой материал примерами программ, при этом эта интерактивность очень естественна и проста в использовании. В этой статье хотелось бы рассказать про возможность создания в Jupyter анимированных примеров работы различных алгоритмов и привести несколько из них с исходным кодом. В качестве кликбейта алгоритм Дейкстры.

Предисловие

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

Чем анимируем

Под Jupyter есть набор виджетов (ipywidgets), которые представляю собой различного рода инструменты управления, взаимодействуя с модулем IPython.display предоставляют интерактивную визуализацию. Следующий код представляет все ключевое взаимодействие с виджетами, с помощью которого можно сделать интерактивную анимацию на содержимом списка:

from ipywidgets import interact, interactive, fixed, interact_manual
import ipywidgets as widgets
from IPython.display import display


def step_slice(lst, step):
    return lst[step]


def animate_list(lst, play=False, interval=200):
    slider = widgets.IntSlider(min=0, max=len(lst) - 1, step=1, value=0)
    if play:
        play_widjet = widgets.Play(interval=interval)
        widgets.jslink((play_widjet, 'value'), (slider, 'value'))
        display(play_widjet)
        # slider = widgets.Box([play_widject, slider])
    return interact(step_slice,
                    lst=fixed(lst),
                    step=slider)

Вот что получится, если подать функции animate_list список из целых чисел:

a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
animate_list(a, play=True, interval=200);

Чтобы продемонстрировать работу какого-либо алгоритма с помощью animate_list нужно сгенерировать промежуточные состояния алгоритма и сохранить их визуальное представление в нужном формате.

Тектовые анимации

Базовые алгоритмы для работы с последовательностями/массивами достаточно текстового представления. У меня к сожалению были проблемы с базовыми строками, которые отказывались обрабатывать перевод строки, в результате я использовал IPython.display.Code. Начнем с классической быстрой сортировки.

Код

from IPython.display import Code
import random

def qsort_state(array, left, right, x, p, q):
    extended_array = list(map(str, array[:left])) + ['['] + list(map(str, array[left: right])) + [']'] + list(map(str, array[right:]))
    offset_x = sum(list(map(len, extended_array[:left]))) + left + 2
    zero_line = ''.join([' ' for i in range(offset_x)]) + f'x = {x}'
    first_line = ' '.join(extended_array)
    offset_p = sum(list(map(len, extended_array[:p + 1]))) + p + 1 + len(extended_array[p + 1]) // 2
    offset_q = sum(list(map(len, extended_array[:q + 1]))) + q + 1 + len(extended_array[q + 1]) // 2
    second_line = ''.join([' ' if i != offset_p and i != offset_q else '↑' for i in range(len(first_line))])

    return Code(zero_line + '\n' + first_line + '\n' + second_line)

def qsort(array, left, right, states):
    if right - left <= 1:
        return
    x = array[random.randint(left, right - 1)]
    p = left
    q = right - 1
    states.append(qsort_state(array, left, right, x, p, q))
    while p <= q:
        while array[p] < x:
            p += 1
            states.append(qsort_state(array, left, right, x, p, q))
        while array[q] > x:
            q -= 1
            states.append(qsort_state(array, left, right, x, p, q))
        if p <= q:
            array[p], array[q] = (array[q], array[p])
            states.append(qsort_state(array, left, right, x, p, q))
            p += 1
            q -= 1
            if p <= q:
                states.append(qsort_state(array, left, right, x, p, q))
    qsort(array, left, q + 1, states)
    qsort(array, p, right, states)  

a = [234, 1, 42, 3, 15, 3, 10, 9, 2]
states = []
qsort(a, 0, len(a), states)
animate_list(states, play=True);

Результат

Похожим образом можно визуализировать и бинарный поиск

Код

def bs_state(array, left, right, x):
    extended_array = list(map(str, array[:left])) + ['['] + list(map(str, array[left: right])) + [']'] + list(map(str, array[right:])) 
    mid = (left + right) // 2
    offset_x = sum(list(map(len, extended_array[:mid + 1]))) + mid + 1
    return Code(' '.join(extended_array) + '\n' + ''.join([' ' for i in range(offset_x)]) + str(x))

# Эта версия бинарного поиска находит последний элемент, который
# меньше или равен искомого
states = []
left = 0
right = len(a)
x = 14
while right - left > 1:
    states.append(bs_state(a, left, right, x))
    mid = (left + right) // 2
    if a[mid] <= x:
        left = mid
    else:
        right = mid
states.append(bs_state(a, left, right, x))

animate_list(states, play=True, interval=400);

Результат

А вот пример для строк: процесс построения префикс-функции:

Код

def prefix_function_state(s, p, k, intermidiate=False):
    third_string = ''.join([s[i] if i < k else ' ' for i in range(len(p))])
    fourth_string = ''.join([s[i] if i >= len(p) - k else ' ' for i in range(len(p))])
    return Code(s + '\n' + ''.join(list(map(str, (p + ['*'] if intermidiate else p )))) \
                  + '\n' + third_string + '\n' + fourth_string)

def prefix_function(s, states):
    p = [0]
    k = 0
    states.append(prefix_function_state(s, p, k))
    for letter in s[1:]:
        states.append(prefix_function_state(s, p, k, True))
        while k > 0 and s[k] != letter:
            k = p[k - 1]
            states.append(prefix_function_state(s, p, k, True))
        if s[k] == letter:
            k += 1
        p.append(k)
        states.append(prefix_function_state(s, p, k))
    return p

states = []
p = prefix_function('ababadababa', states)
animate_list(states, play=True);

Результат

Визуализация с использованием Matplotlib

Matplotlib — библиотека Python для отрисовки различных графиков. Вот несколько примеров как можно её использовать для визуализации алгоритмов. Начнем с примера итеративных алгоритмов поиска минимума функции, наиболее простым из которых является метод случайного локального поиска, которые делает локальное изменение текущего приближения и переходит в него если значение значение функции в новой точки оказалось лучше:

Код

import numpy as np
import matplotlib.pyplot as plt

# Функция, которую минимизируем, минимум в точке (0, 0)
def f(x, y):
    return 1.3 * (x - y) ** 2 + 0.7 * (x + y) ** 2

# Отрисовка траектории и линий уровня функции
def plot_trajectory(func, traj, limit_point=None):
    fig = plt.figure(figsize=(7, 7))
    ax = fig.add_axes([0, 0, 1, 1])    
    
    if limit_point:
        ax.plot([limit_point[0]], [limit_point[1]], 'o', color='green')
    #Level contours
    delta = 0.025
    x = np.arange(-2, 2, delta)
    y = np.arange(-2, 2, delta)
    X, Y = np.meshgrid(x, y)
    Z = np.zeros_like(X)
    for i in range(X.shape[0]):
        for j in range(X.shape[1]):
            Z[i][j] = func(X[i][j], Y[i][j])
    CS = ax.contour(X, Y, Z, [0.5, 1.5, 3], colors=['blue', 'purple', 'red'])
    ax.plot([u[0] for u in traj], [u[1] for u in traj], color='black')
    ax.plot([u[0] for u in traj], [u[1] for u in traj], 'o', color='black')
    
    plt.close(fig)
    return fig

x, y = (1.0, 1.0)
num_iters = 50
trajectory = [(x, y)]
plots = []
# Итерируемся и сохраняем текущий путь на каждом шаге
for i in range(num_iters):
    angle = 2 * np.pi * np.random.rand(1)
    dx, dy = (np.cos(angle) / 2 / (i + 1) ** 0.5, np.sin(angle) / 2 / (i + 1) ** 0.5)
    trajectory.append((x + dx, y + dy))
    plots.append(plot_trajectory(f, trajectory, limit_point=(0, 0)))
    if f(x, y) > f(x + dx, y + dy):
        x = x + dx
        y = y + dy
    else:
        trajectory = trajectory[:-1]

animate_list(plots, play=True, interval=300);

Результат

А вот пример ЕМ алгоритма для данных извержений Old Faithful гейзера, такой же пример приведен на википедии:

Код

# Данные можно взять например здесь
# http://www.stat.cmu.edu/~larry/all-of-statistics/=data/faithful.dat
data = []
with open('data/faithful.csv') as f:
    for line in f:
        _, x, y = line.split(',')
        try:
            data.append((float(x), float(y)))
        except ValueError:
            pass

colors = ['red', 'blue', 'yellow', 'green']

# За основу взято https://jakevdp.github.io/PythonDataScienceHandbook/05.12-gaussian-mixtures.html
from matplotlib.patches import Ellipse

def draw_ellipse(position, covariance, ax=None, **kwargs):
    """Draw an ellipse with a given position and covariance"""
    ax = ax or plt.gca()
    
    # Convert covariance to principal axes
    if covariance.shape == (2, 2):
        U, s, Vt = np.linalg.svd(covariance)
        angle = np.degrees(np.arctan2(U[1, 0], U[0, 0]))
        width, height = 2 * np.sqrt(s)
    else:
        angle = 0
        width, height = 2 * np.sqrt(covariance)
    
    # Draw the Ellipse
    for nsig in range(1, 4):
        ax.add_patch(Ellipse(position, nsig * width, nsig * height,
                             angle, color='red', **kwargs))
        
def plot_gmm(gmm, X, label=True, ax=None):
    ax = ax or plt.gca()
    if label:
        labels = gmm.predict(X)
        ax.scatter(X[:, 0], X[:, 1], c=labels, s=20, cmap='plasma', zorder=2)
    else:
        ax.scatter(X[:, 0], X[:, 1], s=20, zorder=2)
    
    w_factor = 0.2 / gmm.weights_.max()
    for pos, covar, w in zip(gmm.means_, gmm.covariances_, gmm.weights_):
        draw_ellipse(pos, covar, alpha=w * w_factor)
        
def step_figure(gmm, X, label=True):
    fig = plt.figure(figsize=(7, 7))
    ax = fig.add_axes([0, 0, 1, 1])
    ax.set_ylim(30, 100)
    ax.set_xlim(1, 6)
    plot_gmm(gmm, X, label=True, ax=ax)
    plt.close(fig)
    return fig

from sklearn.mixture import GaussianMixture

x = np.array(data)
# max_iters=1 и warm_start=True заставляют gmm.fit делать ровно одну итерацию
# и сохранять состояние
gmm = GaussianMixture(2, warm_start=True, init_params='random', max_iter=1)
# GMM выдает предупреждения на то, что одной итерации мало
import warnings 
warnings.simplefilter('ignore')
# Инициализируем на небольшой порции данных
gmm.fit(x[:10,:])
steps = [step_figure(gmm, x)]   
for i in range(17):
    gmm.fit(x)
    steps.append(step_figure(gmm, x))

animate_list(steps, play=True, interval=400);

Результат

Следующий пример скорее игрушечный, но тоже показывает, что можно сделать в matplotlib: визуализация замощения клетчатой фигуры на плоскости максимальным числом доминошек с помощью нахождения максимального паросочетания:

Код

# Обертка над matplotlib для отрисовки прямоугольника, разделенного на квадраты разных цветов
from animation_utils.matplotlib import draw_filling

def check_valid(i, j, n, m, tiling):
    return 0 <= i and i < n and 0 <= j and j < m and tiling[i][j] != '#'

def find_augmenting_path(x, y, n, m, visited, matched, tiling):
    if not check_valid(x, y, n, m, tiling):
        return False
    if (x, y) in visited:
        return False
    visited.add((x, y))
    
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if not check_valid(x + dx, y + dy, n, m, tiling):
            continue
        if (x + dx, y + dy) not in matched or find_augmenting_path(*matched[(x + dx , y + dy)], n, m, visited, matched, tiling):
            matched[(x + dx, y + dy)] = (x, y)
            return True
    return False

def convert_match(matched, tiling, n, m):
    result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]
    num = 0
    for x, y in matched:
        _x, _y = matched[(x, y)]
        result[x][y] = num
        result[_x][_y] = num
        num += 1
    return result

def match_with_flow(tiling):
    result_slices = []
    n = len(tiling)
    m = len(tiling[0])
    
    matched = dict()
    # Для наглядности визуализации
    rows = list(range(n))
    columns = list(range(m))
    random.shuffle(rows)
    random.shuffle(columns)
    result_slices.append(convert_match(matched, tiling, n, m))
            
    for i in rows:
        for j in columns:
            if (i + j) % 2 == 1:
                continue
            visited = set()
            if find_augmenting_path(i, j, n, m, visited, matched, tiling):
                result_slices.append(convert_match(matched, tiling, n, m))
            
    return result_slices

tiling_custom=[
    '...####',
    '....###',
    '......#',
    '#.#....',
    '#......',
    '##.....',
    '###...#',
]
sequencial_match = match_with_flow(tiling_custom)
animate_list(list(map(draw_filling, sequencial_match)), play=True);

Результат

Ну и попутно демонстрация алгоритма раскраски планарного графа в 5 цветов, чтобы визуально разбиение смотрелось лучше:

Код

def color_5(filling):
    result = [[i for i in row] for row in filling]
    # Строим граф
    domino_tiles = [[] for i in range(max(map(max, filling)) + 1)]
    domino_neighbours = [set() for i in range(max(map(max, filling)) + 1)]
    degree = [0 for i in range(max(map(max, filling)) + 1)]
    
    n = len(filling)
    m = len(filling[0])
    
    for i, row in enumerate(filling):
        for j, num in enumerate(row):
            if num >= 0:
                domino_tiles[num].append((i, j))
                
    for i, tiles in enumerate(domino_tiles):
        for x, y in tiles:
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
                a, b = x + dx, y + dy
                if 0 <= a and a < n and 0 <= b and b < m and filling[a][b] >= 0 and filling[a][b] != i \
                        and filling[a][b] not in domino_neighbours[i]:
                    domino_neighbours[i].add(filling[a][b])
                    degree[i] += 1
    
    # Первым делом нужно найти такой порядок вершин, все вершины имели не больше 5 соседей среди
    # предыдущих. Такой существует в силу того, что граф планарный, а найти его эффективнее всего
    # по очереди находя вершину наименьшей степени и удаляя её из графа, так мы получаем обратный порядок
    active_degrees = [set() for i in range(max(degree) + 1)]
    for i, deg in enumerate(degree):
        active_degrees[deg].add(i)
    
    reversed_order = []
    
    for step in range(len(domino_tiles)):
        min_degree = min([i for i, dominoes in enumerate(active_degrees) if len(dominoes) > 0])
        domino = active_degrees[min_degree].pop()
        
        reversed_order.append(domino)
        for other in domino_neighbours[domino]:
            if other in active_degrees[degree[other]]:
                active_degrees[degree[other]].remove(other)
                degree[other] -= 1
                active_degrees[degree[other]].add(other)                
        
    # Теперь перебираем в обратном порядке и либо красим в еще не занятый цвет,
    # если есть свободный из 5 цветов, иначе находим цепочку из чередующихся цветов,
    # которые могут быть перекрашены. Такая найдется в силу планарности
    colors = [-1 for domino in domino_tiles]
    slices = [draw_filling(result)]
    for domino in reversed(reversed_order):
        used_colors = [colors[other] for other in domino_neighbours[domino] if colors[other] != -1]
        
        domino_color = len(used_colors)
        for i, color in enumerate(sorted(set(used_colors))):
            if i != color:
                domino_color = i
                break
     
        if domino_color < 5:
            colors[domino] = domino_color
            for x, y in domino_tiles[domino]:
                result[x][y] = domino_color
                
            slices.append(draw_filling(result))        
            continue
           
        # Начиная отсюда код я не тестировал, не нашел примера        
        c = 0
        other = [other for other in domino_neighbours[domino] if colors[other] == c]
        visited = set([other])
        q = Queue()
        q.put(other)
        domino_was_reached = False
        while not q.empty():
            cur = q.get()
            for other in domino_neighbours[cur]:
                if other == domino:
                    domino_was_reached = True
                    break
                if color[other] == c or color[other] == c + 1 and other not in visited:
                    visited.add(other)
                    q.put(other)
                    
        if not domino_was_reached:
            for other in visited:
                color[other] = color[other] ^ 1
                for x, y in domino_tiles[other]:
                    result[x][y] = color[other]
            color[domino] = c
            for x, y in domino_tiles[domino]:
                result[x][y] = c
                
            slices.append(draw_filling(result))
            continue
            
        # Проделываем тоже самое для 2 и 3.
        c = 2
        other = [other for other in domino_neighbours[domino] if colors[other] == c]
        visited = set([other])
        q = Queue()
        q.put(other)
        domino_was_reached = False
        while not q.empty():
            cur = q.get()
            for other in domino_neighbours[cur]:
                if other == domino:
                    domino_was_reached = True
                    break
                if color[other] == c or color[other] == c + 1 and other not in visited:
                    visited.add(other)
                    q.put(other)
        for other in visited:
            color[other] = color[other] ^ 1
            for x, y in domino_tiles[other]:
                result[x][y] = color[other]
        color[domino] = c
        for x, y in domino_tiles[domino]:
            result[x][y] = c
        slices.append(draw_filling(result))
                    
    return result, slices

filling_colored, slices =color_5(sequencial_match[-1])
animate_list(slices, play=True);

Результат

Последний пример с matplotlib из вычислительной геометрии — алгоритм Грэхэма-Эндрю для построения выпуклой оболочки на плоскости:

Код

def convex_hull_state(points, lower_path, upper_path):
    fig = plt.figure(figsize=(6, 6))
    ax = fig.add_axes([0, 0, 1, 1])
    
    ax.get_xaxis().set_visible(False)
    ax.get_yaxis().set_visible(False)

    for name, spine in ax.spines.items():
        spine.set_visible(False)
        spine.set_visible(False)
    
    ax.scatter([x for x, y in points], [y for x, y in points])
    ax.plot([x for x, _ in lower_path], [y for _, y in lower_path], color='red')
    ax.plot([x for x, _ in upper_path], [y for _, y in upper_path], color='blue')
    
    plt.close(fig)
    return fig

def vector_prod(point_a, point_b):
    return point_a[0] *  point_b[1] - point_a[1] * point_b[0]

def convex_hull(poitns):
    sorted_points = sorted(points, key=lambda x: x[1])
    sorted_points = sorted(sorted_points, key=lambda x: x[0])
    states = []
    
    upper_path = [sorted_points[0]]
    lower_path = [sorted_points[0]]
    states.append(convex_hull_state(points, lower_path, upper_path))
    
    for point in sorted_points[1:]:
        while len(upper_path) > 1 and vector_prod(point - upper_path[-1], upper_path[-1] - upper_path[-2]) > 0:
            upper_path = upper_path[:-1]
            upper_path.append(point)
            states.append(convex_hull_state(poitns, lower_path, upper_path))
            upper_path = upper_path[:-1]
        upper_path.append(point)
        states.append(convex_hull_state(points, lower_path, upper_path))
        
    for point in sorted_points[1:]:
        while len(lower_path) > 1 and vector_prod(point - lower_path[-1], lower_path[-1] - lower_path[-2]) < 0:
            lower_path = lower_path[:-1]
            lower_path.append(point)
            states.append(convex_hull_state(poitns, lower_path, upper_path))
            lower_path = lower_path[:-1]
        lower_path.append(point)
        states.append(convex_hull_state(poitns, lower_path, upper_path))
    
    return states

points = [np.random.rand(2) for i in range(20)]
states = convex_hull(points)
animate_list(states, play=True, interval=300);

Результат

Последнее, что хотелось бы отметить в контексте matplotlib — это альтернативный способ создания анимаций через matplotlib.animation.FuncAnimation. У этого способа есть свои плюсы: его можно конвертировать в html с помощью IPython.display.HTML, результат будет более надежным, чем на виджетах (у меня виджеты периодически торомозят), не будет требовать рабочего ядра Jupyter, но в этом случае анимация стоновится обычным видео и средства управления ограничены проигрывателем.

Graphviz

С помощью graphviz можно отрисовывать графы. Обратите внимание, что для воспроизведения примеров с его помощью необходимо будет установить graphviz не только в python, но и в систему. Начнем с обхода в глубину:

Код

# Обертка для упрощения работы с графами
from graph_utils.graph import Graph, Arc, Node

def enter_node(node):
    node.SetColor('blue')
    
def enter_arc(node, arc):
    node.SetColor('green')
    arc.attributes['style'] = 'dashed'
    arc.attributes['color'] = 'green'
    
def return_from_arc(node, arc):
    arc.attributes['style'] = 'solid'
    arc.attributes['color'] = 'red'
    node.SetColor('blue')
    
def ignore_arc(arc):
    arc.attributes['color'] = 'blue'
    
def leave_node(node):
    node.SetColor('red')
    
def dfs(graph, node_id, visited, outlist, path):
    visited.add(node_id)
    path.append(node_id)
    enter_node(graph.nodes[node_id])
    outlist.append(graph.Visualize())
    for arc in graph.nodes[node_id].arcs:
        if arc.end not in visited:
            enter_arc(graph.nodes[node_id], arc)
            dfs(graph, arc.end, visited, outlist, path) 
            return_from_arc(graph.nodes[node_id], arc)
            path.append(node_id)
        else:
            ignore_arc(arc)
        outlist.append(graph.Visualize())      
    leave_node(graph.nodes[node_id])

arcs = [
    Arc(1, 3, 3),
    Arc(1, 4, 7),
    Arc(4, 3, 2),
    Arc(4, 5, 3),
    Arc(1, 5, 2),
    Arc(6, 4, 2),
    Arc(5, 6, 2),
    Arc(6, 7, 1),
    Arc(7, 2, 7),
    Arc(4, 2, 2),
    Arc(3, 2, 5)
]

# Если следующий код выдает ошибку, что ему не удается выполнить `dot`, то
# скорее всего придется отдельно поставить graphviz
# https://graphviz.org/download/
graph = Graph(arcs)
visited = set()
dfs_outlist = []
path = []
dfs_outlist.append(graph.Visualize())
dfs(graph, 1, visited, dfs_outlist, path)
dfs_outlist.append(graph.Visualize())
animate_list(dfs_outlist, play=True, interval=400);

Результат

Ну а вот и алгоритм Дейкстры из заголовка

Код

def mark_labelled(node):
    node.SetColor('red')
    
def mark_scanned(node):
    node.SetColor('green')
    
def process_node(node):
    node.SetColor('blue')
    
def set_previous(arc):
    arc.SetColor('green')
    
def unset_previous(arc):
    arc.SetColor('black')

def scan_arc(graph, arc, l, p, mark):
    if l[arc.end] > l[arc.beginning] + arc.weight:
        l[arc.end] = l[arc.beginning] + arc.weight
        if p[arc.end] is not None:
            unset_previous(p[arc.end])
        # Сохраняем arc, а не arc.beginning, чтобы было больше информации
        p[arc.end] = arc
        set_previous(p[arc.end])
        mark[arc.end] = True
        mark_labelled(graph.nodes[arc.end])

def scan_node(graph, node_id, l, p, mark):
    for arc in graph.nodes[node_id].arcs:
        scan_arc(graph, arc, l, p, mark)
    mark[node_id] = False
    mark_scanned(graph.nodes[node_id])
     
        
# Это не традиционная реализация алгоритма Дейкстры, а реализация
# сканирующего метода, подробности смотрите тут
# http://forskning.diku.dk/PATH05/GoldbergSlides.pdf
def base_scanning_method(graph, s, choice_function):
    l    = {key: float('Inf') for key in graph.nodes.keys()}
    p    = {key: None for key in graph.nodes.keys()}
    mark = {key: False for key in graph.nodes.keys()}
    
    l[s] = 0
    mark[s] = True
    mark_labelled(graph.nodes[s])
    
    out_lst = []
    
    while True:
        node_id = choice_function(l, mark)
        if node_id is None:
            break
        process_node(graph.nodes[node_id])
        out_lst.append(graph.Visualize(l))
        scan_node(graph, node_id, l, p, mark)
        out_lst.append(graph.Visualize(l))
    return l, p, out_lst

# Функция выбора в алгоритме Дейкстры
def least_distance_choice(l, mark):
    labelled = [node_id for node_id, value in mark.items() if value == True]
    if len(labelled) == 0:
        return None
    return min(labelled, key=lambda x: l[x]) 

graph = Graph(arcs)
l, p, bfs_shortest_path_lst = \
    base_scanning_method(graph, 1, least_distance_choice)
animate_list(bfs_shortest_path_lst, play=True, interval=400);

Результат

А вот таким образом происходит построение префиксного дерева для слов 'мама', 'мать', 'мартышка', 'мыла', 'молоко':

Код

class TrieNode:
    def __init__(self, parent, word=None):
        # Хранение этого поля очень расточительно, используется исключительно
        # для демонстрации ленивого подсчета суффиксных ссылок
        self.parent = parent
        # Здесь аналогично, это поле чаще всего избыточно
        self.word = word
        self.children = {}
        self.suff_link = None

def init_trie():
    trie = [TrieNode(-1)]
    return trie

def to_graph(trie):
    arcs = []
    for i, node in enumerate(trie):
        for c, nextstate in node.children.items():
            arcs.append(Arc(i, nextstate, c))
        if node.suff_link is not None and node.suff_link != 0:
            arcs.append(Arc(i, 
                            node.suff_link, 
                            attributes={"constraint" : "False", "style" : "dashed"}))
            
    return Graph(arcs)

def add_word(trie, word, steps):
    _num = 0
    for ch in word:
        if not ch in trie[_num].children:
            _n = len(trie)
            trie[_num].children[ch] = _n
            trie.append(TrieNode((_num, ch)))
        _num = trie[_num].children[ch]
        graph = to_graph(trie)
        graph.nodes[_num].SetColor('red')
        steps.append(graph.Visualize())
    trie[_num].word = word
    
def make_trie(words):
    steps = []
    trie = init_trie()
    steps.append(to_graph(trie).Visualize())
    for word in words:
        add_word(trie, word, steps)
        steps.append(to_graph(trie).Visualize())
    return trie, steps

words = [
    'мама',
    'мать',
    'мартышка',
    'мыла',
    'молоко'
]
trie, steps = make_trie(words)
animate_list(steps, play=True, interval=500);

Результат

Ну и напоследок алгоритм Куна для нахождения максимального паросочетания:

Код

def mark_for_delete(arc):
    arc.SetColor('red')
    arc.SetStyle('dashed')
    
def mark_for_add(arc):
    arc.SetColor('blue')
    
def clear(arc):
    arc.SetColor('black')
    arc.SetStyle('solid')
        
def find_augmenting_path(graph, node_id, visited, match, deleted):
    if node_id in visited:
        return False
    visited.add(node_id)
    for arc in graph.nodes[node_id].arcs:
        if arc.end not in match or find_augmenting_path(graph, match[arc.end].beginning, visited, match, deleted):
            if arc.end in match:
                mark_for_delete(match[arc.end])
                deleted.append(match[arc.end])
            match[arc.end] = arc
            mark_for_add(arc)
            return True
    return False

def kuhns_matching(graph, first_part):
    states = [graph.Visualize()]
    match = dict()
    for node_id in first_part:
        node = graph.nodes[node_id]
        node.SetColor('Blue')
        states.append(graph.Visualize())
        deleted = []
        if find_augmenting_path(graph, node_id, set(), match, deleted):
            states.append(graph.Visualize())
            for arc in deleted:
                clear(arc)
            states.append(graph.Visualize())
        node.SetColor('red')
    states.append(graph.Visualize())
    return states

arcs = [
    Arc(1, 6),
    Arc(1, 7),
    Arc(2, 6),
    Arc(3, 7),
    Arc(3, 8),
    Arc(4, 8),
    Arc(4, 9),
    Arc(4, 10),
    Arc(5, 10),
    Arc(2, 8)
]
first_part = [1, 2, 3, 4, 5]
graph = Graph(arcs)
states = kuhns_matching(graph, first_part)

animate_list(states, play=True, interval=400);

Результат

Алгоритмы с матрицами

А вот эта часть относится к неудавшейся попытке. IPython.display умеет парсить latex, однако при попытки его использовать вот что у меня получилось (должен был быть метод Гаусса):

Код

from animation_utils.latex import Matrix
from IPython.display import Math

n = 5
A = np.random.rand(n, n)
L = np.identity(n)
U = np.array(A)
steps = []
steps.append(Math(str(Matrix(L)) + str(Matrix(U))))
for k in range(n):
    x = U[k,k]
    for i in range(k+1, n):
        L[i,k] = U[i,k] / x
        U[i,k:] -= L[i,k] * U[k,k:]
    steps.append(Math(str(Matrix(L)) + str(Matrix(U))))

animate_list(steps, play=True, interval=500);

Результат

Пока я не знаю, что с этим делать, но возможно знающие люди подскажут.

Let's block ads! (Why?)

Как оценить и выбрать оффер разработчику: на что смотреть, к чему готовиться, какие вопросы задавать

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

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

Этап #1: узнаем себе цену и определяемся с пожеланиями

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

Этот подход подходит для вакансий на родине или с релокейтом, в случае удаленной работы на зарубежную компанию, есть свои нюансы. В общем и целом решить эту задачу помогают аналитические материалы. Данные по зарплатам российских айтишников можно найти на ресурсах вроде Levels. К примеру, по информации этого сервиса большинство зарплат разработчиков в нашей стране находятся в промежутке между 1,69 — 3,69 млн рублей в год (140,8 — 307,5к в месяц)

Если вы задумываетесь о переезде в другую страну, то стоит изучить самые свежие отчеты по зарплатам в нужном регионе. Конечно же, стоит обратить внимание на исследования порталов вроде StackOverflow, там можно получить данные по США и некоторым другим странам.

К примеру, в исследовании за 2020 год собраны данные о самых «прибыльных» технологиях, а также дана корреляция между зарплатой и опытом в определенной специальности:

Также для анализа возможной зарплаты можно использовать нашего бота @g_jobbot. После того, как вы внесли в него информацию о своем опыте, он начнет присылать подходящие для вас вакансии прямо в Telegram. Соответственно, по количеству вакансий можно понять, насколько релевантны ваши рыночные запросы. Возможно, ваша зарплата уже устарела – так было у героя одной из наших статей. Инженер зарабатывал на 60% меньше, чем мог бы, и узнал об этом только воспользовавшись ботом.

Еще один важный этап подготовки – определиться с интересными технологиями и траекторией карьеры. Хотите вы расти вертикально или горизонтально? Развивать знания в рамках текущего стека или попробовать его сменить? Все это важные вопросы, ответы на которых серьезно повлияют на оценку будущих офферов.

Для сравнения, вот, как ранжировали разные факторы по их влиянию на выбор работы опрошенные StackOverflow разработчики:

Этап 2: сбор информации о компании

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

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

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

Еще один важный момент, который может помочь подготовиться к следующему шагу обсуждения оффера – постарайтесь узнать, сколько компания обычно платит. Сделать это не так просто, но и никакого rocket science тут нет. Достаточно лишь просто найти в LinkedIn или среди знакомых кого-то, кто уже там работает или работал недавно в похожей должности.

Конечно же, не стоит в лоб спрашивать «сколько тебе платили?» Это некорректно и может поставить собеседника в неловкую ситуацию. Гораздо лучше спросить: «Как ты думаешь, вот такая вилка – это похоже на то, что там платят при таком наборе навыков? И если нет, то что звучит более реалистично?» От полученной цифры можно уже будет отталкиваться на следующем этапе.

Этап 3: переговоры

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

Статистика g-mate по локациям найма: сегодня кандидатам во всех категориях ИТ-специализаций больше всего интересны варианты с релокейтом

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

Итак, вот на какие аспекты будущей работы стоит обратить внимание в ходе обсуждений:

Как будет выглядеть онбординг и есть ли он

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

Каков подход к work-life balance

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

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

Что с премиями

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

Какая финансовая мотивация помимо зарплаты есть в компании

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

Какие еще бонусы предоставляет компания

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

Полезные статьи о поиске работы и собеседованиях в ИТ:

Let's block ads! (Why?)

Илон Маск продемонстрировал Neuralink

Илон Маск, вооружившись поддержкой трех поросят продемонстрировал девайс и похвастался тем, что "Food and Drug Administration" дали "предварительное разрешение" на использование имплантата в медицинских целях. Устройство получило "Breakthrough Device designation" от FDA, это своего рода возможность общаться вплотную с органами сертификации на ранних этапах.

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

Третьего зовут Gertrude. Во время презентации можно было слышать звуки означающие фиксацию импульсов в мозгу.

Биканье, которое вы слышите — это real-time сигналы от Neuralink находящиеся в мозгу Gertrude.

На данный момент команда разработчиков планирует имплантировать устройство людям с параличом в попытке восстановить двигательные функции.

В Neuralink инвестировали более 150 миллионов, часть инвестиций от самого Илона Маска. На данный момент в компании работает 100 человек. Компания надеется на рост, возможно это будет 10 тысяч сотрудников или даже больше. По факту, демонстрация была устроена для привлечения новых сотрудников.

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

В будущем, система повзолит людям сохранять воспоминания и воспроизводить их как кино. Сохранять разум и закачивать его в роботов.

“This is obviously sounding increasingly like a ‘Black Mirror’ episode,” he said. “But, well, I guess they’re pretty good at predicting. … The future is going to be weird.”

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

BraineGate получил разрешение на испытания в клиниках.

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

Илон Маск определенно придает проекту уверености и вместе с тем загадочности. Один из слушателей спросил — возможно ли применение имплантата для управление автомобилем Tesla? И Илон Маск ответил — конечно!

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

Устройство будет работать как Fitbit в вашем мозгу. Специальный робот, всего лишь сделает дырку в вашей голове, размером с монету и установит там 1, 024 электрода. Размер проводка — 5 микрон. Робот будет делать это с максимальной осторожность, что бы не проткнуть чего лишнего.

Задача команды сократить время установки имплантата до часа, а установку проводить под местной анестезией. Пришел, просверлил дырку, поставил имплантат и в этот же день пошел домой под управлением джойстика от xbox.

Зарядки устройства будет хватать на день, а заряжать его можно будет ночью. Предполагаемая зарядка — беспроводная зарядка. Просто кладете свою голову вместо айфона. Я шучу, но технологически так и будет. Подключится к устройству можно будет по Bluetooth.

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

Стоить все это удовольствие будет не дешево, но со временем цена будет снижена за счет масштабов. Автоматизация процесса поможет этого достичь, речь идет об итоговой цене в несколько тысяч долларов. Это должно быть подобно lasik (операции на глазах). Электроника сама по себе не дорогая, она состоит из частей которые уже давно производят в крупных масштабах.

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

Пожалуй самое крутой в презентации — это предсказание. Словно кадры из сериала Devs:

Точки на свинке — предсказание и реальность расположение суставов на основе импульсов мозга который считывает имплантат.

Ещё

https://www.synchronmed.com/
https://techcrunch.com/2020/08/28/elon-musk-demonstrates-neuralinks-tech-live-using-pigs-with-surgically-implanted-brain-monitoring-devices/

Let's block ads! (Why?)

Как выручка ИТ-компаний Азии может пострадать от санкций США против Huawei

Согласно отчету аналитиков Standard and Poor’s, последний пакет санкций США против китайской корпорации Huawei может поставить под удар около $25 млрд долларов выручки технологических компаний в Азиатско-Тихоокеанском регионе.

Huawei – один из крупнейших производителей смартфонов в мире, и компания стала заложником торговой войны между США и Китаем. Как все это скажется на технологическом бизнесе в Азии?

Что случилось

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

Huawei нуждается в таких полупроводниках, чтобы производить свои смартфоны и телекоммуникационное оборудование. Конфронтация США и Китая ставит под угрозу около $25 млрд выручки технологических компаний в Азиатско-Тихоокеанском регионе, подсчитали аналитики S&P. К примеру, санкции могут стоить тайваньcкой Taiwan Semiconductor Manufacturing Co. до 20% выручки и до $7 млрд в деньгах – компания использует американское оборудование и по новому правилу вынуждена будет перед сделками с Huawei получать одобрение США.

Другие компании в регионе пострадают опосредованно – это те юрлица, что как-то связаны с компаниями, которых новый запрет США на работу с Huawei касаются напрямую. Потери такого бизнеса оценены в $18 млрд.

В чем претензии властей США

Ранее правительство США поместило Huawei в entity list – список компаний, с которым американским организациям запрещено вести дела без получения специального разрешения. Власти Америки убеждены, что деятельность китайского телеком-гиганта ставит под угрозу национальную безопасность и интересы США.

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

Все это позволило властям США призвать своих союзников к отказу от использования оборудования Huawei для построения мобильных сетей нового поколения 5G. При этом сама корпорация полностью отрицает обвинения в связях со спецслужбами Китая.

Не только Huawei

Власти США обсуждают ограничения не только в отношении Huawei. Так в стране продолжаются обсуждения новой инициативы – Holding Foreign Companies Accountable Act. Этот законопроект обязывает иностранные компании доказывать тот факт, что зарубежные правительства не владеют в них какой-либо долей. Если сделать это не удастся, или американские регуляторы не смогут провести аудит, наказанием может стать делистинг, то есть насильное снятие акций компании с торгов на биржах в США.

Аналитики считают, что главным образом законопроект направлен против китайских компаний, вроде Alibaba и Baidu.

Пока что акции китайских компаний Alibaba, Baidu и других торгуются на американских биржах без ограничений. А это значит, что купить их можно и из России можно без необходимости открывать отдельный брокерский счет у зарубежных брокеров. С помощью рынка иностранных ценных бумаг Санкт-Петербургской биржи инвесторы могут покупать 500 ликвидных акций ведущих компаний всех секторов мировой экономики, в том числе все акции индекса S&P 500.

Чтобы совершать операции с такими акциями, вам понадобится брокерский счет – открыть его можно онлайн.

Читайте обзоры, аналитику рынков и инвестидеи в Telegram-канале ITI Capital

Let's block ads! (Why?)

[Перевод] 7 расширений для VS Code, установив которые, вы не захотите выходить из редактора

…Даже простейшие инструменты могут давать людям возможность делать великие дела.
Биз Стоун, «Решайся! Заряд на создание великого от основателя Twitter»

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

Многие программисты используют в наши дни Visual Studio Code. Этот редактор кода поддерживает установку расширений. Существует столько подобных расширений, что можно говорить о том, что возможности настройки VS Code практически безграничны.

Но на Visual Studio Marketplace, на площадке, где публикуются расширения для VS Code, опубликовано просто невероятное количество расширений. А это значит, что программистам сложно находить именно то, что им действительно пригодится. Если некое расширение показалось кому-то полезным, то оно, вполне возможно, принесёт пользу и другим людям. Поэтому я расскажу здесь о 7 расширениях для VS Code, которые способны значительно облегчить работу программиста. Всё это — бесплатные расширения. Любой может свободно их загружать и использовать.

1. REST Client

Расширение REST Client позволяет, прямо из VS Code, отправлять HTTP-запросы, и тут же просматривать ответы на них. Это расширение позволяет попрощаться с внешними приложениями, которые иначе пришлось бы использовать для выполнения запросов к серверам.

Это расширение, учитывая то, что у него более миллиона загрузок, весьма популярно. Им пользуется множество программистов. Я уже довольно давно пользуюсь REST Client и полагаю, что это — замечательный инструмент.

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

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

Работа с REST Client

2. CSS Peek

Если вы занимаетесь веб-разработкой, то CSS Peek — это расширение, которое обязательно должно присутствовать в вашем наборе инструментов. Данное расширение позволяет быстро просматривать CSS-правила, применяемые к различным HTML-элементам. Для того чтобы увидеть соответствующий CSS-код, достаточно навести указатель мыши на имя класса элемента или на его ID.

Ниже показан процесс работы с CSS Peek.

Работа с CSS Peek

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

3. Beautify

Если вам нравится чистый код, то вам, определённо, придётся по душе расширение Beautify. Оно позволяет форматировать код. Beautify поддерживает JavaScript, HTML, CSS, Sass и JSON.

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

Beautify, с более чем 5 миллионами загрузок, входит в топ-20 самых популярных расширений.

4. Auto Rename Tag

Расширение Auto Rename Tag решает весьма простую задачу, но, несмотря на это, оно способно занять достойное место в наборе инструментов программиста. А именно, оно автоматизирует задачу переименования HTML-тегов. В частности, если переименовывают открывающий тег, меняется и закрывающий тег. То же самое происходит и при переименовании закрывающего тега.

Если вам нужно, чтобы после ввода скобки, завершающей открывающий тег, автоматически вводился бы закрывающий тег, взгляните на расширение Auto Close Tag. Если у вас есть оба эти расширения, это хорошо поможет вам в написании HTML-кода, сделав ваш труд эффективнее, а результаты вашей работы — единообразнее.

Работа с Auto Rename Tag

5. Quokka.js

Расширение Quokka.js — это нечто вроде «песочницы» для экспериментов с кодом, встроенной прямо в редактор. Она позволяет работать с файлами, выводя соответствующие подсказки непосредственно в коде. Эти подсказки появляются в процессе ввода текста программы, что очень удобно.

Работа с Quokka.js

6. Night Owl

Чего стоит оптимизация VS Code без использования изумительной темы? Программисты проводят очень много времени, работая в редакторе, поэтому — чем привлекательнее выглядит редактор — тем лучше. 

Night Owl — это одна из замечательных тем, используемых многими программистами. В описании к ней сказано, что она рассчитана на тех, кто засиживается за компьютером до поздней ночи.

Тема Night Owl

Но если вам эта тема не нравится — ничего страшного. Существует ещё очень много хороших тем, одна из которых вам точно подойдёт.

7. JavaScript (ES6) code snippets

Расширение JavaScript (ES6) code snippets, завершающее этот материал, предлагает разработчику набор сниппетов, которые позволяют быстро создавать современные JavaScript-конструкции.

Например, если, пользуясь этим расширением, ввести clg и нажать Enter — в код попадёт console.log. Для того чтобы освоить все имеющиеся в этом расширении сниппеты может понадобиться некоторое время. Но тот, кто внедрил в работу JavaScript (ES6) code snippets, сможет по-настоящему быстро писать современный JS-код. Это окупает время, потраченное на изучение данного расширения.

Какими расширениями для VS Code пользуетесь вы?

Let's block ads! (Why?)

[Из песочницы] Технология видео поиска «Video Color»

Немного о поиске

Когда мы говорим о поиске, то сразу представляем себе поисковую систему Google с формой для ввода текстовой строки и многие сотни результатов ссылок на найденные страницы. Однако задумаемся о предмете нашего поиска.

Что мы ищем?

• Текст
• Документы
• HTML странички
• Изображения
• Аудио
• Видео
• Двоичные файлы

Для некоторых видов данных существуют специализированные поисковые системы. Например, существуют сайты специализирующиеся на поиске DLL файлов.

Поиск видео

Давайте рассмотрим поиск видео информации. Каким образом можно это сделать? Чисто теоретически?

• По тексту
• По изображению
• По короткому видео фрагменту
• По короткому аудио фрагменту

Текущее положение дел

Поисковики

• Google
• Microsoft
• Yandex

Я назвал три крупнейшие поисковые системы и все они позволяют осуществлять поиск видео по тексту и по изображениям.

Недостатки современных поисковых систем

К сожалению, все они страдают от следующих проблем:

• Не всегда есть точное название найденного видео. Вместо этого может быть правильно указан актёр и представлены другие изображения с ним.
• Нет точного указания положения в видео. А это весьма полезная информация.

Да, это так. Попробуйте сами и Вы убедитесь, что я прав. Поисковым системам свойственна некоторая неопределённость. Посмотрите скриншот представленный выше, тот, на котором изображён Том Хэнкс. Нет ни названия фильма, ни позиции, в которой он сделан.

Постановка задачи

Перед тем как приступить к решению задачи, давайте попытаемся её описать. Итак, что мы хотим?

Желаемая скорость выполнения запроса

В наше время никто не будет ждать несколько минут выполнения поискового запроса. Однако объем данных и вычислений может быть таков, что потребуется определённое время для обработки запроса. Нужно идти на компромисс. Время выполнения поискового запроса условно ограничим 10 секундами (± несколько секунд). Это, с одной стороны, позволит браузеру не разрывать соединение, а, с другой стороны, даст время скриптам для обработки информации.

А каков объём данных?

Давайте прикинем в уме.

Количество видео

Согласно базе данных по кинематографу IMDb, всего было снято около 2,6 миллионов кинолент, включая отдельные эпизоды сериалов, мультфильмы и короткометражки. (Информация на 13 ноября 2018 года).

Для начала ограничимся круглым числом 1 миллион видео. Понятно, что мы даже не пытаемся коснуться YouTube и других аналогичных сервисов, где объём видео в разы больше. И главное, этот снежный ком будет только расти.

Количество кадров

Некоторые фильмы или эпизоды сериалов довольно коротки. Есть по 15-20 минут. С другой стороны, есть немало фильмов продолжительностью до 2 часов и более. Не мудрствуя лукаво, примем среднюю продолжительность видео равной 1 часу.

Большое количество фильмов сняты с частотой 24 кадра в секунду, но есть и более скоростные. В наше время каждый может снять свой фильм, а частота кадров в нём может быть и 60 и 100 и 200 FPS и выше. Всё зависит от видеокамеры, фотоаппарата, экшен-камеры, смартфона, камеры видео наблюдения и т. д. (нужное подчеркнуть). Всё в наших руках. Но, давайте примем в первом приближении частоту кадров среднестатистического видео равной 30 FPS.

В этом случае в среднестатистическом видео будет:

30 FPS * 3600 сек = 108 000 кадров

Округляя получим, что в среднестатистическом видео порядка 100 000 кадров.

Объем данных

Каков объём хранения информации об одном кадре? Очевидно, что это значение зависит от алгоритма сравнения кадров в нашей базе данных с заданным образцом. Мы используем два алгоритма для сравнения данных. В одном из них на кадр требуется около 30 байт, в другом около 10 байт. Возьмём среднее — 20 байт.

Значит для хранения информации о 1 миллионе видео необходимо

1 000 000 видео * 100 000 кадров * 20 байт = 2 000 000 000 000 байт

Проще говоря, нам потребуется около 2 Тбайт для того чтобы как то описать все наши кадры. Что, вообще говоря, не так уж и плохо, ведь этот объём информации может уместиться на современном HDD или SSD диске. С другой стороны, эту информацию следует как то упорядочить, в противном случае даже для простого чтения 2 Тбайт понадобится ума времени, а мы ведь договорились, что пользователь не будет ждать более 10 секунд.

Даже если считывать информацию с диска со скоростью 500 Мбайт/сек нам понадобиться 2000 секунд, т. е. более получаса!

А сколько серверов нам понадобиться для поиска за указанное время?

Если предположить, что мы храним информацию равномерно на нескольких серверах, то, в этом случае, объём обрабатываемой информации для выполнения одного поискового запроса уменьшается. Например, если у нас 10 серверов, по на каждом из них потребуется обработать не 2 Тбайта информации, а только 200 Гбайт. Или если у нас 100 серверов, то потребуется обработать не 2 Тбайта, а 20 Гбайт информации. В принципе, указанного количества должно хватить для функционирования такой поисковой системы.

Сколько запросов в секунду сможет переварить такая система?

Трудно ответить точно, но вероятнее всего максимум несколько десятков запросов в секунду.

Что было сделано

Сначала нами был реализован поиск по видео фрагментам. Однако вскоре был реализован поиск по изображениям.

История

1 июля 2019

В этот день была выпущена первая версия пакета VideoColor. Она включала в себя три части:

• Manager (индексирование исходного видео)
• Server (серверная часть, которая принимает запросы и ищет совпадение в базе индексов)
• Client (клиентское приложение, которое позволяет проигрывать AVI файлы и отсылать поисковые запросы серверу).

Март 2020

Был создан веб-сайт с возможностью идентификации видео по загруженному видео фрагменту.

14 апрель 2020

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

23 июня 2020

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

Поиск по видео фрагментам

Основная идея

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

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

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

Плюсы

• Относительно небольшой размер индексов. Один час видео в проиндексированном виде занимает около 1 МБ. Таким образом, 1000 фильмов, каждый продолжительностью около 2 часов, в проиндексированном виде займут около 2 ГБ.
• Достаточно точный поиск. Даже если видео пережали несколько раз, если оно визуально выглядит удовлетворительным, то фрагмент скорее всего будет найден.
• Для абсолютного большинства поисковых запросов для правильной идентификации достаточно коротких фрагментов 5-10 секунд.
• Качество поиска слабо зависит от разрешения видео (в определённых пределах).
• Поиск идёт исключительно по видео. Аудио из процесса полностью исключено. Плюс в том, что несколько версий одного и того же фильма с разными звуковыми дорожками в результате поиска приведут к одному и тому же фильму. Это исключает ненужное дублирование и, как следствие, экономит ресурсы.

Минусы

• Поиск необходимо вести от начала и до конца. Т.е. при поступлении запроса необходимо сравнить его со всеми образцами в базе данных. Это накладывает определённые ограничения не только на тип памяти для хранения информации, но и для размеров этой самой памяти. Для того чтобы получить ответ за несколько секунд необходимо, чтобы индексы находились в оперативной памяти. Чем больше база, тем больше места в ОЗУ выделено для хранения информации и тем дольше будет длиться поиск. Например, для 2-х канального доступа и при использовании памяти DDR3 частотой 1600 МГц для поиска по базе размером 12 ГБ понадобится минимум около 0,5 секунды. Для базы размером 48 ГБ необходимо будет уже порядка 2-х секунд минимум.
• Для очень темных или очень светлых мест в видео (обычно это эффекты перехода между сценами) на коротких исходных фрагментах поиск будет работать плохо. Будут многочисленные совпадения. Что, в общем то, вполне понятно, но неприятно.
• Также будут проблемы идентификации с начальными заставками компаний производителей видео или с сериалами. Что, в общем то тоже, вполне понятно. Это не проблема алгоритма — это дубликаты данных.
• Качество поиска может сильно зависеть от обрезки видео по краям.

Поиск по изображениям

Основная идея

Разбиваем исходное изображение на ячейки таблицы M x N. Находим усреднённое значение красной, зелёной и синей компоненты в каждой из областей. Собственно набор этих значений и будет характеристикой этого изображения, с помощью которой мы сможем их все отличать друг от друга. Заносим эту характеристику в базу данных вместе с указателем на описание видео (Video ID) и порядковым номером кадра в видео. Остаётся лишь вопрос, какие значения принимают M и N? Мы взяли 5 x 5, но Вы можете попробовать другие значения. При небольших значениях этих параметров есть шанс что у нас будет много дубликатов, а при больших — мы потратим много памяти.

Однако это ещё не всё. Если в дальнейшем осуществлять поиск по всем этим характеристикам, то на обработку каждого запроса будет уходить много времени! Как же быть? Можно подсчитать усреднённое значение R, G, B компонент для этого изображения и на основе этих значений группировать их в массиве данных. Например: R=200, G=188, B=212. В этом случае мы заносим информацию о кадре в соответствующий раздел или добавляем поле в таблицу. А при поиске аналогично определяем эти компоненты и ищем с учётом этих параметров. Таким образом, мы во много раз сужаем объём сравниваемых данных и ускоряем поиск.

Если честно, то это только в теории, на практике всё немного иначе. Но это тема для отдельной статьи.

Плюсы

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

Минусы

• Вследствие того, что после перекодирования видео может несколько отличаться от оригинала, да и JPEG-кодирование (при поиске по изображению) меняет оригинал и группа может быть определена неверно. Это требует либо расширения диапазона группы (приводит к уменьшению скорости поиска) либо к дополнительным поисковым запросам (тоже замедляет поиск).

Инструментарий

На сегодняшний день написано несколько приложений, некоторые из них успели устареть и больше не поддерживаются.

Поиск видео (клиентская часть)

• Через веб-форму на сайте
• Через приложение «Video Color Capture»

Поиск видео (серверная часть)

• Video Color Server. Существует две версии: Windows (работает как сервис) и Linux (работает под обычным пользователем, запуск через crontab).

Добавление видео

• Через приложение «Video Color Creator»

Области применения поиска видео по видео фрагментам

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

Идентификация старых и неизвестных видео фильмов

Предположим, что у вас есть файл с корявым названием. Начальная заставка либо отсутствует (замысел автора) либо вырезана. Что это за фильм? Хотелось бы прочитать описание и комментарии тех, кто его просмотрел.

Нахождение и отсечение рекламных блоков

Пример: У вас есть свой самописный видео плеер и вы хотите, чтобы при просмотре потокового видео ваши пользователи видели не рекламу с центральных каналов, а вашу собственную.
Проверка частей видео на предмет заимствования их из других фильмов (плагиат)
Пример: Если есть подозрение, что кто-то использует в своём видео ваше видео (снятое с квадрокоптера).

Определение точной даты публикации и названия шоу (передачи) если в репосте отсутствует данная информация

Пример: Вы смотрите видео-шоу, размещённое на неизвестном сайте. Возможно, вы даже знаете, как это шоу называется, но не знаете, когда оно было показано. Год назад или два?

Определение более-менее точной позиции проигрываемого потокового видео, если идёт вещание ранее проиндексированного видео

Пример: Это может понадобиться если вы хотите прикрутить к чужому потоковому видео приложение, демонстрирующее титры или другую контекстную информацию (карты, ссылки, новости и т. д.). Сперва идёт захват видео, расчёт индекса, идентификация видео и позиции на сервере, а затем приложение выводит в отдельном окне контекстную информацию, синхронизированную с воспроизводимым видео.

Как пользоваться сервисом

Поиск видео через веб-форму на сайте

Для этого необходимо загрузить видео фрагмент или изображение в соответствующее поле формы.

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

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

Поиск видео с помощью приложения

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

Можно ли в одиночку наполнить содержимое базы данных индексной информацией об одном миллионе видео?

Скорее всего нет. Где взять эти видео? Как их прокачать по сети? Где взять вычислительные ресурсы для их обработки?

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

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

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

Планы на будущее

• Ускорение поиска.
• Повышение точности поиска.
• Поиск по аудио фрагментам.

Поиск видео по коротким аудио фрагментам дополнит существующие два метода поиска (по видео фрагментам и изображениям).

Итоги

• В данной публикации мы рассмотрели текущее положение дел с поиском видео.
• Ознакомились с методами поиска видео по короткому видео фрагменту и изображению.
• Рассказали о приложении для поиска видео «Video Color Capture».
• Упомянули о приложении «Video Color Creator» для добавления в общую базу данных видео компании «AAP Software».

Ссылки

Сайт

http://www.videocolor.aapsoftware.ru/
На сайте доступен поиск по короткому видео фрагменту, а также по изображению из видео.

Приложения

• Windows x64 приложение для идентификации видео Video Color Capture
• Windows x64 приложение для добавления видео в базу данных Video Color Creator
• Все приложения бесплатны.

Видео

Публикации

Let's block ads! (Why?)