Чтобы уверенно пересечь незнакомую местность, можно или двигаться быстрее, или подыскивать удобную дорожку. Другими словами, слишком пристальное внимание к скорости как таковой может вас притормозить. То же касается и разработки программного обеспечения.
Алгоритмы *
Все об алгоритмах
Новости
Как улучшить распознавание скелетов в MediaPipe
Я очень люблю скелетные детекторы из Mediapipe. Чтобы запустить их нужно всего несколько минут. Работает на разных платформах (мобильные, pc, embedded, и.т.д.). И выдает достаточное качество для многих применений.
Но надо признать что не всюду его можно брать и использовать. Давайте я расскажу как небольшими силами можно его улучшить. Приведенная тут логика будет построена вокруг Mediapipe, но она им не ограничена. Применяя аналогичные подходы можно улучшить практически любой скелетный алгоритм.
Генетический алгоритм поиска решения для задачи по выбору планировок этажа многоквартирного дома
Предложенный алгоритм - это очень ранний прототип рабочей версии. Суть публикации познакомить всех желающих с возможностями генетических алгоритмов в различных сферах бизнеса.
Как мы выбирали консенсус для энтерпрайз-блокчейна
Любому блокчейн-проекту, который рассчитывает на успех, стоит думать, что он будет с этим успехом делать. Больше пользователей, больше транзакций, больше нагрузка на сеть — рано или поздно встанет вопрос о масштабировании. В этом посте мы расскажем, куда нас привели вопросы масштабирования, согласованности и почему мы не взяли на вооружение какой-нибудь готовый консенсус.
«Божественная комедия», или Девять кругов прогнозирования промоспроса в «Магните»
Привет, Хабр! На связи команда направления прогнозирования промо в «Магните». В предыдущей статье «Магнитная аномалия: как предсказать продажи промо в ритейле» мы дали читателю общее представление о том, чем занимается наша команда. Теперь поговорим о конкретных сложностях и методах их решения, с которыми нам приходится сталкиваться в работе.
Чтобы лучше разобраться во внутренней кухне, предлагаем читателю вместе прогуляться по нашим «девяти кругам прогнозирования промо спроса».
Грокаем алгоритмы
Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих от Бхаргава А. Эта книга рекомендована Яндекс Практикум при подготовке к алгоритмическому собеседованию. Сам автор указывает, что книга для самоучек, студентов, выпускников и тех, у кого программирование не является основным профилем.
Мое впечатление неоднозначно. С одной стороны, до сего момента я не встречал описания динамического программирования, поиска кратчайшего пути в графе по алгоритму Дейкстры и использование K ближайших соседей для классификации и аппроксимации (возможно, все это есть в 4м или последующих томах Кнута, но в магазине они мне не встречались). С другой стороны, описания и примеры, приведенные в книге, таковы, что практической пользы не представляют. Описания очень поверхностны, примеры нарочно примитивны, код в половине случаев не приведен. Но даже там где есть код, он нарочито упрощен под конкретный пример и на практике бесполезен.
Казалось бы, есть масса книг - каталогов шаблонов. Они реально полезны и новичку и профессионалу. Эта книга не из их числа. Но, видимо, это и не было целью. Напоминает научно-популярные книги издававшиеся в СССР: простым языком рассказывает о сложных вещах, прививает у читателя интерес к теме, расширяет кругозор. Не более. Но тоже важно.
Вернемся к Яндекс Практикум и их рекомендации. Если алгоритмы так важны, то почему именно эта книга? Есть масса других, где и алгоритмов больше и разобраны они так, что бери да пользуй. Например, классический труд Д. Э. Кнута Искусство программирования. Да, рисунки в детском стиле в Грокаем алгоритмы забавны. Но иллюстрации в Искусство программирования полезны для понимания. Разве это не важнее, если уж кандидата посылают на алгоритмическое собеседование?
Алгоритмы на кристалле. Глава 1: Вычислительная модель
Возможно, в вашем браузере с первого раза не будут правильно отображаться формулы. Если так, попробуйте перезагрузит страницу — на моем компьютере этот фокус работает
Пара слов о том, что мы будем изучать.
На фотографии ниже представлена электронная схема в том масштабе, на котором мы привыкли их видеть невооруженным взглядом. Множество всяких квадратных и не очень блочков с торчащими из них проволочными ножками (пинами), сеть проводящих металлических дорожек, к которым своими ножками припаяны блочки, покрывающая плату затейливым узором. Современные цифровые схемы на кристалле концептуально представляют из себя примерно тоже самое, однако их строение не получится разглядеть без микроскопа.
Какая-то плата. Источник фото ukrmarket.net
В общих словах работу цифровой схемы можно описать так: дорожки соединяют выходные пины одних блочков с входными пинами других. С некоторой периодичностью по дорожкам распространяются электрические импульсы от выходных пинов, где они, собственно, и зарождаются, к входным. Обычно каждый такой импульс кодирует одно из двух значений: логические ноль или логическую единицу. Значение импульсов, которые за текущий такт породит блочок на своих выходных пинах, зависят от конструкции блочка и того, какими были значения импульсов, пришедших на его входные пины за все предыдущие время.
Конечно, чтобы уметь проектировать микросхему и потом быть в состоянии рассуждать о ее работе, нам потребуется какая-то более-менее точная теория. Созданием такой теории мы сейчас и займемся. Если кто-то из читателей переживает, что он не знает или забыл, где у транзистора база, а где эмиттер, я спешу его успокоить – эти знания нам даже не понадобятся. Рассуждения в книге будут относиться к концептуально более простому и высокому уровню: уровню логических блоков.
Почему программистам нужно знать структуры данных и как я сэкономил компании $22 000 в год
Как я оптимизировал аналитику используя структуры данных. Что в итоге сэкономило $22 000
Изящное шестистраничное доказательство. Как возникают случайные структуры
Двое молодых математиков ошеломили коллег, представив полное доказательство гипотезы Кана-Калаи — обобщающее утверждение о том, как возникает структура в случайных множествах и графах.
Когда математики Джефф Кан и Гиль Калаи в 2006 году впервые выдвинули свою гипотезу о «пороге ожидания», они сами в нее не поверили. Их тезис – широкое утверждение о природе математических объектов, именуемых «случайными графами» — казался слишком категоричным, слишком всеобъемлющим, слишком смелым, чтобы претендовать на истинность. Казалось, что он скорее выдает желаемое за действительное, чем отражает математическую истину. Даже с такими оговорками, никто не смог опровергнуть эту гипотезу, и она быстро стала одной из важнейших нерешенных задач в своей области.
Теперь, более 15 лет спустя, двое молодых математиков из Стэнфордского университета сделали то, что, по мнению Кана и Калаи, граничит с невозможным. В В на удивление кратком препринте, выложенном в онлайне всего несколько недель назад, Джинён Пак и Гью Туан Фам дали полное доказательство этой гипотезы.
«Оно получилось поразительно простым и изобретательным», — сказал Калаи, — «Завораживающим. Чудесным».
Найти за полсекунды: сравниваем похожие фотографии
Привет, меня зовут Петр и я работаю в Badoo в команде биллинга. В этой статье я хочу поделиться своим опытом работы над пет-проектом по созданию хранилища фотографий с возможностью поиска дубликатов. Я расскажу, с каким багажом я вошел в этот проект, в чем заключалась задача и как её решал. В конце поделюсь результатами и почему я считаю, что это один из лучших проектов, которым я занимался.
Однажды мои знакомые попросили сделать им хранилище изображений для их проекта по модерации внешних ресурсов. Условия: срок хранения до трех лет, фотографии при этом присылаются неравномерно, в среднем поток — 150.000 картинок в сутки.
Казалось бы, достаточно банальная задача. Если бы не еще одно условие: хорошо бы сопоставлять фотографии с уже имеющимися: искать дубликаты и помечать их.
Строковые алгоритмы на практике. Часть 3 — Алгоритм Рабина — Карпа
Сегодня мы разберем хитроумный и нетривиальный алгоритм поиска подстроки в строке. Он основан не на сравнении символов, а на сравнении чисел. Я уже писал, что основная моя цель это не написать простой разбор алгоритмов, а посмотреть их эффективность, какие-то интересные места и сравнить их производительность между собой.
И сегодня есть что посмотреть.
Знакомство со стековыми графами
В декабре 2021 года Github объявил, что открывает общий доступ к точной навигации по коду для всех публичных и приватных репозиториев с Python на сайте GitHub.com. Точную навигацию в коде обеспечивают стековые графы, новый фреймвввооорк с открытым исходным кодом, созданный в Github и позволяющий устанавливать правила привязки имен для языка программирования при помощи декларативного предметно-ориентированного языка (DSL). Стековые графы позволяют генерировать данные о навигации по стеку для конкретного репозитория, не требуя при этом какого-либо участия в конфигурировании со стороны владельца репозитория и не вмешиваясь в процесс сборки или другие задания, связанные с непрерывной интеграцией. В этом посте будет подробно рассказано, как работают стековые графы, и как с их помощью достигаются такие результаты.
(Этот пост написан на основе доклада, прочитанного автором на конференции Strange Loop в октябре 2021 года. Есть видео с этим докладом, там рассказано гораздо больше!)
Алгоритмы на кристалле (анонс книги)
Пол первой главы
Нет, этот шаг – не безумие, но моя попытка бороться с ним. Попытка сконцентрироваться на чем-то разумном, заставить свой мозг снова думать, преодолеть моральную травму и начать хоть как-то смотреть в будущее. Быть может, этот труд станет лекарством не только для меня.
О чем и для кого эта книга
Я собираюсь рассказать об удивительном мире, где для решения любой алгоритмической задачи вы имеете право построить какую-угодно вычислительную машину и как угодно по своему желанию ее запрограммировать. Больше никаких чужих правил, чужих архитектур и чужих языков программирования – полная свобода фантазии и изобретательства. Это мир, в котором вы сами решаете, какую именно микросхему реализовать на полупроводниковом кристалле. Чтобы вам в этом помочь, я постарался собрать некий базовый набор приёмов того, как проектировать эффективные логические цифровые схемы.
Основной акцент повествования сделан на математическую и алгоритмическую стороны решаемых задач. Это скорее не «еще одно» руководство по проектированию электронных схем, а учебник по очень специфическому способу реализации алгоритмов. Я надеюсь, что его содержание заинтересует и увлечет широкий круг любителей математики и программирования, даже если они раньше никогда и не сталкивались с разработкой микросхем. В то же время я старался подобрать материал так, чтобы и типичный hardware-разработчик мог легко в нем разобраться и с пользой применить в своем ремесле.
Лучший технический вопрос, который мне задавали на собеседовании
Много воды утекло с тех пор, как я в последний раз участвовал в собеседовании по программированию как соискатель. Но до сих пор помню особенно полюбившийся мне вопрос с такого собеседования. Дело было в MemSQL, году так в 2013. (Они даже успели переименоваться, поэтому, полагаю, конкретно этот вопрос они на собеседовании уже не задают. Не чувствую вины за то, что выдаю его. Это отличная история, которая также кажется мне поучительной; просто раньше я о ней никогда не писал).
Окей, вообще, это даже не вопрос как таковой, это программерская задачка на засыпку. Не помню, сколько времени мне на нее дали. Скажем, три часа, считая время, потребовавшееся на постановку задачи.
Поскольку компания MemSQL разрабатывала базу данных, этот челлендж из той же оперы.
Proof-of-work — лучший выбор консенсуса для Bitcoin
Какой консенсус лучше для блокчейна, proof-of-work или proof-of-stake? Многие спорят об этом и приводят разные аргументы. В этой статье я рассмотрю основные преимущества и недостатки каждого варианта.
Это перевод поста из блога Bitcoin, дополненный комментариями наших экспертов. Эти комментарии выделены курсивом.
Модификации сортировки пузырьком
Написав предыдущую статью о сортировке подсчётом beSort - меня не отпустило. Я решил поковыряться в базовых алгоритмах и залип на модификациях пузырьковой сортировки, ну а статья о том - что из этого получилось.
Формирование однородных групп для сплит-тестирования. Реализация на Python
Всем привет! Если перед вами стоит задача проведения А/Б тестирования, то я помогу вам понять, как с помощью python сформировать однородные группы с помощью алгоритмов сходства объектов на основе косинусного и взвешенного косинусного расстояния для его проведения.
Аддитивная композиция натуральных чисел и её интересные свойства
Любое натуральное число можно выразить через уникальное множество простых чисел, перемножение которых даёт исходное число. Для простых чисел это множество состоит из одного элемента – самого этого числа. Такую композицию можно называть мультипликативной, она очень хорошо известна и изучена.
В статье предлагается способ выразить натуральное число через уникальное множество простых чисел (включая единицу), сложение которых даёт исходное число. Такую композицию будем называть аддитивной, и она ранее не предлагалась.
При работе над статьёй была посчитана композиция чисел до одного триллиона. Данный расчёт дал довольно интересные результаты, изложенные в статье. Возможно, обсуждение этих результатов поможет сделать дальнейшие выводы, пригодные для публикации в научном журнале.
Обход графа в ширину (BFS) и глубину (DFS)
Задумка данного поста заключается в том, чтобы коротко и ясно объяснить как работают на графах обход в ширину и обход в глубину. То есть целью поста в первую очередь является понимание, а не детали реализации в коде, хотя псевдокод будет также приложен. Надеюсь данный пост поможет получить хотя бы примерное понимание происходящего.
Сказка про Guid.NewGuid()
C#. Guid.NewGuid()
. Linux. Windows. Randomness or Uniqueness. RNG and PRNG. Performance. Benchmarking.
Цель нашей сегодняшней сказки — развлечься как следует. Детективная история в поисках потерянного перфоманса с красивым финалом и эффектным результатом непосредственно связана с набором слов из предыдущего абзаца.
Вклад авторов
-
alizar 2691.5 -
ZlodeiBaal 1426.0 -
agorkov 1345.0 -
Fil 1280.0 -
Leono 1086.0 -
YUVladimir 1037.0 -
valemak 1014.0 -
mephistopheies 996.0 -
haqreu 958.0 -
Zalina 922.0