Алгоритмы *

Тихо и незаметно (с), вышел Python версии 3.5! И, безусловно, одно из самых интересных нововведений релиза является новый синтаксис определения сопрограмм с помощью ключевых слов async/await, далее в статье об этом.

Поверхностный просмотр «PEP 0492 — Coroutines with async and await syntax» поначалу оставил у меня вопрос «Зачем это надо». Сопрограммы удовлетворительно реализуются на расширенных генераторах и на первый взгляд может показаться, что все свелось к замене yield from на await, а декоратора, создающего сопрограмму на async. Сюда можно добавить и возникающее ощущение, что все это сделано исключительно для использования с модулем asyncio.

Но это, конечно же, не так, тема глубже и интереснее.

Какую бы вы назначили цену за проживание незнакомцев в вашем доме? Или сколько вы сами заплатили бы за то, чтобы пожить у кого–то? Вы заплатили бы больше или меньше, будь это спланированный отпуск или спонтанная поездка?
Не так просто ответить на все эти вопросы. В своё время мы столкнулись с тем, что заставляя арендодателей и пользователей отвечать на них, мы тем самым уменьшали активную базу данных жилья. Собирая фокус–группы мы наблюдали за тем, как люди вносят своё жильё в список доступных для аренды мест на нашем портале. И большинство застревали, когда нужно было назначить стоимость. Многие начинали смотреть, какие цены установлены на жильё поблизости, открывая в браузере кучу вкладок и пытаясь сравнивать своё предложение с аналогичными. Кто–то уже приходил, имея определённую цель, может быть, чтобы немного заработать на оплату ипотеки или оплату отпуска. Такие люди устанавливали цену исходя из своих заранее обдуманных целей, без учёта реальной ситуации на рынке. А некоторые, к сожалению, просто сдавались и не указывали стоимость аренды их жилья.

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

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

Введение

В былые времена я увлекался компьютерной графикой, как 2х так и 3х мерной, в том числе математическими визуализациями. Что называется just for fun, будучи студентом, написал программу визуализирующую N-мерные фигуры, вращающиеся в любых измерениях, хотя практически меня хватило только на определение точек для 4-D гиперкуба. Но это только присказка. Любовь к геометрии осталась у меня с тех пор и по сей день, и я до сих пор люблю решать интересные задачи интересными способами.
Одна из таких задач попалась мне в 2010 году. Сама задача достаточно тривиальна: необходимо найти, пересекаются ли два 2-D отрезка, и если пересекаются — найти точку их пересечения. Более интересно решение, которое, я считаю, получилось достаточно элегантным, и которое я хочу предложить на суд читателя. На оригинальность алгоритма не претендую (хотя и хотелось бы), но в сети подобных решений я найти не смог.

Многие документы содержат защитные элементы, такие как голограммы, водяные знаки, гильош и т.д. В процессе сканирования таких документов возникает проблема — защитные элементы мешают системам распознавания (OCR). При разработке Smart PassportReader мы провели исследование, направленное на поиск и устранение подобных защитных элементов с изображений документов.



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

Как и в прошлый раз, для этого будет использоваться преобразование Фурье.

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

Скажу пару слов об этой научной задаче: необходимо было произвести расчет динамики биологических микротрубочек на временах порядка минуты. Расчеты представляли собой вычисления с использованием молекулярно-механической модели микротрубочки, разработанной в научной группе. Планировалось, что на основе полученных результатов вычислений можно будет сделать вывод о механизмах динамической нестабильности микротрубочек. Необходимость в использовании ускорителя была обусловлена тем фактом, что минута эквивалента достаточно большому количеству расчетных шагов (~ 10 ^ 12) и, как следствие, большому количеству времени, затрачиваемому на вычисления.

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

В качестве базовой архитектуры проекта был использована архитектура с поддержкой DMA передач. Как компонент этого вычислительной платформы необходимо было реализовать IP ядро, которое способно было бы генерировать новое псевдослучайное нормально распределенное число типа float каждый такт и занимало бы как можно меньше ресурсов на ПЛИС.

Реляционные базы данных (РБД) используются повсюду. Они бывают самых разных видов, от маленьких и полезных SQLite до мощных Teradata. Но в то же время существует очень немного статей, объясняющих принцип действия и устройство реляционных баз данных. Да и те, что есть — довольно поверхностные, без особых подробностей. Зато по более «модным» направлениям (большие данные, NoSQL или JS) написано гораздо больше статей, причём куда более глубоких. Вероятно, такая ситуация сложилась из-за того, что реляционные БД — вещь «старая» и слишком скучная, чтобы разбирать её вне университетских программ, исследовательских работ и книг.

На самом деле, мало кто действительно понимает, как работают реляционные БД. А многие разработчики очень не любят, когда они чего-то не понимают. Если реляционные БД используют порядка 40 лет, значит тому есть причина. РБД — штука очень интересная, поскольку в ее основе лежат полезные и широко используемые понятия. Если вы хотели бы разобраться в том, как работают РБД, то эта статья для вас.

Для автомобилистов проблему незнакомых улиц давно решили навигаторами. Но даже автомобилисты ходят пешком. Если магазин через дорогу, то мы встаём и идём. Трудности появляются, если предстоит пройти пятьсот метров по незнакомой улице и два-три раза свернуть.

Ни один из известных нам сервисов не строил маршрут из точки А до точки Б там, где нет тропинок и тротуаров, зато полно заборов и домов причудливых очертаний.

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

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

Hash array mapped trie — это ассоциативный контейнер, который обладает свойствами хэш таблиц и trie. Операции вставки пары ключ-значение и поиск по ключу — О(1) операции.
Про trie на хабре уже писали.

Как известно, существует три вида алгоритмов: линейные, разветвленные и циклические:



Основой всего, что сделано в методологии программирования, включая и объектное программирование стало структурное программирование, предложенное Эдсгером Дейкстрой в 1970-х годах. Одной из основных идей было введение блочных операторов ветвления (IF, THEN, ELSE) и цикличности (WHILE, FOR, DO, UNTIL и др.) вместо проблемного оператора GOTO, который приводил к получению запутанного, неудобочитаемого «спагетти-кода».

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

Понятно, зачем теоретики находят эффективные алгоритмы решения задач какого-то класса, а потом практики их реализуют. Но теоретики стараются также доказать, что для некоторых задач эффективных алгоритмов (и даже вообще никаких алгоритмов) не существует. Что при этом им удаётся и не удаётся, и зачем это может быть нужно? В лекции речь идет о «проблеме остановки» и задачах, к которым она сводится, о знаменитом классе NP, а также о простых нижних оценках.



Лекция был прочитана в Малой Школе анализа данных, которую Яндекс организует для старшеклассников. Автор — Александр Шень. Окончил мехмат МГУ, под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии». Сейчас является сотрудником Института проблем передачи информации им. А.А. Харкевича РАН и Лаборатории Национального центра научных исследований Франции. Научные интересы: алгоритмы, колмогоровская сложность, логика, теория информации. Почти все книги, которые Александр Ханиевич написал о математике и программированию, находятся в свободном доступе.

Под катом — расшифровка лекции.

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

В этой статье рассказывается, как писать синтаксические анализаторы с помощью этой небольшой библиотеки на с++.

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

Например, элемент xml состоит из открывающего тега, содержимого и закрывающего тега. —> Открывающий тег состоит из '<', имени тега, возможно пустого списка атрибутов и '>'. —> Закрывающий тег состоит из '</', имени тега и '>'. —> Атрибут состоит из имени, знаков '=', '"', строки символов и снова '"'. —> Содержимое в свою очередь тоже может содержать элементы. —> И т.д. Таким образом, после разбора получается синтаксическое дерево.

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

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

Например для БНФ вида expr ::= expr1 expr2 expr3 будем писать такую функцию:

Этим летом мне посчастливилось попасть на летнюю стажировку в компанию Itseez. Мне было предложено исследовать современные методы, которые позволили бы выделить местоположения объектов на изображении. В основном такие методы опираются на сегментацию, поэтому я начала свою работу со знакомства с этой областью компьютерного зрения.
Сегментация изображения — это разбиение изображения на множество покрывающих его областей. Сегментация применяется во многих областях, например, в производстве для индикации дефектов при сборке деталей, в медицине для первичной обработки снимков, также для составления карт местности по снимкам со спутников. Для тех, кому интересно разобраться, как работают такие алгоритмы, добро пожаловать под кат. Мы рассмотрим несколько методов из библиотеки компьютерного зрения OpenCV.

Автор оригинала на английском языке — хабраюзер dzeban

Введение

В прошлый раз мы обсудили, как можно искусственно ограничить доступную программе память. В качестве бонуса я заполучил себе libmemrestrict – библиотеку с обёртками функций вроде malloc для отслеживания использования памяти, и ptrace-restrict — инструмент на базе ptrace, перехватывающий вызовы brk, sbrk и mmap с той же целью.

Так зачем нам пытаться организовывать ограничение памяти – так ли это часто встречается? Когда в последний раз ООМ прибил ваше приложение? Вы всегда думаете о потреблении памяти во время программирования? Память – штука дешёвая, и если вам не хватает памяти, добавьте ещё пару гигабайт.

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

И вот я занялся подобными задачами, начав с простой – как отсортировать миллион целых чисел (4 MiB данных) при наличии 2 MiB памяти? Эту задачу можно обобщить на тот случай, когда у вас недостаточно памяти, чтобы вместить все данные.

Дано

Необходимо написать программу сортировки набора целых чисел, хранящихся в файле. Для его создания я написал простейшие утилиты randints и rangeints

Программа должна выдавать отсортированный массив на stdout в виде текста

Она должна измерить время работы и вывести его на stderr. Нельзя просто запустить программу через утилиту time, потому что она посчитает время на чтение файла и время на его вывод.

Она должна работать, имея памяти как минимум в два раза меньше объёма файла. Для этого мы применим libmemrestrict или ptrace-restrict.

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

Они будут проверяться для решения оригинальной задачи (сортировки 4 MiB в 2 MiB). Также я запущу их на виртуалке со 128 MiB памяти для сортировки 500 Mb (125 миллионов четырёхбайтных целых).

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

Речь пойдет не о чудесных Граалях, продаваемых в интернете, не о высокочастотной торговле и не о «безрисковых» вложениях в мифические ТОП-20 лучших трейдеров. Только хардкор: мы проводим многочисленные торговые операции, кто-то вручную, кто-то ― автоматически, и получаем в результате этих операций положительный прирост счета при статистически значимом количестве сделок.

Добрый день! Недавно мы начали цикл статей о совместном редактировании. В первой статье я рассказал о задаче неблокирующего редактирования и возможных подходах к его реализации. Напомню, что в итоге в качестве алгоритма мы выбрали Operation Transformation (OT). Также был анонсирован рассказ о его клиент-серверном варианте, и сегодня я освещу подробности его работы. Кроме того, вы узнаете, почему отмена в OT работает иначе и чем грозит столкновение с суровой реальностью.

Дальше вас ждет много алгоритмов и диаграмм. Думаю, вам будет интересно.

В июне этого года в России был принят новый стандарт блочного шифрования — ГОСТ Р 34.12-2015. Этот стандарт помимо старого доброго ГОСТ 28147-89, который теперь называется «Магма» и имеет фиксированный набор подстановок, содержит описание блочного шифра «Кузнечик». О нем я и расскажу в этом посте.

Традиционная техника “начального уровня”, сравнения текущего изображения с эталоном основывается на рассмотрении изображений как двумерных функций яркости (дискретных двумерных матриц интенсивности). При этом измеряется либо расстояние между изображениями, либо мера их близости.

Как правило, для вычисления расстояний между изображениями используется формула, являющаяся суммой модулей или квадратов разностей интенсивности:

d(X,Y) = SUM ( X[i,j] — Y[i,j] )^2

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

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

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

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



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

Например вот такая забавная оптимизация набора арифметических инструкций (взятых из какой-то подвернувшейся под руку математической библиотеки), соответствующих формулам: , которая на 6 джаве с выключенным JIT у меня давала около 10% ускорения, при этом на первый взгляд даже не очевидно что эти формулы эквивалентны (ОТКУДА ТУТ OR? ЭТО ВООБЩЕ ЗАКОННО?!), хотя это так. Под катом я расскажу, как именно получались такие результаты и каким образом компьютер придумывал лучший код чем тот, который мог написать я сам.