Pull to refresh
1
0

Software engineer

Send message

Изобретаем JPEG

Reading time28 min
Views178K

Вы правильно поняли из названия, что это не совсем обычное описание алгоритма JPEG (формат файла я подробно описывал в статье «Декодирование JPEG для чайников»). В первую очередь, выбранный способ подачи материала предполагает, что мы ничего не знаем не только о JPEG, но и о преобразовании Фурье, и кодировании Хаффмана. И вообще, мало что помним из лекций. Просто взяли картинку и стали думать как же ее можно сжать. Поэтому я попытался доступно выразить только суть, но при которой у читателя будет выработано достаточно глубокое и, главное, интуитивное понимание алгоритма. Формулы и математические выкладки — по самому минимуму, только те, которые важны для понимания происходящего.

Знание алгоритма JPEG очень полезно не только для сжатия изображений. В нем используется теория из цифровой обработки сигналов, математического анализа, линейной алгебры, теории информации, в частности, преобразование Фурье, кодирование без потерь и др. Поэтому полученные знания могут пригодиться где угодно.

Если есть желание, то предлагаю пройти те же этапы самостоятельно параллельно со статьей. Проверить, насколько приведенные рассуждения подходят для разных изображений, попытаться внести свои модификации в алгоритм. Это очень интересно. В качестве инструмента могу порекомендовать замечательную связку Python + NumPy + Matplotlib + PIL(Pillow). Почти вся моя работа (в т. ч. графики и анимация), была произведена с помощью них.

Внимание, трафик! Много иллюстраций, графиков и анимаций (~ 10Мб). По иронии судьбы, в статье про JPEG всего 2 изображения с этим форматом из полусотни.
Читать дальше →

Линейная регрессия на пальцах в распознавании

Reading time7 min
Views39K
Линейная регрессия на пальцахВ задаче распознавания ключевую роль играет выделение значимых параметров объектов и оценка их численных значений. Тем не менее, даже получив хорошие численные данные, нужно суметь правильно ими воспользоваться. Иногда кажется, что дальнейшее решение задачи тривиальное, и хочется «из общих соображений» получить из численных данных результат распознавания. Но результат в этом случае получается далеко не оптимальный. В этой статье я хочу на примере задачи распознавания показать, как можно легко применить простейшие математические модели и за счет этого существенно улучшить результаты.
Читать дальше →

Делаем приставку — счётчик Гейгера к iPhone за 2 часа

Reading time3 min
Views203K
image

UPD: Кто уже читал пост — пожалуйста зайдите и поучаствуйте в опросе. Спасибо большое!

Примерно полтора года назад на нескольких сетевых ресурсах, в том числе и на хабре, начали пиарить проект «До-ра» — приставку к iPhone, позволяющую измерять радиационный фон и делать много всего вкусного на основании получаемой со счётчика Гейгера информации. Статьи в новостях проекта упоминают несколько многомиллионных грантов, выделенных на разработку приборчика фондом «Сколково». Шли месяцы, «До-ра» всё никак не получалась, покупатели ждали, конкуренты не дремали. Так ли сложна «До-ра» как её малюют и как собрать за пару часов из подручных деталей в десять раз более чувствительный аналог я расскажу тем кто нажмёт на
кнопку

Lock-free структуры данных. Извне: введение в libcds

Reading time14 min
Views31K

В этой статье я даю краткий обзор того, как применять библиотеку lock-free структур данных libcds. В реализацию я углубляться здесь не буду, — это просто взгляд извне, взгляд со стороны пользователя библиотеки.

Библиотека libcds имеет свою точку зрения на многие известные структуры данных. Отчасти это объясняется целевой областью – lock-free структуры данных довольно минималистичны по набору предоставляемых методов, — отчасти желанием выйти за ограничения и решения стандартной библиотеки STL. Что из этого получилось – решать пользователям libcds.

Кому интересно – добро пожаловать под кат
Читать дальше →

Lock-free структуры данных. Основы: Модель памяти

Reading time18 min
Views103K

В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.
Читать дальше →

Lock-free структуры данных. Внутри. Схемы управления памятью

Reading time28 min
Views53K

Как я упоминал в своих предыдущих заметках, основными трудностями при реализации lock-free структур данных являются ABA-проблема и удаление памяти. Я разделяю эти две проблемы, хоть они и связаны: дело в том, что существуют алгоритмы, решающие только одну из них.
В этой статье я дам обзор известных мне методов безопасного удаления памяти (safe memory reclamation) для lock-free контейнеров. Демонстрировать применение того или иного метода я буду на классической lock-free очереди Майкла-Скотта [MS98].

Читать дальше →

RMI средствами С++ и boost.preprocessor

Reading time11 min
Views7.3K
Это моя первая публикация на сем ресурсе, посему, прошу отнестись с пониманием к допущенным мною ошибкам.

RMI — весьма банальная задача для ЯП, поддерживающих интроспекцию. Но, С++, к сожалению, к ним не относится.

В данной публикации я хочу продемонстрировать возможность реализации весьма юзабильной RMI средствами С++ препроцессора.

Постановка задачи


1. Предоставить максимально простой синтаксис, чтоб невозможно было допустить ошибку.
2. Идентификация(связывание) процедур должна быть скрыта от пользователя для того, чтоб невозможно было допустить ошибку.
3. Синтаксис не должен накладывать ограничения на используемые С++ типы.
4. Должна присутствовать возможность версионности процедур, но, так, чтоб не ломалась совместимость с уже работающими клиентами.
Читать дальше →

«ZeroMQ».Глава 1: Приступая к работе

Reading time10 min
Views86K
Всем привет!
Хочу начать вольный перевод книги «ZeroMQ.Use ZeroMQ and learn how to apply different message patterns». Уверен, что многие захотят разобраться с этой интересной библиотекой.

Содержание


Добро пожаловать в ZeroMQ! Эта глава представляет собой введение в ZeroMQ и дает читателю общее представление о том, что такое система очередей сообщений и, самое главное, что такое ZeroMQ. В этой главе мы поговорим о следующих темах:
  • Обзор того, что представляет собой очередь сообщений
  • Зачем использовать ZeroMQ и что отличает ее от других технологий работы с очередями сообщений
  • Основы клиент/серверной архитектуры
  • Рассмотрим первый паттерн: запрос-ответ
  • Как мы можем обрабатывать строки в C
  • Проверка установленных версий ZeroMQ


Читать дальше →

Что такое MANET или почему WiFi не решение всех телекоммуникационных проблем

Reading time10 min
Views42K
Прочитав очередной пост на хабре на тему самоорганизующихся сетей автор понял, что в этой теме до сих пор нет ясности. В большинстве случаев о самоорганизующихся радиосетях говорят «mesh», «ad hoc», «mobile ad hoc» и т.д., подразумевая, что это одно и тоже. И это касается не только простого хабро-обывателя, пусть даже технически подкованного, но и большинства инженеров с PhD. К тому же, зачастую такие сети преподносятся как универсальное средство на все случаи жизни [1] или даже как чуть-ли не единственный вектор развития и эволюции телеком индустрии [2]. Смею уверить, что без четкого понимания места и роли этих сетей, такие утверждения, по крайней мере, преждевременны, хотя и недалеки от реальности.

Итак, начнем с определения, что же такое сети типа Mesh, Ad Hoc, mobile Ad Hoc и в чем разница между ними.

Mesh сети – радиосети ячеистой структуры, состоящие из беспроводных стационарных маршрутизаторов, которые создают беспроводную магистраль и зону обслуживания абонентов) и мобильных/стационарных абонентов, имеющих доступ (в пределах зоны радиосвязности) к одному из маршрутизаторов. Топология – звезда, со случайным соединением опорных узлов.
Ad hoc сети – радиосети со случайными стационарными абонентами, реализующие полностью децентрализованное управление при отсутствии базовых станций или опорных узлов. Топология – фиксированная со случайным соединением узлов.
MANET (Mobile Ad hoc NETworks) сети – радиосети со случайными мобильными абонентами, реализующие полностью децентрализованное управление при отсутствии базовых станций или опорных узлов. Топология – быстро меняющаяся со случайным соединением узлов.
К этому надо добавить WSN (Wireless Sensor Networks) — беспроводные сенсорные (телеметрические) сети, состоящие из малогабаритных сенсорных узлов с интегрированными функциями мониторинга определенных параметров окружающей среды, обработки и передачи данных по радиоканалам. Они могут, в зависимости от задачи, строиться как топологии mesh, ad hoc так и MANET; автомобильные сети VANET (Vehicle Ad hoc NETworks) – сети связи транспортных средств; и всевозможные гибриды вышеизложенного.

Почему именно MANET?

Сегодня подавляющее большинство наземных мобильных беспроводных сетей связи имеют фиксированную инфраструктуру и соединены между собой с помощью различных, как правило проводных или радиорелейных, каналов передачи данных. В последнее десятилетие большое внимание уделяется созданию мобильных пакетных радиосетей, которые не имеют фиксированной инфраструктуры – сети стационарных (Ad Hoc) и мобильных абонентов (MANET).

Такие сети являются самоорганизующимися, поскольку их узлы являются не только оконечными пользовательскими терминалами, но и являются ретрансляторами-маршрутизаторами, ретранслируя пакеты других абонентов и участвуя в нахождении маршрутов к ним, следовательно, эти сети способны к самоорганизации. Такие сети могут состоять из десятков, сотен и даже тысяч узлов. Сфера применения таких сетей достаточно широка. Так, сети MANET полезны в поисково-спасательных операциях, на театре военных действий тактического уровня, местах большого скопления людей (например, для обслуживания участников конференций), и там, где нет телекоммуникационной инфраструктуры (например, в экспедициях в удаленные от «цивилизации» регионы). Возможно, что эти сети во многих случаях могут стать альтернативой массовым сетям мобильной связи.

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

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

Lock-free структуры данных. Основы: Атомарность и атомарные примитивы

Reading time15 min
Views112K

Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый круг ада низкий уровень из двух.
Читать дальше →

Lock-free структуры данных. 1 — Начало

Reading time12 min
Views153K

Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.

Читать дальше →

Lock-free структуры данных. Основы: откуда пошли быть барьеры памяти

Reading time22 min
Views100K

Как только я заинтересовался lock-free алгоритмами, меня стал мучить вопрос – а откуда взялась необходимость в барьерах памяти, в «наведении порядка» в коде?
Конечно, прочитав несколько тысяч страниц руководств по конкретной архитектуре, мы найдем ответ. Но этот ответ будет годен для этой конкретной архитектуры. Есть ли общий? В конце концов, мы же хотим, чтобы наш код был портабелен. Да и модель памяти C++11 не заточена под конкретный процессор.
Наиболее приемлемый общий ответ дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он построил некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и зачем он был введен.
Вообще, Paul McKenney – известная личность. Он является разработчиком и активным пропагандистом технологии RCU, которая активно используется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к безопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C++11.
Статья большая, я даю перевод только первой половины. Я позволил себе добавить некоторые комментарии, [которые выделены в тексте так].
Передаю слово Полу

Алгоритм распределения данных в кластере серверов в dCache

Reading time2 min
Views4.6K
В продолжение статьи о dCache расскажу о некоторых деталях внутренней реализации.

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

Показать, как это сделано в dCache

Кластер, который всегда с собой

Reading time5 min
Views41K
lxcЗахотелось странного.
Во-первых, взгромоздить кучу виртуальных машин прямо на свой ноутбук.
А во-вторых, раскурить одну виртуализацию внутри другой.

Речь пойдет про использование контейнеров LXC, причем внутри другой виртуальной машины.

WTF! На кой это нужно?

ADB Uninstall плагин для Android Studio (IntelliJ IDEA)

Reading time6 min
Views20K

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

Создаем быстрый прототип мобильного приложения

Reading time6 min
Views220K
На хабре уже присутствует некоторое количество статей, посвященных процессу прототипирования в разработке программного обеспечения. Есть достаточно фундаментальные статьи с обзорами стандартов и расчетами, есть статьи про прототипирование устройств, есть цикл из двух статей про процесс выбора инструмента для прототипирования. К сожалению, процесс создания прототипов мобильных приложений освещен очень скудно – в виде единственной статьи в 2010 году, и пара слов в статье Разработка мобильных приложений: с чего начать.

Хотелось бы исправить эту ситуацию, и предложить вашему вниманию большой обзор доступных инструментов для прототипирования мобильных приложений.
Читать дальше →

ARM-ы для самых маленьких

Reading time8 min
Views210K


Пару дней назад я опубликовал и потом внезапно убрал в черновики статью о плане написать про создание своей ОС для архитектуры ARM. Я сделал это, потому что получил много интересных отзывов как на Хабре, так и в G+.

Сегодня я попробую подойти к вопросу с другой стороны, я буду рассказывать о том, как программировать микроконтроллеры ARM на нарастающих по сложности примерах, пока мы не напишем свою ОС или пока мне не надоест. А может, мы перепрыгнем на ковыряние в Contiki, TinyOS, ChibiOS или FreeRTOS, кто знает, их там столько много разных и интересных (а у TinyOS еще и свой язык программирования!).

Итак, почему ARM? Возиться с 8-битными микроконтроллерами хотя и интересно, но скоро надоедает. Кроме того, средства разработки под ARM обкатаны долгим опытом и намного приятнее в работе. При этом, начать мигать светодиодами на каком-то «evaluation board» так же просто, как и на Arduino.

Читать дальше →

Взаимодействие клиентов SIP. Часть 1

Reading time5 min
Views245K


Месяц назад я начал свое знакомство с IP-телефонией, а именно с Lync и Asterisk. И заметил следующую картину: в сети очень много интересных статей по практической стороне вопроса (как и что делать) и очень мало внимания уделено теории (в конце статьи приведены ссылки). Если Вы хотите разобраться с SIP, то извольте либо читать RFC 3261, либо одну из «этих толстых книг». Это, естественно, полезно, но многим хочется в начале изучить некую выжимку, а уж потом бросаться в омут с головой. Эта статья как раз для таких людей.
Поехали

IP-телефония: от медных проводов до цифровой обработки сигнала

Reading time11 min
Views91K


Если в один прекрасный день вам придется на скорую руку разобраться, что есть VoIP (voice over IP) и что значат все эти дикие аббревиатуры, надеюсь, эта методичка поможет. Сразу замечу, что вопросы конфигурирования дополнительных видов обслуживания телефонии (такие как перевод вызова, голосовая почта, конференц-связь и т.п.) здесь не рассматриваются.



Итак, с чем мы будем разбираться под катом:
  1. Базовые понятия телефонии: типы аппаратов, схемы подключения
  2. Связка SIP/SDP/RTP-протоколов: как это работает
  3. Как передается информации о нажатых кнопках
  4. Как происходит передача голоса и факсов
  5. Цифровая обработка сигналов и обеспечение качества звука в IP-телефонии

Читать дальше →

Настоящее sock_raw'вище

Reading time5 min
Views39K
image

Raw сокеты предоставляют программисту более широкие возможности по сравнению с остальной частью сокетного API. Все знают об этих «широких» возможностях, но более или менее систематизированное их описание встречается в Интернете нечасто. Попробуем, восполнить данный пробел и разобраться с предназначением raw cокетов и вариантами их применения в сетевом ПО.
Читать дальше →

Information

Rating
Does not participate
Registered
Activity

Specialization

Backend Developer, System Software Engineer
Lead
From 8,192 $
Git
C++ Boost
Multiple thread
Http
Linux
High-loaded systems
OOP
TCP
Network technologies
Linux administration