Всем привет!
Небольшая статья о нахождении оптимального маршрута
Ян Жабин
@MikeLP
Software Engineer
Гипотеза Колатца
Туториал
Привет, Хабр! В данной статье мы рассматриваем гипотезу Колатца, которая заключается в следующем. Если мы возьмём произвольное число, то нам нужно посмотреть на то, чётное ли оно. Если чётное, то делим на два, если не чётное, то умножаем на 3 и прибавляем 1. Потом с получившимся числом делаем тоже самое. Например возьмём 5. 5 нечётное, значит умножаем на 3 и прибавляем 1. Получаем 16. 16 чётное, значит делим на 2, получаем 8. И так далее. 16->8->4->2->1. А дальше следующее 1->4->2->1->4… . Получаем цикл. Гипотеза Колатца заключается в том, что любое число после некоторого конечного числа операций, превратится в 1, то-есть войдёт в этот цикл. По сути гипотеза неверна в двух случаях, если есть другой цикл, кроме, 1->4->2->1. Или же существует число, которое бесконечно растёт. В данной статье рассказывается об доказательстве гипотезы.
Имплементируем WebSocket протокол на Go
Из песочницы
Статья для тех, кто хочет познакомиться с устройством технологии WebSocket или языком программирования Go.
Или узнать с какой простотой Go стал одним из самых популярных языков программирования для написания сетевых приложений.
Google проложит первый подводный кабель между Азией и Канадой
Google проложит первый подводный сетевой кабель между Азией и Канадой. Кабель Topaz пройдет от Порт-Алберни на западном побережье острова Ванкувер через Тихий океан к Миэ и Ибараки в Японии. Ожидается, что проект завершится в 2023 году.
Почему мьютексы в Rust реализованы именно так
Перевод
Я часто слышу от пробующих работать с Rust системных программистов жалобы на мьютексы и особенно на Rust Mutex API. Жалобы обычно выглядят так:
- Они не хотят, чтобы мьютекс содержал данные, только блокировку.
- Они не хотят управлять «защитным» значением, разблокирующим мьютекс при сбросе, в частности, они просто хотят вызывать операцию
unlock, потому что им кажется, что это более явное действие.
Такие изменения превратили бы Rust mutex API в эквивалент C/Posix mutex API. Однажды я даже видел, как один разработчик пытался использовать
Mutex<()> и разные хитрости, чтобы его имитировать.Однако у такого стремления есть проблема: эти два аспекта
Mutex неразрывно связаны друг с другом, а также с гарантиями безопасности Rust в целом — изменение одного из них или обоих откроет возможности для возникновения незаметных багов и повреждений из-за гонок данных.Использование API мьютексов в стиле C, состоящего из набора косвенно защищаемых данных и из функций
lock и unlock было бы опрометчивым в Rust, потому что это позволяет безопасному коду легко вносить ошибки, нарушающие безопасность памяти и вызывающие гонки данных.Прозвучит спорно, но я утверждаю, что это справедливо и для C. Просто в Rust это более очевидно, поскольку Rust тщательно разделяет понятия «безопасного» кода, в который невозможно внести подобные ошибки, и «небезопасного» кода, в который можно вносить такие ошибки. В C такого разделения нет, и в результате этого использующий мьютексы код на C может тривиальным образом создавать серьёзные баги, которые потенциально можно подвергать эксплойтам.
В этом посте я разберу типичный C mutex API, сравню его с типичным Rust mutex API, и расскажу о том, что произойдёт, если мы изменим Rust API так, чтобы он напоминал C.
Настоящая* перегрузка операторов в JavaScript
Одна из активно реквестируемых фич в JavaScript и TypeScript — перегрузка операторов. Без инфиксной записи, к примеру, получаются очень громоздкими вычисления с векторами или множествами. Тем не менее, используя сильное колдунство некоторые знания о том, как сейчас работают операторы в JavaScript, мы можем реализовать все самостоятельно.
Турель из Portal своими руками
Блог компании RUVDS.com Программирование микроконтроллеров *3D-принтеры DIY или Сделай сам Игры и игровые консоли
Туториал
Перевод
А вы играли в Portal? Даже если нет, сборка личной автоматической турели с детекцией движения и оригинальным голосовым сопровождением наверняка окажется как минимум любопытной, ведь такая диковина может не просто украсить интерьер, но и стать, к примеру, отличным подарком для детей.
Ищем простые числа до триллиона за тридцать минут
Поиск простых чисел — популярная задача среди программистов, увлекающихся математикой. Самый известный алгоритм, придуманный, по-видимому, больше двух тысяч лет назад, — решето Эратосфена; в настоящее время существует бесчисленное множество его вариантов и оптимизаций.
Сегодня я хотел бы поделиться с вами различными вариантами реализации поиска простых чисел на языке C#, начиная с классических алгоритмов — решета Эратосфена, Сундарама и Аткина, и кончая различными оптимизациями (сегментация, факторизация). Особый упор я делал на простоту: самый быстрый из алгоритмов, который мне удалось получить, содержит 120 строк кода и ищет простые числа до триллиона меньше, чем за 30 минут, а до миллиарда — меньше, чем за секунду (это далеко от производительности лучших из существующих библиотек по поиску простых чисел, но эти библиотеки обычно содержат свыше 4000 строк кода).
В заключение мы применим самую быструю реализацию для поиска максимального расстояния между двумя соседними простыми числами до триллиона. Прежде чем заходить под кат, я предлагаю вам попытаться угадать ответ. Для сравнения, для простых чисел до 100 максимальное растояние равно 8 (между соседними простыми числами 89 и 97), а до тысячи — 20 (между 887 и 907).
Весь исходный код можно найти на гитхабе.
15 игр, которые прокачивают логику, алгоритмы, ассемблер и силу земли
Есть «Super Mario», признанная классика видео игр. Есть «Doom», который запускают на чайниках и тестах на беременность. Есть супер-популярные по статистике twitch.tv игры («League of Legends», «GTA V», «Fortnite», «Apex Legends») которые стримят пятая часть всех стриммеров.
А есть игры, на которые очень мало обзоров, но они супер крутые — игры про алгоритмы. Игры, в которых можно кодить на ретро-компьютере; игры, которые надо взламывать; игры, где можно программировать контроллеры или поведение персонажей; игры, где можно создавать свою игру внутри игры.
Под катом подборка классных игр про алгоритмы за последние 10 лет. Если что-то упустила — буду рада дополнениям.
Еще я создала канал в Telegram: GameDEVils, буду делиться там клевыми материалами (про геймдизайн, разработку и историю игр).Ещё 20+ игр, которые прокачивают логику, алгоритмы и радуют умный мозг [по следам комментариев на Habr]
Я выложила вчера подборку «15 игр, которые прокачивают логику, алгоритмы, ассемблер и силу земли». И столько классных ссылок в комментарии накидали, что я чуток опухла, но сделала отдельную подборку, по горячим следам. Спасибо большое всем, кто внес свой вклад.
Еще я веду канал в Telegram: GameDEVils, делюсь там клевыми материалами (про геймдизайн, разработку и историю игр).Хватит совать в детей интерфероны
Интерфероны? Да в задницу их!
Это, как многие думают, концентрат иммунитета. Коротко — нет.
Что происходит:
Изначально этот класс белков случайно открыли в 1957 году вирусологи Алик Айзекс и Жан Линдеман. У них возникла проблема с мышами, которые не заболевали при введении вируса. Как выяснилось позже, причина была в том, что эти мыши уже болели другой вирусной инфекцией, что приводило к выбросу белков ранее неизвестного класса — интерферонов. Поначалу казалось, что наконец найдено универсальное решение против вирусных болезней, но, как обычно, дальнейшие исследования выявили множество ограничений. Например, при введении серьёзных дозировок интерферона альфа можно получить жёсткую депрессию, биполярное расстройство и другие ментальные нарушения вплоть до бреда и галлюцинаций.
Поэтому сегодня я попробую объяснить, почему этот класс препаратов вовсе не добрые капельки от гриппа, а серьёзное лечение с кучей побочных эффектов. Ну и бесполезность введения его в нос и per rectum тоже затронем.
Это, как многие думают, концентрат иммунитета. Коротко — нет.
Что происходит:
- Ребёнка с симптомами ОРВИ приводят к педиатру.
- Педиатр прописывает витамин С, разбавленный сахар и интерферон в форме ректального суппозитория. Если витамин С и дорогой сахар в целом безопасны, то вот с интерфероном это далеко не так.
- Уровень интерферона в крови — это сложнейшая система, дающая сигнал к запуску процесса иммунного ответа, связующее звено врождённого и приобретённого иммунитета, но добавление интерферона в организм не означает, что иммунитет будет «сильнее». Упрощая, интерфероны тормозят работу заражённых клеток и дают другим клеткам вокруг поражённой вирусом сигнал, что произошло вторжение, останавливают деление вируса внутри клетки и стимулируют работу Т- и В-лимфоцитов. Так же они способны влиять на деление клеток, что важно при онкологии, например.
Изначально этот класс белков случайно открыли в 1957 году вирусологи Алик Айзекс и Жан Линдеман. У них возникла проблема с мышами, которые не заболевали при введении вируса. Как выяснилось позже, причина была в том, что эти мыши уже болели другой вирусной инфекцией, что приводило к выбросу белков ранее неизвестного класса — интерферонов. Поначалу казалось, что наконец найдено универсальное решение против вирусных болезней, но, как обычно, дальнейшие исследования выявили множество ограничений. Например, при введении серьёзных дозировок интерферона альфа можно получить жёсткую депрессию, биполярное расстройство и другие ментальные нарушения вплоть до бреда и галлюцинаций.
Поэтому сегодня я попробую объяснить, почему этот класс препаратов вовсе не добрые капельки от гриппа, а серьёзное лечение с кучей побочных эффектов. Ну и бесполезность введения его в нос и per rectum тоже затронем.
Как компьютеры рисуют странные формы: метаболы, marching squares, электрические поля
Перевод
Пару месяцев назад я наткнулся на очень красивые анимации. В основе этих анимаций лежат несколько простых окружностей, но выделяет их то, насколько органично они сливаются друг с другом. Мне стало любопытно, как это работает, и моё исследование оказалось гораздо интереснее, чем я ожидал. Выяснилось, что соединяющиеся друг с другом круглые объекты называются метаболами (metaballs) и с ними связано множество математических и вычислительных понятий. Если вы в чём-то похожи на меня, то посмотрев на эти анимации, вы бы сразу задались вопросом, как подойти к решению такой задачи. Допустим, нам поручили разобраться с тем, как генерировать метаболы. Как сформулировать эту задачу? Что означает возможность органичного слияния окружностей? Как компьютер рендерит нечто подобное на экране? Всё это очень сложные вопросы.
В этой статье мы совершим путешествие и узнаем, как люди решают эту задачу. Базовый алгоритм, играющий неотъемлемую роль в генерации таких анимаций, называется marching squares. Он используется во многих сферах графики, а также медицинской визуализации. Но каким бы полезным ни был алгоритм, самым важным в нашем путешествии будет то, насколько изящен этот подход при решении подобной задачи. Есть истинная красота в том, что мы берём расплывчатую задачу и преобразуем её в конкретный решаемый вид. Главная цель этой статьи — дать вам ощущение радости при исследовании смены точек зрения, превращающих подобные сложные задачи в решаемые.
Рекомендательные системы: проблемы и методы решения. Часть 1
Привет! Я хочу рассказать вам о рекомендательных алгоритмах. Мы в Prequel создаем фильтры и эффекты для редактирования фото и видео. Создаем давно, и постепенно этих эффектов стало очень много. А с ними и пользовательского контента. Мы захотели помочь с выбором из этого многообразия, для чего нам и понадобилась система рекомендаций. Если масштабы вашей системы такие, что пользователям сложно в ней ориентироваться, возможно, что рекомендации могут помочь и вам.
Задуманный систем оказался слишком объемным для одной статьи, поэтому мы разбили его на две части. Перед вами первая, она посвящена постановке задачи и базовым методам решения. В этой части мы разберем коллаборативные модели от матричного разложения (на примере ALS) до neural collaborative filtering. Кроме того, будет небольшой обзор метрик и техник борьбы с проблемой холодного старта.
Анатомия рекомендательных систем. Часть первая
Я работаю дата-саентистом в компании CleverDATA. Мы занимаемся проектами в области машинного обучения, и один из наиболее частых запросов на разработку основанных на машинном обучении маркетинговых решений — это разработка рекомендательных моделей.
В данной статье я расскажу о рекомендательных системах, постараюсь дать максимально полный обзор существующих подходов и на пальцах объясню принципы работы алгоритмов. Часть материала базируется на неплохом курсе по рекомендательным системам лаборатории MovieLens (которая большинству знакома по одноименному датасету для тестирования рекомендаций), остальное – из личного опыта. Статья состоит из двух частей. В первой описана постановка задачи и дан обзор простых (но популярных) алгоритмов рекомендаций. Во второй статье я расскажу о более продвинутых методах и некоторых практических аспектах реализации.
Источник
В данной статье я расскажу о рекомендательных системах, постараюсь дать максимально полный обзор существующих подходов и на пальцах объясню принципы работы алгоритмов. Часть материала базируется на неплохом курсе по рекомендательным системам лаборатории MovieLens (которая большинству знакома по одноименному датасету для тестирования рекомендаций), остальное – из личного опыта. Статья состоит из двух частей. В первой описана постановка задачи и дан обзор простых (но популярных) алгоритмов рекомендаций. Во второй статье я расскажу о более продвинутых методах и некоторых практических аспектах реализации.
Использование потоков WebAssembly из C, C++ и Rust
Перевод
Поддержка многопоточности стала одним из важнейших апгрейдов производительности в WebAssembly. Она позволяет выполнять либо части кода на разных ядрах параллельно, либо один код для независимых элементов входных данных, масштабируя его на максимально доступное пользователю число ядер. Все это значительно сокращает общее время выполнения.
В этой статье вы узнаете, как использовать потоки WebAssembly для переноса многопоточных приложений, написанных на языках C, C++ и Rust, в веб-среду.
В поисках упорядоченного множества в Python: разбираемся с теорией и выбираем лучшую реализацию
Множество (Set) — структура данных, которая позволяет достаточно быстро (в зависимости от реализации) применить операции add, erase и is_in_set. Но иногда этого не достаточно: например, невозможно перебрать все элементы в порядке возрастания, получить следующий / предыдущий по величине или быстро узнать, сколько элементов меньше данного есть в множестве. В таких случаях приходится использовать Упорядоченное множество (ordered_set). О том, как оно работает, и какие реализации есть для питона — далее.
RBAC? ABAC?.. PERM! Новый подход к авторизации в облачных веб-службах и приложениях
Туториал
Данная статья преследует цель рассказать о новом походе к авторизации в облачных решениях, в основе которого лежит использование интерпретируемого языка определения политики управления доступом — который называется языком моделирования PERM (PML). Данный язык можно использовать для выражения различных моделей управления доступом, таких как список управления доступом (ACL), управление доступом на основе ролей (RBAC), управление доступом на основе атрибутов (ABAC) и других. А также рассказать о практическом воплощении этого подхода в виде конкретной реализации кросс-языковой библиотеки авторизации Casbin
Используем GPU для повышения производительности JavaScript
Перевод
Мы, разработчики, всегда стремимся искать возможности повышения производительности приложений. Когда речь идёт о веб-приложениях, то улучшения обычно вносятся только в код.
Но думали ли вы об использовании мощи GPU для повышения производительности веб-приложений?
В этой статье я расскажу о библиотеке ускорения JavaScript под названием GPU.js, а также покажу вам, как повысить скорость сложных вычислений.
Что такое GPU.js и почему его стоит использовать?
Если вкратце, GPU.js — это библиотека ускорения JavaScript, которую можно использовать для любых стандартных вычислений на GPU при работе с JavaScript. Она поддерживает браузеры, Node.js и TypeScript.
Кроме повышения производительности есть и множество других причин, по которым я рекомендую использовать GPU.js:
- В основе GPU.js лежит JavaScript, что позволяет использовать синтаксис JavaScript.
- Библиотека берёт на себя задачу автоматической транспиляции JavaScript на язык шейдеров и их компиляции.
- Если в устройстве отсутствует GPU, она может «откатиться» к обычному движку JavaScript. То есть вы ничего не потеряете, работая с GPU.js.
- GPU.js можно использовать и для параллельных вычислений. Кроме того, можно асинхронно выполнять множественные вычисления одновременно и на CPU, и на GPU.
Учитывая всё вышесказанное, я не вижу никаких причин не пользоваться GPU.js. Давайте узнаем, как его освоить.
Прямоугольные тайловые миры
Туториал
Тайлы - пожалуй один из самых удобных способов построения игровой логики. Все происходит максимально дискретно, никаких тебе физик с просчетом коллизий и прочими трудностями.
Огромное множество игр на самом деле содержат тайлы - так просто проще представлять игровой мир. Такая упорядоченность помогает геймдизайнерам строить игровые механики, упрощает жизнь художников и делает код программистов понятнее. Самих видов тайлов тоже огромное количество - сегодня поговорим о прямоугольных и изометрических.
Какие CSS-генераторы можно использовать в 2021 году
Перевод
CSS генераторы экономят время и сокращают количество ошибок в коде. Они позволяют автоматизировать многие задачи, которые опытным верстальщикам или фронтендерам уже кажутся скучными. В то же время, они могут облегчить работу над задачами, которые сложны для начинающих специалистов.
Схема работы таких генераторов проста: достаточно ввести через простой визуальный интерфейс нужные вам параметры и на выходе получить готовые CSS-стили. Далее полученный код нужно скопировать и добавить в свой проект.
Известный full-stack разработчик Марко Денич предлагает свою подборку лучших CSS-генераторов. Возможно, о каких-то из них вы не знали, и, познакомившись с ними сейчас, начнёте использовать в работе.