Кодируем | Артем Пушкин

Hash Table Всем привет, друзья! 🤍 На этот раз разберем, что такое Хеш Таблицы, очень много про них поговорим, посмотрим на множество рисунков и расскажем разные примеры. ℹ️ Этой информации хватит с головой и для Leetcode, и для работы, и для прохождения интервью, и просто освежить знания, а то и узнать новенькое! ℹ️ Плюс-минус это будет актуально всегда и для разных языков программирования (py, go, cpp и др). Используются эти же принципы, с дополнительными оптимизациями и наворотами. Понять их после этого видео будет значительно проще, если вдруг вам захочется это сделать! ℹ️ Это самая популярная структура данных, которая используется просто везде и всюду, поэтому стоит уделить ей какое-то время! ℹ️ В этом видео я собрал очень много всего и больше гуглить и искать что-то по теме уже не обязательно! Это видео будет полезно тем, кто хочет понять: 💡 что такое хеш таблицы / load factor 💡 что такое хеш / hashing / hash функции 💡 как использовать хеш таблицы 💡 Как они resize'атся 💡 Откуда там зацикливания 💡 какие бывают виды хеш таблицы и как они устроены (Open Addressing [Linear Probing, Quadratic Probing, Double Hashing], Chaining). 💡 какие варианты и когда применять в разных ситуациях 💡 Performance. Когда можно вообще забить и найти линейно в массиве? 💡 как применять на Leetcode 💡 как применять на работе Links: 📹 Hash Table

Golang Scheduler Я тут решил немного поразминаться и вспомнить кусочек моего исследования косательно планировщика Golang и того, как он ищет свободные горутины для исполнения 😄 ⚡️Go runtime имеет свою подсистему синхронизации лочек, каналов, mutexes и свой шедулер. Специально, чтобы не делать дорогой контекст свитч в namespace ядра. Это значит, что разного рода ожидания синхронизируются локально без похода в ядро. Он менее подвержен сильной деградации при большом кол-ве соединений и эргономично распределеяет их между потоками параллельно и асинхронно ❓G - горутина (тысячи) ❓P - процесс, на котором выполняются Gs (кол-во = GOMAXPROCS) ❓M - машина (реальный поток ОС) на котором выполняется P ❓Park - сохранить в ожидании, сделать неактивным Этапы поиска горутин для исполнения: 💡 1/61 GRQ Вызов дорогой + лочка; не даем ждущим горутинам Gs в глобальной очереди простаивать, если локальная очередь LRQ у всех Ps всегда занята; забираем ИНОГДА от туда горутинки) 💡 LRQ В первую очередь берем Gs из локальной очереди без синхронизации 💡 GRQ Берем из глобальной очереди 💡 NetPoller - Fast path - Non-blocking - Забираем сразу пачку горутин Gs из NetPoller'а - Это те горутины, сетевые дескрипторы которых получили некоторое событие из Linux Kernel в event loop'е - они готовы, чтобы в них писали или в них есть данные, чтобы прочитать; есть разные виды event loop'ов, такие как select, poll, epoll, io_uring, которые мониторят множество разных дескрипторов на предмет наличия в них определенных событий. Поток на нем полностью засыпает и Linux Kernel сам отдаст вам снова управление, как только будут события) 💡 Work Stealing Крадем горутинки Gs у других процессов Ps (но при выполнении определенных условий; иначе - пропускаем) 💡 GC's marking Gs Помогаем GC, если он активен сейчас 💡 GRQ Снова проверяем глобальную очередь 💡 NetPoller Блокирующий вызов (время ограничено pollUntil) 💡 Park M Нет никаких задач сейчас - паркуем M в пул потоков, пусть спит Некоторые особенности: ✏️Сильный вторичный фокус (первичный - LRQ, GRQ) на операции I/O - планировщик несколько раз пытается отработать их, даже если никакой обычной работы нет. Только когда понятно, что ничего нигде не происходит можно начать парковать Ms ✏️ Из NetPoller'а Gs берутся батчами. Одна G возвращается, другие перераспределяются между Ps & GRQ. Если для них недостаточно Ms для выполнения, Ms создаются или стартуют припаркованные ✏️ Стилить сразу не будет, а только: 1 Попробовав LRQ, GRQ, NetPoller, GC и инициировав spinning (голодающей) для текущего M на одной из итераций, если работы совсем нет 2 Либо, если spinning Ms в два раза меньше сейчас, чем занятых Ps (тогда текущий тоже начнет крутиться, у нас есть слоты для активно ожидающих Ms (cpu) и можно стилить 3 В этих случаях, мы раскручиваем нашу текущую M и крадем работу у других процессоров, если она там есть 4 Если же spinning Ms уже достаточно и мы не крутимся, то акцент делается на I/O & NetPoller - означает, что и так достаточно крутящихся Ms, стилящих джобы (которых особо нет) и мы бы хотели потратить ресурсы этого M на I/O через blocking механизмы ✏️ На каждой итерации либо вернем G (или распределим пачку от NP), либо стартанем новую итерацию (но, каждая итерация может немного отличаться, в зависимости от того, что до этого было) ✏️ Весь алгоритм повторяется заного, если ничего не нашлось ✏️ Конкретные варианты исходов могут быть определены, если описать это в виде разных вариантов workflow (либо FSM), которые могут случиться при разных условиях (fail path, happy path, gc has something, NP has something, etc), используя событийную модель + разные варианты, когда и сколько Ms are [running, parked, spinning], при каких условиях они рестартуют цикл. Более того, необходимо учитывать еще внешние события, которые приводят к текущему состоянию системы 🔗Kод читать можно с этой строчки: https://github.com/golang/go/blob/master/src/runtime/proc.go#L3294

Критическое мышление🧠 Повышаем свою гиканутость 🕺 Подсматриваем, что там в реальном мире 👀 ❕Большая просьба здесь и на youtube проставить лайки для обоих частей видео, плиз) 1 минутка 😄 ау-ау 🥺 thank u very much) Все-таки сделал это видео. Все, что у меня накопилось я перенес туда и постарался как-то рассказать лайтово. Что-то доресерчил. Немного перегорел от съемок... Но, рад что получилось! Как мог старался)) ⭐️Кому не интересно, все ок! Будет в будущем тех контент! Разбавить немного ведь никогда не помешает 🙂 ⭐️Если я где-то ошибся, это норм! Это не какая-то истина в первой истанции! 🙂 ⭐️Есть свои паттерны, истории и тд - пишите, с удовольствием почитаю 🙂 ⭐️Таймкоды в описании каждого видео ⭐️Лайк за дракончиков 🐉 ⭐️Поддержка очень важна! Я тоже человек, представляешь? 🥺 🔗Можно сразу прыгать в ловушки мышления, если не хочется все другое смотреть 2:29:00 🔗Тотальная схемка по ресерчу, аргументации, мышлению здесь 9:36:47 🔗Формы аргументации 4:21:48; 4:35:04; 4:39:06 🔗False Dillema ❌✅ 3:14:51 🔗Confirmation Bias 4:05:38 🔗Generalization 5:04:13 🔗Straw Man Fallacy 🤡🤡 7:09:15 🔗Ad Hominem 👊😡 8:31:26 🔗Red Herring 🎣🐠 25:12 ❓Замечали, что иногда то, что мы думаем в реальности оказывается совсем другим? Думаем, что мы правы в данной ситуации, а потом понимаем, что оно вообще работает иначе? ❓Кто-то говорит настойчиво какую-то фразу, которая кажется не имеет смысла и логики, но звучит убедительно? wtf? ❓Или что нам поясняют, что ты ничего не понимаешь на самом деле? Все иначе в реальности? Это у тебя в голове все! ❓Что ты мне втираешь? Какие нафиг факты? Газлайтер шта-ли? Душный? Мне лучше знать как правильно! ❓Тебя б в другом месте вообще прибили! Скажи спасибо, что легко отделался парой синяков! ❓Замечали, что решение, которое принято за 5 мин или оно же, но с тщательным обдумыванием по факту могут координально различаться и вести к совершенно разным результатам? ❓Когда вы спорите с кем-то, а человек просто прыгает по рандомным темам, путает вас и делает виноватым? ❓Или искажает все, что вы говорили? ❓Или атакует вашу внешность или поведение? ❓Есть ли какие-то подходы, при которых можно аргументированно придти к адекватному результату? Истине? Или к оптимальному варианту? ❓Могут ли существовать две правды? У тебя и у меня? ❓Что такое сильный, слабый, валидный и невалидный аргумент? Как его составить, убрать эмоции и манипуляции? Это вообще реально? ❓Или балабол или покажи мне пруфы, ссылки, статьи, древние писания и двойные слепые исследования по теме ❓Да херня эти твои пруфы, мы все знаем, что это не так работает, вернись в реальный мир уже:D ❓Не веришь мне? Я для тебя пустое место? Здесь мы как можем постараемся разобрать все эти вопросы. Не кидайте камнями, как мог старался) ℹ️Мне не особо было интересно собирать чистую теорию, философию и проч, и поэтому там в основном все, что удобно для практики. Чтобы было одно место, где можно все об этом посмотреть, подсмотреть, вспомнить (что такое КМ, 70+ видов ловушек мышления, виды манипуляций и различные способы их применений, несколько видов схем аргументации, небольшая теория аргументации, чтобы понимать о чем речь, инфо про научный подход, механизм принятия решений + все сагрегировал в кучу в самом конце в виде большой обобщенной схемы, чтобы можно было быстро вернуться и вспомнить) Это видео может причинить пользу тем, кто хочет понять: 📌что такое критическое мышление 📌почему мы постоянно попадаем в ловушки и ошибки мышления и как этого избежать🤔💭 📌как подходить к принятию решений, строить адекватные и выполнимые планы 📌повысить вероятность принятия более лучших решений↗️ 📌как подходить к глубокому исследованию какой-либо темы🧑‍🔬 📌как вести аргументированный спор и показаны основные схемы составления аргумента 📌как проверять свое мышление через такие схемы✅ 📌как использовать научный подход✏️ 📌и одно из ключевых частей - более 70 самых важных ошибок мышления 🎧 📌понимать логику манипуляций в отношениях и дебатах 👿🤬 📌стать немножечко лучше 🐰 📹Критическое мышление Часть 1 (ТЫК) 📹Критическое мышление Часть 2 (ТЫК) 📚Книжко ТЫК

Когда применять 🔤lean 🔤rchitecture❓ Part 4/4 У меня есть забавное хобби. В конце напишу 🫠 Говоря о бесконечных холиварах на разные темы, в том числе и про SOLID & Clean Code, можно наткнуться на интересное 😈 Есть забавное когнитивное искажение, когда мы склонны придерживаться и защищать точку зрения, которая нам больше всего знакома или которой мы интересуемся в последнее время. Например, мы читаем про процедурное программирование и везде видим процедуры и все передаем в них и из них. Читаем про функциональное программирование и нам везде видятся функции и отсутствия состояний, любое состояние кажется чем-то чужеродным мышлению. Читаем про ООП и паттерны GOF и все хочется делать классами, а все эти функции и switch'и и прочее - не по феншую, не то, не "по правилам". Изучаем алгоритмы и хочется все через них решать и мы видим их везде вокруг нас. Читаем про SOLID и Clean Code - начинаем все подряд выносить, все что только выносится и декомпозируется, пока оно не станет нечитаемым куском BBOM. Работаем с low-level и везде видим оптимизации каждого бита "иначе мир придет в упадок от не оптимальных программ". Wtf is going on?🤷‍♂️ Человеку часто свойственно такое искажение в разных вещах, думаю каждый замечал это в себе. Самое интересное, что мы начинаем все чаще искать именно ту инфо, которая подтверждает наши взгляды, закрепляем ее в сознании. Сторонние вещи все более и более становятся чужеродными. Все эти истории с людьми, которые по 10 лет изучают досканально какой-нибудь с++ и считают что вот ты обязан знать язык, на котором пишешь. Также досканально. Или ты не достоин, плохо разбирался и т.д. Почему не повторяешь док-цию каждый месяц? Не инженер? Тот, кому зашел какой-нибудь X и он потратил годы на него, начинает видеть все другие Y плохими и недоделанными, а людей недостаточно умными, чтобы понять сокральный смысл X. Это же легко (про годы заучивания мы, конечно же, опустим). Любые споры и аргументы против, часто воспринимаются максимально агрессивно. Защитная реакция просто не даст на подсознательном уровне согласиться, что ты потратил годы жизни копая и шлифуя то, без чего в 80% времени и проектах можно обойтись. Либо все знаешь, либо не достоин 🤬 Мышление очень сильно подвержено confirmation bias, это форма lazy thinking и работает автоматом. Человек начинает искать первую попавшуюся ссылку, подтверждающую именно его точку зрения и вкидывать в качестве аргумента. Повторить. Повторить. Повторить, заставить силой согласиться. Можно еще из головы придумывать🫠️️️️️️Докинуть немного атаки на личность и эмоции. Часто каждое такое "доказательство" подкрепляется generailzation bias - вот видишь, ссылка со мной согласна, значит весь мир так думает и весь мир так устроен. Весь мир как-бы схлопывается в черное белое polarized thinking - либо так, либо никак 🤯 ℹ️ Я собирал много инфо по теме критического мышления, когнитивных ошибках мышления и предвзятости. Еще я провел несколько real-life экспериментов на подобную тему устроив пару споров в разных чатиках 🙂 Понятно, что я не психолог, а просто собрал интересные штуки. Если кому-то интересно critical thinking, темы расхождения представления о реальности с реальностью, разного рода cognitive fallacies, biases, манипуляций и тд ("всем же известно, что киты розовые, не выставляй себя идиотом", "все смотрят на меня", "мой прапрадедушка курил и дожил до 100 лет и все норм, че ты мне втираешь?", "я никогда не встречал это, значит оно нигде не надо", "если я не выучу все алгоритмы, моя жизнь будет разрушена", "если мы начнем делать SOLID, скоро код станет говном", "все собаки злые; значит, если у тебя есть собака, она тоже злая" 🤨 и множество других ошибок мышления и их названия), то я бы мог поделиться своей небольшой работой на эту тему, разных форм аргументов, способов манипуляции и тд. Оно больше про логику и мышление, не про псих манипуляции. Правда, там много работы нужно, чтобы подготовить более-менее не стремно✍️ Но, это может быть нудновато, для узкого круга и повысить степень гиканутости! 🤓 😂 #Clean_Architecture #Critical_Thinking

Когда применять 🔤lean 🔤rchitecture❓ Part 3/4 Все это и многое другое - принципы и паттерны, а не привязка к конкретному одному примеру. SOLID, Clean Code & Architecture - не про "ой вот у нас класс с виртуальным методом, я ща накатаю искуственный пример и покажу, что SOLID - говно" 🤡 😑"Дай уже метод, который везде подойдет, шобы раз и вот как весь крутой софт делался делаешь и все супер. Опять воды налил, сам ниче не знает". Ответ - этого способа нет. Каждый проект и подход требует отдельного ресерча, обдумывания. Необходим опыт в разработке, опыт в бизнес логике и предметной области, workflows, events, etc. Часто это все вообще не доступно. Это живые системы с изначальным накидыванием границ и оптимальной модульностью. Эволюция и подстройка. А иногда инфы вообще нет (изобретаешь новое, делаешь никому незнакомое). Agile development, итеративно растет приложение и постоянно проходит цикл рефакторинга. Применяется наработанный опыт, чувство вкуса, логики, separation of concerns и др. По мере знакомства с предметной областью, появляются идеи и видение деталей и абстракций (или наоборот, что не нужны). Очень много новых идей так реализовывалось, которых в мире до этого не было. Научный подход. А не попытки водопадом все продумать заранее с кучей неизвестных и найти одну единственную универсальную silver bullet. Ее нет. 💬 🔗Проект начинается не с абстракций, а абстракции начинаются с проекта🔗 💬 🔗Избыточные абстракции делают проект неподдерживаемым🔗 💬 🔗Избыточные детали реализации (implementation) делают проект неподдерживаемым🔗 Это просто баланс между abstraction & implementation. Гибкое мышление и изменение. Где без абстракции очень тяжело - внедряем их. Там, где они лишние или мы можем их иначе реализовать - делаем. Замеряем и все плохо - оптимизируем. Если нет - зачем тратить время на оптимизации? Применяем устоявшиейся подходы. Зависит от текущих знаний, умений и опыта команды. Разные люди могут совершенно по-разному написать код. У каждого свои способности и нет идеального варианта. Адекватно всегда исходить из текущей ситуации, а не впихивать все вокруг в искусственный шаблон (lazy thinking - дай одно решение, лень думать и подстраивать там че-то, ерунду говоришь). 💬 🔗Premature optimization is evil🔗 💬 🔗Premature abstraction is evil🔗 ⚠️ There is no silver bullet⚠️ #Clean_Architecture

Когда применять 🔤lean 🔤rchitecture❓ Part 2/4 💡При выполнении нашего executable, использующего символы из разных shared libraries, этим символы могут не резолвиться сразу, а в рантайме - есть специальный механизм ловушек, чтобы инициализировать их в локальных таблицах GOT, PLT по месту вызова (lazy loading - как только вызвали функцию, dynamic linker ищет адрес, где она определена и сохраняет). 🔗PLT (Procedure Linkage Table) — это таблица компоновки процедур 🔗Delayed loading 💡В С++ вирутальные методы и иерархия классов может быть соптимизирована компилятором. Виртуальность полностью выбрасывается и подставляются актуальные вызовы функций без походов в vtable. Такая оптимизация может происходит, если компилятор видит, что символы используются только в данной единице трансляции и нет вероятности, что оно вылезет наружу или нужен будет dynamic polymorphism. Также там много других мест, где они ее используют. Так что не все так просто и в уме такое не просчитаешь. 🔗Devirtualization in C++, part 1 🔗Devirtualization in C++, part 2 🔗Optimizations in C++ Compilers 💡Где-то нужна скорость и максимальные cpu cache-friendly data structures. 🔗Entity component system 🔗Data-oriented design 💡Когда мы читаем или пишем в файл, угадайте, сколько уровней абстракций в системе это проходит? У нас есть std library нашего языка, которая может закешировать ваши данные - они реально не пошли ни в файл, ни, например, в консоль. Она ждет больше данных, чтобы минимизировать syscalls и снизить расходы. Когда она все же пошлет это ядру, ядро, в свою очередь, тоже кеширует данные в памяти. И будет держать такие ваши грязненькие данные, пока не появится возможность записать их в дескриптор файла. Представьте, вы база данных и записали в файл событие снятия денег с аккаунта пользователя, оно повисло в ядре и машина перезапустилась, шо делать? 🙂 🔗Stdout & Buffer & Newline 🔗setvbuf 🔗write & fsync & kernel buffering 🔗The buffer cache 💡Ну и я думаю, все уже слышали, что файлики, сокеты, терминальчики - представлены файловыми дескрипторами. Омг, они просто помешались на SOLID'е и абстракциях! 🔗Everything is a file 💡Pipeline из команд в нашем любимом bash - что это? Просто, казалось бы вертикальная палочка и сама работает и есть не просить, а вот нет 🙂 Вы хоть раз правили ее поведение каким-то образом программно? Лезли в имплементацию? Сколько раз пересобирали программу, потому что пайпы как-то изменились в обновлением? Скорее всего, ни разу. Крутая так-то абстракция. 🔗Pipeline 💡"It was later summarized by Peter H. Salus in A Quarter-Century of Unix (1994): Write programs that do one thing and do it well". Looks like SRP Principle. 🐶 🔗Unix philosophy 💡Когда пишете GUI приложение, как часто вы лезете в рендер и правите его поведение? Скорее всего 0 раз. У вас есть API и механизмы, которые абстрагируют его полностью от нас. Оно само рисуется как-то, причем еще и multi platform на каком-нибудь Qt Framework. 🔗Qt 💡Как часто вы залазили и изменяли, к примеру, physical или logical replication в Postgresql? Оно как то работает 🙂 Есть конфиги какие-то, чтобы devops подтюнили и настроили. Сколько из них написало хоть одну строчку кода, чтобы как-то заюзать код из внутрянки Postgresql? Сокрытие деталей и модульность внутри. Дает возможность реплицировать данные даже без знания внутрянки. 🔗Logical and Physical Replication 🔗Replication 💡Вы хотите писать надежные приложения и не терять ивенты от пользователя? Заюзаем брокер? Kafka & RabbitMQ & NATS с JetStream? Наверное, это сложно и надо точно знать детали имплементации, переменные, функции, которые там у них прямо в коде реализованы, да? Конечно нет. Абстракция, декомпозиция, separation of concerns. Послали request и приняли response (ack). Забыли. Оно надежно лежит в write-ahead log'е и все спрятано за абстракцией, пропускающей через себя миллионы rps, до которой только через RPC можно достучаться. 🔗WAL 🔗WAL Kafka #Clean_Architecture

Когда применять 🔤lean 🔤rchitecture❓ Part 1/4 Прямо очень много споров постоянно проходит про то, где правильно применять SOLID, Clean Code, Clean Architecture. Кто-то топит, что без них никуда, кто-то говорит, что они делают программу сложнее, ухудшают перформанс и вовсе не нужны. Как, собственно, я и говорил в начале видео. По фану поищем разные интересные истории с абстракциями и интерфейсами из жизни. Потом поговорим, как применять. Потом отдельным постом посмотрим, почему так происходят заблуждения и как понять, где истина (или ее нет) (если косячнул где-то, поправьте в комментах) ❓Кажется, что чем меньше абстракций, тем, лучше. Программы будут производительней и все станет лучше само по себе (ведь мир погряз в эпидемии медленного ПО, все плохо). Однако, большинство программ и систем используют абстракции, декомпозицию, разделение ответственности, сокрытие данных разного рода, solid. 💡Возьмем Linux. Наши приложения в userspace взаимодействуют с периферией (e.g. вывести в std output на консольку), как бы вы думали? Правильно, через довольно не легкую абстракцию syscall. Например, мы вызываем функцию, которая на уровне ассемблера подготавливает данные (заполняет определенные регистры) и затем передает управление ядру системы (посылает как dto'шки). Ядро внутри производит разного рода подготовку, поиск номера сискола в табличке, копированием данных к себе из регистров и вызова функции. Потом обратный процесс в userspace, копирование, передача из обертки над asm в std вашего языка и потом в ваши функции. Это четко очерченные границы, ABI (Application Binary Interface) и хорошая абстракция (к нам ничего не течет, оно там как-то само имплементировано внутри std, библиотеки и ядра). 🔗System Calls in Linux 🔗Linux Kernel Syscall Table 🔗TLB 💡Внутри Linux. Тоже самое. Код поделен на разные подсистемы-модули (network, process, memory, peripheral stuff, modules, filesystem, architecture-depended stuff etc). И другие. То, о чем мы с вами говорили. Заметьте, скорость там явно важна. 🔗Concrete Architecture of the Linux Kernel 🔗Linux as a Case Study Its Extracted Software Architecture 🔗Architecture of the Linux kernel 🔗Linux® Kernel Architecture (page 36, 51) 🔗Kernel Architecture Of Linux 💡Множество разных файловых систем имплементируют интерфейс, чтобы работать в системе. Можно даже сделать свою через software interface FUSE. 🔗Fuse 💡Процесс - абстракция над ресурсами нашей машины. Например, вы знали, что когда вы форкаете процесс ядро не скопирует его полностью? На самом деле будет использован механизм copy-on-write и оно будет иметь те же самые страницы памяти. Процессы и потоки (same) шарят между собой и экономят память через вызовы clone, fork и exec, скрывающими имплементацию. 🔗Copy-on-write 🔗Fork, Clone 💡Каждый драйвер устройства может подключаться в виде модуля, реализуя определенный интерфейс. Как Plugin Architecture, о которой мы говорили в видео. 🔗Loadable kernel module 💡Как разные процессы могут взаимодействовать между собой? Слышали про сигналы? Отправил и забыл одним. Принял и обработал другим. Абстракция и один из видов IPC (Inter Process Communication). 🔗Signals 💡А если надо общаться более сложно? Dbus - своего рода локальный брокер в системе, передающий сообщения между процессами. 🔗D-Bus 💡Одна из самых используемых библиотек в мире - pthreads. Угадайте, через что мы взаимодействуем с ней? Да, абстракции, скрывающие детали реализации. Представьте, что бы было, если бы каждое приложение в мире знало о деталях ее реализации? В ней невозможно было бы сделать ни одного изменения. Паттерн используется и в Go. 🔗pthreads 🔗libpthread Interfaces 🔗phtread.h 🔗Abstractions and Interfaces in the Posix Thread and Semaphore APIs (opaque type, page 4) 🔗Opaque pointers design pattern in C #Clean_Architecture

Интересные ролики про производительность и разработку от лучших разработчиков в мире. Сегодня был епик интеллектуальный спор про чистую архитектуру и Владимир @vladimirzay привел один старенький ролик, который все еще актуален енивей (Scott Meyers). Можно посмотреть и вспомнить, для интереса. 📹 Cpu Caches and Why You Care Еще его ролик: 📹 Solving the Right Problems for Engine Programmers Также есть ролики от Chandler Carruth, который разрабатывает компилятор clang. Там они имплементируют солид, декомпозицию, модульность и прочее + стараются при этом всем добиться максимальной производительности, как нигде. Например, пишут свои производительные аналоги структур данных и тп. 📹 High Performance Code 201: Hybrid Data Structures 📹 Going Nowhere Faster 📹 On "simple" Optimizations Еще можно почитать про разного рода SSO для использования стека для маленьких строк и авто переход на heap, когда это необходимо: 🔗 Small String Optimization Еще одна из очень популярных идиом в Linux Kernel (например при fork) и для имплементации строк в разных языках (Clojure), называется Copy On Write (COW) Idiom. 🔗 Copy-On-Write Idiom А также очень известного и опытного товарища Rich Hickey (software developer with over 30 years of experience in various domains), который прогал и на джаве, и сам создал такой язык как clojure, чтобы упростить разработку и который стал популярен во всем мире. Один из the best of the best. Это не прямо про оптимизации и перформанс, но про подходы. Как создавать простые программы, их отличие от "легких" в написании программ (сложная бизнес логика может быть написана просто и понятно или же тяжело для понимания и поддержки), сложности программ, декомпозиции на компоненты и т.д. 💬 🔗If you focus on ease and ignore simplicity, no matter what technology you use, the complexity will eventually kill you🔗 💬 🔗Incidental complexity is your fault🔗 :D 💬 🔗We actually can't get much smarter. We are not gonna move our brain closer to complexity. We have to make things near by simplifying them🔗 💬 🔗Partitioning and stratification don't imply simplicity, but are enabled by it🔗- не всегда разделять и выносить все подряд == чище код (может сделать хуже, наоборот же делает лучше и проще, декомпозирует в простые понятные блоки) 💬 🔗State Is Never Simple. By stateful, I mean, every time we ask the same question we get a different answer... you have this complexity and it's like poison, like dropping some dark liquid in a vase and it's going to end up all over the place🔗 💬 🔗Easy is not simple🔗- это работа, развитие ощущения понимания, когда есть лишняя связность и что с ней делать 💬 🔗Simplicity is the ultimate sophistication🔗- Leonardo Da Vinci 📹 Simple Made Easy Популярные лэтенси для разного рода взаимодействий и их "humanized" version. 🔗 Latency numbers every programmer should know Необходимость применений каких-либо оптимизаций и место для их пременения в проекте диктуется самым медленным компонентом (bottleneck): 🔗 Amdahl's law 💬 Ну и красивая цитатка: 🔗An idiot admires complexity, a genius admires simplicity🔗 - Terry A. Davis #Clean_Architecture

Подкинули видео с критикой чистого кода для спора 🤩 Видео довольно манипулятивное и рассматривает искусственный пример, оторванный от реальности и процериует его на весь сложный мир вокруг со множеством меняющихся требований. 📌 "they tell you never ever do that" - кто "they"? 🤡 Анкл боб сам же пишет - используй свитч, если удобно и размер проекта позволяет. Об этом я говорил тоже. Тоже так делаю. Почему "они" так говорят - первые темы, про которые мы говорили об ограниченности мышления и желания взять 1 инструмент и везде его использовать с fixed mindset. Это не серьезно и biased. 📌 Что такое "clean code" - он дал свое манипулятивное определение без аргументов. Biased. Это уже нивелирует все, что он говорит. Я дополнительно делал акцент на том, что clean code - не инструмент "делай вот так", а принципы, применяемые в нужном месте и время, по ситуации, при эволюции кода. Но, кто бы знал что за деревьями есть лес 🙉 📌 Он на серьезных щах сравнивает разницу между 35 vs 25 cpu cycles 🤡 Буквально, 1 cpu cycle on 4Ghz processor == 0.25ns => 35 * 0.25 vs 25 * 0.25 => 8.75ns vs 6.25ns. В добавок, это сравнение идет при прогоне бесполезной программы 1000 раз карл! Если мы, например пишем любой бекенд, шанс, что твой workflow прогонит разного рода объекты из иерархии 1000 раз очень мал. И даже если вдруг, то.... 9 НАНОСЕКУНД . Такое можно еще считать, если мы ракетостроением занимаемся или жесткими embedded (и то современные ембедед типа телефонов и планшетов даже не заметят этого). Значит, прогнать подобное 1 000 000 раз будет 90 нс, 1 000 000 000 раз - 1мс. Часто, если у нас сложная логика и бд, к примеру, то наш запрос может отработать и за 100-300мс, что 10^8 больше, чем он прогоняет 1000 раз свои объекты для вызова 1 метода => это просто капля в море. Могу миллиарды раз так гонять, и пользователь не заметит 😒 📌 Код стал хуже читаться, поддерживаться, на мастшабах это может убить проект. Теперь каждое место по всей программе должно знать ВСЕ типы объектов, чтобы написать логику. И все поля структуры, чтобы писать логику. Мы не можем просто принять интерфейс и вызвать метод. Нет. Теперь пиши функции и там перебирай все типы объектов. А если что поменяется - меняй их ПО ВСЕЙ программе (представьте в сотне тысяч строк поменять). В своем и даже абсолютно чужом коде, где ты без понятия, что люди делают и как и что изменить надо правильно. Nice👌 📌 Подумайте, почему комменты закрыты полностью? 😏 📌 Оптимизации switch -> hash table не всегда возможны и нужны. Только в узких местах. Я так иногда делаю. Но не для мега оптимизаций, а читаемости кода или удобства. 📌 Подобный подход можно использовать, при разработке в agile style (и мы так делали в видосах). Без лишних абстракций и тд. Когда маленький проект и оч мало людей на нем (1-2-3). Все работает, быстро, без абстракий?. Ок. Скрыто в небольшом модуле. Ок. Легко понять, читать много не нужно. Ок. НО! Даже там мы не будем оптимизировать до талого код, который мы 100% удалим и поменяем на другой, когда проект начнет становиться больше. Или когда эти оптимизации не рациональны в нашей задаче (90% случаев). Такими вещами типа байтодрочева занимаются в чрезвычайно узких местах. 🏃‍♂️ Код пишется не просто "в стол" и его надо поддерживать. Requirements у бизнеса в большинстве случаев не оптимизация до нс. Не "скорость" ради скорости. А имплементация бизнес логики и решения задач ОПТИМАЛЬНО. Чтобы в этот код можно было легко вносить новые изменения и фичи, оптимальная скорость, минимум кода и cognitive complexity, чтобы команды не конфликтовали при разработке и тд. Если я на интервью скажу "я оптимизирую код по максимуму и если потом кто-то захочет что-то в нем изменить, ему надо будет перелопатить сотни тыщ строк и везде принять решение, что и как изменить, чтобы ничего не поломать; clean code говно; зато очень быстро будет!", скорее всего у интервьювера случится когнитивный диссонанс. Можно спорить в комментах 🙂 Срач Кейси и Боб ⚡️ Prime Reacts 📹 "Clean" Code, Horrible Performance 📹 #Clean_Architecture

Чистая архитектура и чистый код. ❤️ Clean architecture & clean code. 💡 Как создать чистую архитектуру и написать чистый код? Какие есть паттерны? Как их применять? Почему все их понимают по-разному? Можно ли их представить без привязки к конкретному языку? Почему для кого-то они не работают? Uncle Bob нас обманул? 💡Их надо использовать в маленьком проекте, скрипте или огромных энтерпрайз решениях? Как бороться со сложностью в наших проектах и делать так, чтобы затраты на внесение новых изменений были оптимальны с его ростом? 💡Можно ли построить монолит на миллионы строк и остаться в здравом уме? 💡На эти и другие каверзные вопросы мы будем отвечать и рассуждать в этом видео. Будет очень много рисунков с отвязкой от конкретных имплементаций на конкретном языке, где это возможно. Где нет - приведем код. Где-то польем воды, как без этого; а то хейтерам не будет работы 😂 💡В целом тут все, что нужно знать, как применять и на какой стадии проекта. Когда их пременение дает профит, а когда сильно мешает и усложняет код. Очень много про decoupling & cohesion, на которых мы построим рассуждения почти на всех уровнях абстракции. Первые главы много и нудно говорят про мышление, которое потом красной нитью абстракций будут пронизаны все остальные главы. 💡Не забудем про SOLID и некоторые другие принципы. Упомянем случаи, когда SOLID приводил к сложноподдерживаемой лапше, а когда делал код красивым и понятным. Где-то кринжанем немного. Все как мы любим)) 💡 Не все и не все смогут понять и тем более сразу применить на практике. Многие вещи нужно вырабатывать как навык, постоянно рефлексируя, рефакторя код после каждой доработки. Но, мы стараемся быть лучше и использовать это, если появляется возможность сделать наш код лучше и понятней для других людей; код, в который легко и приятно вносить новые изменения. ☀️ Надеюсь, каждый найдет что-то полезное для себя. Значит, делал не зря. ❗️❗️❗️Я не сделал акцент и это ошибка. То, о чем мы здесь говорим - generic format паттернов, который мы можем потом применять на разных уровнях абстракции и на задачах разной сложности. Это не академические бесполезные определения в бумагу. Практика и для практики. Мы это рассматриваем на разных примерах. От общего к частному. Не наоборот, как делается сейчас почти везде на YT. Мы не можем частный случай накладывать на всю сложность мира и ожидать успеха. Это как раз и порождает проблемы вида "ты дал определение не по Мартину", "оно не сработало для нас" и тд. Я был бы рад развивать именно это направление мышления и не парировать ваши тейки про частные случаи и не идеальность определений. Это не ведет ни к какому результату и время это показало. Не универсально. ❗️❗️❗️Если не получается понять, о чем речь в начале или других местах, мотайте дальше на те темы, которые вам ближе. Уже появились люди с сильной защитной реакцией в виде негатива. Если что-то не понятно, это не значит оно плохое или глупое, просто сейчас не время и нужно будет вернуться через пол года-год-несколько лет с другими знаниями и взглядами, и попробовать снова. Постарайтесь быть толерантней и ценить чужой труд! П.С. Любые совпадения с реальностью случайны, никакие темы, кроме разработки не затронуты ни явно, ни косвенно. П.П.С. Понятно, что мы не бежим все переделывать и т.д. Просто стараемся улучшать и приводить к чему-то более-менее адекватному с учетом всевозможных факторов, процессов, эмоций и исторических решений. Инкрементно улучшаем без бессмысленного фанатизма. Пытаемся соблюдать осторожность и советуемся. 📹Youtube: https://www.youtube.com/watch?v=WlCDcr8JYFU 📹Rutube: https://rutube.ru/video/1101b8a395a8c2630537e2e5221dbf89 #Clean_Code #Clean_Architecture

Как написать чистый код? (Общий подход) ⭐️ Угадываем, что хотел ввести юзер. Немного говорим про low coupling & high cohesion. Лайкай не глядя! Сегодня разберем, какая все же последовательность действий и ход мышления должен быть, чтобы получалось писать чистый и читаемый код даже там, где есть алгоритмы. Какие есть способы? Как начать разрабатывать и писать код? Как приступить? Декомпозируем задачу на каждом уровне абстракции, спускаемся ниже и ниже и решаем проблемы по мере поступления. 🚀 Сделаем программу, которая угадывает, какую команду хотел вызвать пользователь, но ошибся при написании. Мы подскажем ему, какие похожие варианты есть в нашей системе. 🚀 Мы сделаем максимально легковесно без фреймворков и баз данных и полнотекстовых поисковых систем. Просто возьмем и добавим маленькую и полезную фичу. 🚀 Также сделаем так, чтобы наш код был максимально понятный и читаемый. Чтобы мы могли понять все структуру программы, прочитав пару первых функций на самом высоком уровне. 🚀 Нарисуем все основные части нашей программы. Ньюансы (чтобы экономить время): ❗️Я не стал покрывать все типами, но это обязательно нужно делать ❗️Я не стал покрывать тестами, но это очень сильно помогает для понимания кода, его надежности и поддержки ❓ Соберем вместе фреймворк по чистому коду? Как использовать паттерны, принципы. В чем плюсы и минусы. Сложно или нет это делать? Какие принципы знаете уже или хотите услышать? Чтобы "берешь и используешь" его. Чтобы не спорить "А вот смотри наглядно - это не вкусовщина, а у тебя переплетается логика или потекли абстракции - это плохо и тд". Если будут мысли - пишите. Это было бы очень круто. И это совсем иное, нежели бестолковые часто style guides и code reviews Youtube Rutube Code: https://gist.github.com/idfumg/28d474fd1181b804a49516ecb04eda00 Links: https://en.wikipedia.org/wiki/Levenshtein_distance #Algorithms #Clean_Code

Как долго думать над задачей? Там в чатике снова спрашивают, как же лучше всего практиковать задачки? Как долго сидеть и думать над ней? Давайте выстроим какую-то четкую схему и поймем, почему она будет работать лучше всего. 🚀 Как я говорил, первое - брутфорс. Самое тупое, циклами, рекурсиями. Хорошо найти что-то, на чем тестить. Плюс, это может дать некоторое понимание темы, что мы правильно вообще поняли условие задачи. Теперь, нужно определиться, сколько у нас есть времени. 🚀 Если его много и мы не торопимся , то можем думать над задачей дольше - несколько дней. Крутить в голове всякие варианты и активно пользоваться фреймворком. Выбираться, что лучше именно вам заходит. Собирать инфо. Представлять, как данные перетекают, как мы бегаем по ним мысленным взором и ищем что-то. Просто кайфовое занятие, развивающее фантазию и мышление. 🚀 Второе вариант - нам нужно быстрее. Тогда мы думаем минут 30. Перебираем все паттерны. Вообще никак. Нет идей. Смотрим фреймворк. Берем пару рабочих для вас пунктов. Пытаемся играть с данными, выписывая, вычисляя, составляя уравнение и т.д. Не получается. Это ок. Так у всех бывает иногда даже с тупыми задачами. Я тоже туплю часто! 🚀 Теперь что мы делаем. Мы идем в решения и ПОДСМАТРИВАЕМ ИДЕЮ. Думаем, ага, попробую сам эту идею закодить, вроде там нет спец алгоритма какого-то. И пытаемся сами. Пытаемся это с чем-то связать, что мы знаем. 🚀 Потом смотрим быстро код, его конструкции, не разбирая детально. Попробовать их перекрутить в голове, вдруг будут новые идеи. Кодим теперь сами на память. Не переписывайте. 🚀 В конце уже просто разобрать решение по шагам. Тут уже очевидно, что ты просто не знаешь кого-то подхода, алго или паттерна. А некоторые вещи с нуля изобрести или оч сложно или невозможно вообще. Можно тут даже переписать код вручную, чтобы лучше понять (раз 100 😂). ✏️ Как бы не решили, если вы видите «о, паттерн можно похожие задачи на изи им решать» - выпишите себе и повторяйте их регулярно. Можно просто быстро подсматривать и вспоминать в голове как вы данными манипулируете. Пробегать мысленно по данным - не обязательно кодить каждый раз (разве что по-началу). 🧠 Повторять свои паттерны регулярно. Довести до уровня, когда смотришь на называние паттерна типа "найти n самых больших чисел через heap" и сразу быстро в голове бежишь по данным оставляя в heap только самые большие, накапливая их туда, выбрасывая лишние и в конце это и есть ответ. Занимает 2-3 секунды. Подсматривать только, если забыли, как он работает. Стараться вспомнить самим. ❓Почему это будет работать? Потому что здесь мы используем сразу две важные техники. ⭐️ Первая - active recall. Мы заставляем наш мозг постоянно через "боль" вспоминать и работать. Мозг включается на полную и ищет связи, ассоциации, пытается как-то сопоставить текущие знания с проблемой, вытащить инфо. И такой процесс создаст сильные нейронные связи. В следующий раз, вспоминая и имея более сильные связи, мы сделаем это в несколько раз быстрее. ❗️Это очень эффективно. ❗️Пассивный просмотр не работает. ⭐️ Регулярное повторение - это space repetition. Как в anki карточки. Прикол в том, чтобы не повторять бесконечно пока не сойдешь с ума, а дойти до момента, когда ты начинаешь немного забывать. Чтобы было усилие воли вспомнить (active recall). Чтобы как раз заставлять окрепнуть нейронные связи и сделать их мощнее. Рекомендации обычно через 1 день, 3 дня, неделя, месяц и тд. Но, лучше по своим ощущениям. Чуть забываешь - повторил, прокрутив в голове. ❗️Это помогает тормознуть forgetting curve. Сначала забывается очень быстро, но с каждым повторением все дольше. Если вы это делаете как мульт в голове - это усиливает эффект в разы. 🤩Не психуйте и не нервничайте. Внушите себе, что вам в кайф и интересно. Стресс может значительно замедлить обучение. Он может помочь, но дозированно и не prolonged one. ❗️❗️❗️Не забывать про рефлексию после решения! Они боятся вас больше, чем вы их ;) Пара ссылок в комментах.

Зачем нужны алгоритмы? Получается, ты изучаешь инструмент ради интрумента, а не для полевых условий. Много людей продолжают думать, что алгосики - это баловство, ненужная трата времени и нигде не применяются. Я уже писал про это в постах про рекурсию. ➖ https://t.me/koduryem/13 ➖ https://t.me/koduryem/15 ➖ https://t.me/koduryem/32 Тажке общался с вами в видео про методы решения задач. 🧠 https://t.me/koduryem/26 В двух последних видео много говорили про дп, ход мышления и подходы к проблемам. ✔️ https://t.me/koduryem/33 ✔️ https://t.me/koduryem/34 Также у меня есть видео про другие темы, такие как Heap, BinarySearch, LRU, LFU и др. ➖ https://t.me/koduryem/9 ➖ https://t.me/koduryem/10 ➖ https://t.me/koduryem/16 ➖ https://t.me/koduryem/18 ➖ https://t.me/koduryem/19 ❗️ Все это не просто так. Эти вещи применяются регулярно на работе и в жизни (явно и неявно). Чем больше знаешь, тем больше их видишь везде и можешь применить. 🚀 Тебе надо искать проблемы через трейсы. Ты будешь делать это выводя в лог абсолютно все сутками или же используешь binary search, и мега быстро сведешь проблему к одному месту? 🚀 Ты будешь посылать запросы на выборку в БД в цикле o(n), o(n^2)? Тогда у тебя ляжет бд или приложение будет мега тормозное. 🚀 Твой селект в бд очень тормозит. Что делать? А, у нас же индексы есть! А как они работают? Их же несколько! Как выбрать? В чем разница? 🚀 Тебе надо как можно аккуратней и понятней решить проблему и вот на выходе портянка на 1000 строк. Нет практики работать с данными эффективно и емко. Это можно было сделать в 100 понятных строк с несколькими циклами и одной data structure. Может быть, bruteforce даже будет емче, быстрее и понятнее. Но, человек искренне не понимает, как еще можно. А читать и разбираться в этом потом - тебе. 🚀 Если ты будешь делать in-memory cache, как спроектируешь? Какой структурой? Какой алгоритм? Они же разные могут быть... Взять готовый, лишь бы не писать? А ты понимаешь, как он работает? Что он будет делать и для твоей ли он задачи? Наугад? И да, много кто так делает. Потом это не работает и тот, кто шарит, подсказывает, какой надо и почему. 🚀 У тебя есть набор чего-то, прилетает запрос, выбери самый лучший ответ из него и верни. Или подсказку, если человек ввел неправильно что-то. 🚀 Сделай пдфку на страничку и так, чтобы текст был ровненький и переносы где надо сами вставились. 🚀 Сделай сортировку, но умную, по двум-трем полям. И чтобы порядок не изменился в выводе. UI хочет показывать так. Что возьмешь? Sort? Но, он ведь так прямо не работает. Надо допиливать. Ой, а он же меняет порядок. Ой, ну все, эту задачу нельзя сделать. Кто придумал это говно вообще? 🚀 Что взять Postgres, Cassandra, CockroachDB? А в чем разница? Что лучше, что нет? И где? Там, наверное, есть что-то да такое необычное? Какие гарантии и почему? Не потому, что где-то на заборе написано, а ты реально понимаешь общую картину? Distributed transactions - это бред какой-то, раз в pg этого нет? Как оно работает? 🚀 Сделаем cache с автоматической инвалидацией и апдейтом. Это сложно? Какой алгоритм? Какие инструменты? Как они работают? Какие алго используют? Какие последовательности действий? 🚀 Сделаем шардинг по хешу. Как это работает? Чем плохо? 🚀 Искать в кафке по timestamp? Индекс и быстро или не варик? ❗️ Любая задача в программировании - работа с данными каким-то образом. Это и есть algorithms and data structures. ❗️ В жизни можно любое действие, последовательности, окошки, техники планирования могут использовать их. Как было вот в последних видео. Это не выдумка, не я так считаю, а то, как я мыслю в черно-белом формате «на бумаге». ❗️ Ярость, гнев, упадок настроения, защитная реакция вида "херня это", "в жизни нигде нет", "криво написали сами", "тупые алгосы" - это дефолт, когда ты не понимаешь темы, не имеешь базовых алгоритмических навыков и мышления, пытаешься наобум что-то скопировать, чтобы хоть как-то заработало. А когда оно ломается, значит пора менять компанию 🙂 Когда не хватает силы воли посидеть и поразбираться. Хочется, чтобы само, быстро и без усилий.

Как найти элементы в Dynamic Programing & Thinking Process! Лайкай не глядя! Сегодня разберем, как найти актуальные элементы в Dynamic Programming! То, чего нет нигде на других каналах! Ведь мы уже столько раз видели, как это решается и находили минимум, максимум, количество, суммы и прочее. Но, не всегда это мега полезно и хочется посмотреть, а какие реальные элементы в этой последовательности то? Какие из них дают такой результат? Как нам найти это и использовать в прямо жизни? Здесь вы найдете ответы на эти вопросы! А также услышите маленький рассказ и научитесь еще одному способу представлять это все в голове! Воображение настолько сильное оружие, что мы научимся создавать целые миры из ничего, просто используя эту "хрен зачем надо" и "бесполезную рекурсию". :))) Изучите то, о чем даже подумать не могли ранее. Жду от вас одобрение лайками и поддержкой! Мне будет тоже приятно! Надеюсь, всем понравится этот подход и образ мышления в таких задачах. Скоро будете мне рассказывать, как это все делать правильно! 😄 ❗️Не забывайте представлять в голове эти техники и предыдущие. Это очень важно. И сделает все более интересным! Просто чиселки - это скучно. 🛞 Дай им пройти свой путь, собрать данные и вернуться к тебе с ними. Заюзай то, что знаешь + то, что тебе вернули, после прохождения тысяч вариантов. Собери это и верни результат, чтобы ты же, но намного ранее в другом мире, также собрал это все и обработал. 🛞 После того, как ты послал их по разным дверям, подожди их и выбери ту, что привела к нужному варианту! Запомни себе в кеш. В самом конце восстанови весь путь со всеми решениями в каждом из направлений. Выкинь ненужные направления - они ведут в никуда. Video: https://www.youtube.com/watch?v=Tp792VHs8JU Problems: 💪 https://leetcode.com/problems/minimum-deletions-to-make-string-balanced 💪 https://leetcode.com/problems/filling-bookcase-shelves Recursion: ➖ https://t.me/koduryem/13 ➖ https://t.me/koduryem/15 ➖ https://t.me/koduryem/32 DP Knapsack & Thinking: ➖ https://t.me/koduryem/33 TV Shows: 👁 Dark Matter: https://www.imdb.com/title/tt19231492/ 👁 Solar Opposites: https://www.imdb.com/title/tt8910922/ Общий чатик: 💬 https://t.me/koduryem_chat #Leetcode #DynamicProgramming #RestoreItemsInDP

Dynamic Programming Knapsack & Thinking Process! Всем привет! Сегодня разберем Dynamic Programmin Knapsack! Но, мы попробуем не просто хайпануть стандартным алгоритмом, а рассмотреть его вариации, как его понимать, что такое leap of faith, как его видоизменять в разных задачах как угодно (ограничено только простором фантазии), продавим решение специальными моими эксклюзивными трюками по переводу из рекурсии в итерацию и наоборот, а также трюками по уменьшению состояний dp, трюками с dp оптимизациями вплоть до элементарных заоптимизированных решений. Решим множество задач вплоть до Hard ОДНИМ паттерном! Это вам не шутки! 🙂 Я реально очень постарался и был на драйве! С вас лайки везде везде много много 😄 Ну и стоки мы все собрали и зарешали)) Сам подход, по сути, не является каким-то паттерном, а больше про high-level логику, подход к таким задачам, используя который мы можем найти решения и сами паттерны. rus: 🛞 Использовать накопленные даные в виде состояния, чтобы сделать решение о переходе или выходе 🛞 Брейнштормим все решения, которые мы можем принять в текущем состоянии 🛞 Брейнштормим как мы можем сделать переход в новое состояние, которое ведет ближе к ответу (уменьшая или увеличивая индексы, накапливая что-либо и тд) 🛞 Брейнштормим все возможные невалидные состояния и сразу выходим в них 🛞 Ищем конец рекурсии - мы достигли того, чего хотели или мы собрали наш ответ в параметрах функции, или прямо на текущем этапе выбрали самый лучший вариант из возможных eng: 🛞 Use the accumulated past experience (in a form of states) to make a decision right now 🛞 Brainstorm all decisions we can make right now 🛞 Brainstorm how we can make a transition to a new state, which is closer to the answer 🛞 Brainstorm every possible invalid state, so we immediately return 🛞 Find the end of the recursion (we’ve just reached out whatever we want, or we’ve accumulated the answer in the function parameters, or we have chosen the best possible answer from all partial answer right in this state of recursion). Video: https://www.youtube.com/watch?v=0sdzzkkkFnc Problems: 💪 https://leetcode.com/problems/best-time-to-buy-and-sell-stock 💪 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii 💪 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii 💪 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv 💪 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown 💪 https://leetcode.com/problems/maximum-subarray/ Recursion: ➖ https://t.me/koduryem/13 ➖ https://t.me/koduryem/15 ➖ https://t.me/koduryem/32 Как делать cache на go: ⭐️ https://gist.github.com/idfumg/59580ea70f320fe16973c145dd71ec87 ⭐️ https://gist.github.com/idfumg/e95fc14aaab43280a2a03f1e514d0797 ⭐️ https://gist.github.com/idfumg/cdae8a155e8b9a8da633f993fe5c5e53 Как делать cache на cpp: ⭐️ https://gist.github.com/idfumg/632608b0950c3c581897e366e00b9213 ⭐️ https://gist.github.com/idfumg/3c6f334de0d33285a60eee1e931a8496 Как сделать cache на py: ⭐️ https://gist.github.com/idfumg/9458a06bbdb4b324e7672cd5e530478d Общий чатик: 💬 https://t.me/koduryem_chat #Leetcode #DynamicProgramming #Knapsack

а с чем связано такое обилие рекурсивных задач? Очень много задач имеют рекурсивную природу. Много из них решаются декларативно через рекурсию, просто описывая "что имеем на данный момент => что делаем, исходя из этого". Таким образом, рекурсия - это средство борьбы со сложностью, когда большая задача декомпозируется на более маленькие, которые решить проще и проще до тех пор, пока мы точно не знаем ответ без каких-либо вычислений. И большая задача автоматически "собирается" из всех промежуточных ответов. Таким же образом решается большинство других задач программирования, не связанных с рекурсии (Divide and Conquer и тд). Мы "верим", что вниз по рекурсии более маленькая задача сама знает, как решить себя. То, что нам остается - это убедиться, что каждая итерация ведет к базовому случаю, ответ на который известен. Одно из таким свойств называется Leap of Faith (Link1, Link2, Link3). Я "верю", что следующий шаг рекурсии справится - выполнит эту же логику и передаст дальше вниз по стеку вызовов, а когда пойдет обратно, "соберет" ответы. Много есть алгоритмов, которые работают рекурсивно, деревьев. Одно из популярных - B-Tree (Wiki Link). If the table had 1,000,000 records, then a specific record could be located with at most 20 comparisons: ⌈ log2 (1,000,000) ⌉ = 20. The auxiliary indices have turned the search problem from a binary search requiring roughly log2 N disk reads to one requiring only logb N disk reads where b is the blocking factor (the number of entries per block: b = 100 entries per block in our example; log100 1,000,000 = 3 reads). In practice, if the main database is being frequently searched, the aux-aux index and much of the aux index may reside in a disk cache, so they would not incur a disk read. The B-tree remains the standard index implementation in almost all relational databases, and many nonrelational databases use them too. Например, в Postgresql по дефолту юзается B-Tree, что позволяет мега быстро искать данные и также диапазоны данных (по timestamp, например). Плюс, значительно сокращать доступы к диску, что довольно медленная операция (нам дорого бегать по диску и искать, мы хотим сразу отсекать лишние диапазоны, где точно данных нет). Часто, если делать итеративно, решение может быть более громоздкое и с большим кол-вом багов, разных условий. Но, бывает и наоборот. Многие языки поддерживают tail recursion optimization и некоторые другие оптимизации, разворачивая рекурсию в цикл (lisp, rust, c++). Некоторые языки построены на ней. Обычно требует немного иного декларативного мышления и декомпозиции. В competitive programming люди часто пишут сразу через циклы. Но, все равно надо понимать рекурсию и переходы состояний, просто они часто сразу разворачивают в голове в цикл. Иногда, рекурсия может работать значительно быстрее из-за pruning и отсечения множества веток и просто делая return, которые в циклах нам придется перебирать хотим мы этого или нет. Очень много, а то и полностью рекурсия применяется в c++ template metaprogramming, для выполнения кода на этапе компиляции и создания очень емких и красивых API наших функций или классов. Ее очень много в таких языках, как lisp, если почитать, например SICP. To iterate is human to recurse divine Recursion: ➖ https://t.me/koduryem/13 ➖ https://t.me/koduryem/15 Я вижу по комментам, что не заходит и надо что-то с этим делать ^_^ Сорян, что грузанул вас, народ 🙂

Новое видео со сложной задачей! Еще один формат с рисунками. Если честно, начал сомневаться, стоит ли выкладывать такие сложные или брать полегче. Как-будто в ней слишком много тем учавствуют, по которым надо отдельные видео снимать по часу-полтора и многим может быть не интересно. Даже не смотря на множество рисунков. Думаю, что с этим делать. Может не так жёстко брейнштормить и быстрее к результату идти. Енивей, надеюсь, кому-то будет интересно посмотреть. Не забудьте, что центральное тут - рекурсия и без нее будет очень сложно. По рекурсии есть отдельный ролик. Video: https://www.youtube.com/watch?v=TOdck8cJm48 Problem: https://leetcode.com/problems/minimize-the-total-price-of-the-trips/description/ Recursion: ➖ https://t.me/koduryem/13 ➖ https://t.me/koduryem/15 #Leetcode

Новое видео с задачей! Еще один формат с рисунками. Жду от вас фидбека - понятен ли ход мышления? Делать ли больше примеров в тексте? Делать заготовленные решения прямо с описание моих мыслей в тексте и потом по ним проходить? Или решать и страдать в полу live режиме, как здесь? Стараться все варианты прорешивать, которые возникают в голове или только самый важные или интересные? Что улучшить? Делитесь своими решениями и ходом мыслей. Video: https://www.youtube.com/watch?v=yciiFSnYof0 Problem: Leetcode. Hard. 502. IPO #Leetcode

Новое видео! Пробую еще один формат. Сразу начинаем разбирать заранее последовательно продуманные решения. Жду от вас фидбека - понятен ли ход мышления? Делать ли больше примеров в тексте? Делать заготовленные решения прямо с описанием моих мыслей в тексте и потом по ним проходить? Или решать и страдать в полу live режиме, как здесь? Стараться все варианты прорешивать, которые возникают в голове или только самые важные или интересные? Что улучшить? Делитесь своими решениями и ходом мыслей. Было много мыслей, как сделать лучше, не убивая много времени на реальные графические рисунки. Интересно вам такое вообще? Прожимайте лаки, если интересно здесь и в ютубе. Так буду понимать, стоит ли продолжать решать, улучшать что-то или нет. Video: https://www.youtube.com/watch?v=2gy3FEwMkQY Problem: Leetcode. Hard. 1235. Maximum Profit in Job Scheduling #Leetcode

Новое видео! Пробую новый для меня формат. Жду от вас фидбека - понятен ли ход мышления? Делать ли больше примеров в тексте? Делать заготовленные решения прямо с описанием моих мыслей в тексте и потом по ним проходить? Или решать и страдать в полу live режиме, как здесь? Стараться все варианты прорешивать, которые возникают в голове или только самые важные или интересные? Что улучшить? Делитесь своими решениями и ходом мыслей. Было много мыслей, как сделать лучше, не убивая много времени на реальные графические рисунки. Интересно вам такое вообще? Прожимайте лаки, если интересно здесь и в ютубе. Так буду понимать, стоит ли продолжать решать, улучшать что-то или нет. Алгоритм в конце line sweep Video: https://www.youtube.com/watch?v=vtM4cpI7VZs Problem: Leetcode. Hard. 995. Minimum Number of K Consecutive Bit Flips #Leetcode