Алгоритмы *

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

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

2) не париться с limiter и анализировать ответ от внешнего источника данных и на основе его ответов, принимать решение когда и сколько запросов можно отправить (но такие ответы есть не у каждого сервиса и существует вероятность, что будут отправлены лишние запросы, что может привести к бану)

3) хранить историю запросов локально, но использовать алгоритм leaked bucket, но это не позволяет накидать несколько запросов и ждать

4) хранить историю запросов локально, но использовать алгоритм sliding window, можно накидать запросов и ждать какое-то известное время

О реализации sliding window для java пойдет речь в этой статье.

Всем привет! Меня зовут Хусрав, я бэкенд разработчик в компании Bimeister.

В этой статье я бы хотел бы поговорить о способе поиска родительских и дочерних элементов структуры посредством PostgreSQL Materialized Path.

Статья является вводной и рассчитана на людей, незнакомых с темой.

Алгоритм бинарного (или двоичного) один из базовых алгоритмов, которые часто используется при решении алгоритмических задач. На LeetCode на момент написания этой статьи порядка 190 задач в решении которых он используется (можно посмотреть это здесь: https://leetcode.com/tag/binary-search/). Бинарный поиск разбирается во множестве статей, его идея достаточно несложная и интуитивно понятная. Однако алгоритм имеет некоторое количество "подводных камней". В этой заметке я хотел бы показать решение одной из задач с его помощью.

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

Суффиксное дерево (Suffix Tree, ST) – это структура данных, которая позволяет "проиндексировать" строку за линейное время от её длины, чтобы потом быстро находить подстроки (за время О(длина искомой подстроки)).

Тема построения Suffix Tree и его применения хорошо раскрыта в Интернет (википедия, статья на хабр про алгоритм Вейнера, язык Си, и статья на хабр про алгоритм Укконена). Но всегда есть соблазн поучаствовать в соревновании "написать проще и яснее", хотя шансов мало. Тем не менее, рискну.

Несмотря на сложность, алгоритм построения ST умещается в 35 строк на python (см. ниже метод _build_tree). Их буквально можно выучить и воспроизводить по памяти как некое произведение искусства, как воплощенный в набор символов труд человеческой мысли, причём не одного человека, и первые из них точно гении. :) Есть соблазн, всматриваясь в код, прикоснуться к великому и чему-то научиться.

С вашим языком программирования все в порядке — он просто производит вычисления с плавающей запятой. Изначально компьютеры могут хранить только целые числа, так что им нужен какой-то способ представления десятичных чисел. Это представление не совсем точное. Именно поэтому, чаще всего, 0.1 + 0.2 != 0.3.

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

Предлагаем хабрасообществу наш перевод этого материала. Обращаем ваше внимание, что позиция автора не всегда может совпадать с мнением МойОфис.

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

В этой статье мы поговорим о том, зачем вообще их нужно знать веб-разработчикам, и затронем тему оценки сложности алгоритмов и Big O нотации.

Зачем мне алгоритмы? Я фронтендер!

Вы наверняка задумались: «А зачем мне нужно тратить своё время на изучение этих сложных алгоритмов, если я работаю с фронтендом? Как знание графов и бинарных деревьев поможет мне лучше отцентровать одну div-ку внутри другой div-ки?»

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

Многие веб-разработчики на таких форумах, как Reddit и Stack Overflow, отмечали, что, освоив даже на базовом уровне эти фундаментальные основы программирования, чувствовали себя увереннее, профессиональнее и писали более чистый и структурированный код.

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

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

Ведь они ищут лучших из лучших, и знание алгоритмов как раз делает вас лучше как разработчика. Тем более, лучше инвестировать свое свободное время в новые знания и навыки, чем в сериалы на Netflix.

И на этой прекрасной ноте давайте перейдем к основной теме статьи.

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

Здесь описан алгоритм мозга, который с небольшими вариациями управляет разнообразными мыслительными процессами и все наше мышление есть по сути его комбинации. Я предполагаю, что он соответствует созданному эволюцией алгоритму разума, так как он простой и универсальный. Проявления этого алгоритма участвуют, как в распознавании картинки, так и в мышлении.

Вывод HTML-дерева из локального файла в окно программы-оболочки «Windows PowerShell» версии 5.1 (или в окно программы-оболочки «PowerShell» версии 7) с помощью скрипта на языке PowerShell в операционной системе «Windows 10». Используется библиотека «HTML Agility Pack».

В качестве упражнения в алгоритмах и структурах данных рассмотрено несколько способов обхода и вывода HTML-дерева: NLR (прямой с приоритетом обхода потомков слева направо), NRL (прямой с приоритетом обхода потомков справа налево), LRN (обратный). Примеры практической реализации.

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

С докладами технического трека Positive Hack Days 11 мы вас уже познакомили, настал черед трека, посвященного проблематике искусственного интеллекта и машинного обучения. AI-трек шел всего день, зато как: вместе с экспертами из «Ростелекома», Security Vision, Bloomtech LLC и других известных компаний мы поговорили о биометрических алгоритмах обнаружения витальности в Единой биометрической системе, о том, как компаниям обмениваться данными, не обмениваясь ими, и о том, какие методы машинного обучения помогают в выявлении сетевых атак. Делимся докладами, которые «зашли» участникам форума больше всего.

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

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

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

Не так давно я захотел написать свой шахматный движок. На удивление в Интернете нашлось не так много хороших статей на эту тему. Были статьи с довольно слабыми программами, многие из которых даже умудрялись пропускать некоторые важные правила. А были статьи с хорошими программами (некоторые из них были даже чуть лучше чем получилось у меня в итоге), но там авторы рассказывали лишь основные идеи, пропуская подробности, из-за чего написать что-то свое по таким статьям было проблематично. Поэтому после написания своей программы, я решил написать статью, дабы облегчить жизнь интересующимся в данной теме. Я не претендую на лучшую шахматную программу или на чистейший код, но эта статья будет хорошим и легким началом для тех, кто хочет написать что-то свое.

По этой ссылке приложение для поиска по датасету Open Images and Places 365 (3.5 миллиона картинок)

Загружаете свою картинку - получаете 18 похожих.

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

Как написать программу, чтобы победить на конкурсе плохого кода? Этот вопрос я задал сам себе, когда прочёл о необычном челлендже на форуме reddit. Да, вы правильно поняли. Это статья не о чистом коде и правильных тестах. Но здесь не будет и речи о плохом, заурядно плохом коде, том коде, который мы очень часто видим в наших проектах. Я расскажу об экстремальном, невообразимом, гениально плохом коде, коде, который использует те возможности джавы, о которых вы, скорее всего, и не догадывались, и те приёмы, которые вы никогда не встретите в обычных проектах. Сможете ли вы использовать эти приёмы на практике? Думаю, нет. Если вы прагматичный человек, то сэкономите своё время и остановитесь. Не читайте эту статью. Однако если вы хотите немного отвлечься от повседневной рутины, увидеть и узнать что-то новое о нашем любимом языке Java, - милости просим!