Привет! Сегодня я надеюсь показать вам немного магии. Моим хобби является придумывание всяких казалось бы невозможных штук на С++, что помогает мне в изучении всевозможных тонкостей языка ну или просто развлечься. Оператор in есть в нескольких языках, например Python, JS. Но в С++ его не завезли, но иногда хочется чтобы он был, так почему бы его не реализовать.

	std::unordered_map<std::string, std::string> some_map = 
	{
		{ "black", "white" },
		{ "cat", "dog" },
		{ "day", "night" }
	};

	if (auto res = "cat" in some_map)
	{
		res->second = "fish";
	}

В недавней статье «Амплитудная модуляция произвольного сигнала» её автор довольно сумбурно попытался представить своё понимание формирования спектра при амплитудной модуляции. Но отсутствие иллюстраций и избыток математики с привлечением интегральных преобразований помешало сообществу понять мысли автора и оценить статью по достоинству; в то время как тема это достаточно простая — и рассмотреть которую мы попробуем ещё раз, на этот раз с картинками и привлечением Wolfram Mathematica.

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

Давайте я за 5-10 минут чтения и понимания коротенькой статьи добавлю вам в резюме строчки «машинное обучение» и «нейронные сети»? Тем, кто далек от программирования, я развею все мифы о сложности ИИ и покажу, что большая часть всех проектов на машинном обучении строится на предельно простых принципах. Поехали — у нас всего пять минут.

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

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


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

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

Мой автомобиль Skoda Octavia 2011 г. в. не предлагает возможностей управления с телефона, поэтому я решил исправить этот недостаток, а заодно и добавить функцию голосового управления. В качестве шлюза между CAN шиной и телефоном я использую Raspberry Pi с шилдом CAN BUS и WiFi роутер TP-Link. Протокол общения агрегатов авто закрытый, и на все мои письма предоставить документацию протокола Volkswagen отвечал отказом. Поэтому единственный способ узнать, как общаются устройства в авто и научиться ими управлять является реверс-инжиниринг протокола CAN шины VW.

Я действовал поэтапно:

1. Разработка CAN шилда для Raspberry Pi
2. Установка ПО для работы с CAN шиной
3. Подключение к CAN шине авто
4. Разработка сниффера и изучение протокола CAN шины
5. Разработка приложения для телефона
6. Голосовое управление с помощью Homekit и Siri

В конце видео голосового управления стеклоподъемником.

Речь пойдёт о простой структуре данных — системе непересекающихся множеств. Вкратце: даны непересекающиеся множества (например, компоненты связности графа) и по двум элементам x и y можно: 1) узнать, находятся ли x и y в одном множестве; 2) объединить множества, содержащие x и y. Сама структура очень проста в реализации и описывалась много раз в различных местах (например, есть хорошая статья на хабре и ещё кое-где). Но это один из тех удивительных алгоритмов, написать который ничего не стоит, а вот разобраться, почему он работает эффективно совсем нелегко. Я постараюсь изложить относительно простое доказательство точной оценки на время работы этой структуры данных, придуманное Зейделем и Шариром в 2005 (оно отличается от того ужаса, который многие могли видеть в других местах). Конечно, сама структура тоже будет описана, а попутно разберёмся причём здесь обратная функция Аккермана, о которой многие знают только, что она оооочень медленно растёт.

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

Вот как-то я сидел и думал, что бы мне написать. Я выбрал для себя 16 программок, несколько раз подбросил монетку, и жребий указал мне на программку получения гифки из видео. Кто хочет увидеть дилетантский крестовый код — прошу под кат.

И снова здравствуйте!

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

Теперь настало время поговорить о самом интересном – как устроен сам движок извлечения информации.

Как правильно расширить возможности языка программирования используя перегрузку операторов.

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

«А зачем, ведь то, что вы предлагаете, можно сделать имеющимися средствами языка».

Перегрузка операторов появилась в С++ по просьбе физиков и математиков, которым хотелось удобно оперировать с самодельными типами данных, большими числами, матрицами.

Хотя физикам и математикам эта возможность пришлась по душе, программистам, в том числе создалелям С++ перегрузка операторов никогда особо не нравилась. Слишком сложное дело, много неявностей, поэтому за перегрузкой операторов закрепилось мнение чего-то вредного и применяемого в редких случаях.

Сегодня я попробую показать почему это так сложно и как правильно использовать перегрузку на примере создания одного нового типа под названием var поведение которого будет максимально приближено к аналогичному типу в JavaScript.

В то время пока я собирался на ланч, мой ко-воркер Дейв окликнул меня: «Хэй, Алекс, а ты не хочешь заниматься улучшениями навыков своего программирования?». Я задумался. Это было интересное предложение, но я склонялся ответить отказом: «Сейчас я занимаюсь развитем навыков говорения на языках, дружище!». Ладно, шучу. Утро началось с того, что я добрался до почты и заполучил в руки копеечный китайский Кубик, случайно заказанный на али. К обеду я проштудировал мануал сборки и обновил мышечную память, а к вечеру пришло осознание, что я наигрался. Будущее кубика было ясным: он будет пылиться на полке, раз или два в неделю может быть я буду его собирать, чтобы привести мысли в порядок или отвлечься, но не более того. Соревнование в механической скорости сборки? Non merci, уж лучше скворечники делать…

Ситуацию, как всегда, спасли мысли об автоматизации. После недолгого изучения я узнал рекогнисцировку. Для начала, число Бога уже давно найдено и равно 20. Правда задача сборки от этого не упрощается, т.к. использовать граф кратчайших путей для всех возможных конфигураций кубика не очень спортивно и немножко накладно по ресурсам. Алгоритм Бога предполагает под собой некое разумное количество использованной памяти, и в то же время обязан обеспечить минимально возможное число модификаций. Так вот, такого алгоритма еще нет. Есть ряд алгоритмов, позволяющих заметно ускорить сборку по сравнению с традиционными шаблонными методоми, но повторять кем-то уже проложенный (математически) путь мне показалось скучным. Если кому интересно, вот хороший анализ Далее есть традиционные шаблонные методы. Идея здесь в послойной сборке снизу вверх с использованием формул. Формула — последовательность модификаций Кубика, приводящая к таким-то целевым модификациям, и таким-то побочным. Соответственно, побочные модификации почти всегда падают на еще не собранные слои. Различаются шаблонные методы уровнем детализации шаблонов. Всякого рода спидкуберы знают все мыслимые шаблоны для большого количества частных случаев, что позволяет отыграть лишнюю 0.1 секунду с каждой модификации на соревнованиях. Пример, на что еще можно потратить жизнь.

Итак, я постепенно формировал для себя задачу. В итоге, формулируется она так: за кратчайшее реальное время необходимо написать решалку для Кубика Рубика.

Что мы знаем о Кубике? Число его состояний описывается как

(8! × 3^7) × (12! × 2^11)/2 = 43 252 003 274 489 856 000

.

Моя статья расскажет Вам как принять 10 миллионов пакетов в секунду без использования таких библиотек как Netmap, PF_RING, DPDK и прочие. Делать мы это будем силами обычного Линукс ядра версии 3.16 и некоторого количества кода на С и С++.



Сначала я хотел бы поделиться парой слов о том, как работает pcap — общеизвестный способ захвата пакетов. Он используется в таких популярных утилитах как iftop, tcpdump, arpwatch. Кроме этого, он отличается очень высокой нагрузкой на процессор.

Итак, Вы открыли им интерфейс и ждете пакетов от него используя обычный подход — bind/recv. Ядро в свою очередь получает данные из сетевой карты и сохраняет в пространстве ядра, после этого оно обнаруживает, что пользователь хочет получить его в юзер спейсе и передает через аргумент команды recv, адрес буфера куда эти данные положить. Ядро покорно копирует данные (уже второй раз!). Выходит довольно сложно, но это не все проблемы pcap.

Кроме этого, вспомним, что recv — это системный вызов и вызываем мы его на каждый пакет приходящий на интерфейс, системные вызовы обычно очень быстры, но скорости современных 10GE интерфейсов (до 14.6 миллионов вызовов секунду) приводят к тому, что даже легкий вызов становится очень затратным для системы исключительно по причине частоты вызовов.

Также стоит отметить, что у нас на сервере обычно более 2х логических ядер. И данные могут прилететь на любое их них! А приложение, которое принимает данные силами pcap использует одно ядро. Вот тут у нас включаются блокировки на стороне ядра и кардинально замедляют процесс захвата — теперь мы занимаемся не только копированием памяти/обработкой пакетов, а ждем освобождения блокировок, занятых другими ядрами. Поверьте, на блокировки может зачастую уйти до 90% процессорных ресурсов всего сервера.

Хороший списочек проблем? Итак, мы их все геройски попробуем решить!

По долгу службы мне часто нужно находить все пересечения между текстами (например, все цитаты из одного текста в другом). Я достаточно долго искал стандартное решение, которое бы позволило бы это делать, но найти его мне так и не удалось — обычно решается какая-то совсем или немного другая задача. Например, класс SequenceMatcher из difflib в стандартной библиотеке Питона находит самую длинную общую подпоследовательность в двух последовательностях hashable элементов, а потом рекурсивно повторяет поиск слева и справа от нее. Если в одном из текстов будет более короткая подпоследовательность, которая содержится внутри уже найденной (например, если кусок длинной цитаты где-то был повторен еще раз), он ее пропустит. Кроме того, когда я загнал в него «Войну и мир» и «Анну Каренину» в виде списков слов и попросил для начала найти самую длинную подпоследовательность, он задумался на семь минут; когда я попросил все совпадающие блоки, он ушел и не вернулся (в документации обещают среднее линейное время, но что-то в прозе Льва Толстого, по-видимому, вызывает к жизни worst-case квадратичное).

В конечном итоге я придумал свой алгоритм, тем самым наверняка изобретя велосипед, который надеюсь увидеть в комментариях. Алгоритм делает ровно то, что мне нужно: находит все совпадающие последовательности слов в двух текстах (за исключением тех, что в обоих текстах входят в состав более крупных совпадающих последовательностей) и сравнивает «Войну и мир» с «Анной Карениной» за минуту.

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

В качестве примера одной из таких вещей можно назвать cmd.exe. Да-да, это тот самый интерпретатор командной строки, входящий в поставку всех современных (и не очень) операционных систем семейства Windows. Исторических причин у него накопилось изрядное количество — достаточно вспомнить хотя бы то, как необходимо производить вставку и копирование в данный интерпретатор (ради справедливости стоит сказать, что в Windows 10 эту ситуацию наконец исправили, да и приложения наподобие ConEmu здорово в этом помогают). Но речь сегодня пойдёт о другом поведении, которое заствляет задуматься впервые столкнувшегося с cmd.exe человека, казалось бы, там, где этого совсем не требуется.

Как вы знаете, одной из команд, которые воспринимает cmd.exe, является «CD». Официальный хелп по этой команде сообщает следующее:

C:\Users\Nikita.Trophimov>CD /?
Displays the name of or changes the current directory.
[...]

Казалось бы, всё просто. Вызываешь CD без аргумента — в stdout выводится путь до текущей директории, передаёшь другую директорию в качестве аргумента — он сменяет текущую директорию на указанную. Подводные камни тут начинаются в том случае, если пользователь решил сменить директорию одновременно вместе с диском. Например, если вы находитесь в директории «C:\Windows\system32», то команда «CD D:\books» не сделает ровным счётом ничего. На мой взгляд, очевидного для новых пользователей в этом совершенно ничего нет, так что их спасает гугл или официальная документация, которая, кстати, сообщает:

Use the /D switch to change current drive in addition to changing current
directory for a drive.

Разумеется, этот вопрос, равно как и причины возникновения подобного поведения, уже не раз обсуждался в интернете (например, тут), так что останавливаться на подобных вещах мы не будем. Вместо этого мы попробуем отладить cmd.exe, чтобы убрать необходимость явного указания ключа "/D".

Как протекал процесс, и что из этого вышло, читайте под катом.

Привет, Хабр!

Мы в HumanFactorLabs парсим адреса в особо крупных размерах. Наши продукты упрощают ввод контактных данных и работу с ними.

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

Недавно на Хабре нас попросили привести примеры необычных адресов, в связи с чем и написана эта статья.

Google, Microsoft, Mozilla и инженеры проекта WebKit 17 июня сделали анонс, что они объединились для запуска WebAssembly, нового бинарного формата для компилирования веб-приложений.

Современные версии ОС налагают на исполняемый код ограничения, связанные с требованиями безопасности. В таких условиях использование механизма исключений в инжектированном коде или, скажем, во вручную спроецированном образе может стать нетривиальной задачей, если не быть в курсе некоторых нюансов. В этой статье речь пойдет о внутреннем устройстве юзермодного диспетчера исключений ОС Windows для платформ x86/x64/IA64, а также будут рассмотрены варианты реализации обхода системных ограничений.

Сегодня в свет вышел отчет группы специалистов по информационной безопасности, посвященный исследованию атак, основанных на способах коммуникации между собой различных приложений на OS X и iOS — (XARA, от Cross-App Resource Access). Для тех, кому лень читать все 26 страниц оригинальной статьи, я решил подготовить ее небольшой обзор.

Для начала, два коротких тезиса:

• Во-первых, большая часть обнародованных уязвимостей касается OS X. В iOS все намного спокойнее.
• Во-вторых, все на самом деле достаточно печально.

Предисловие от переводчика

Здесь представлен один из новейших методов расчёта ориентации в пространстве по показаниям датчиков акселерометра, гироскопа и компаса — фильтр Маджвика, который, по словам автора, даёт результат лучший, чем применение фильтра на основе метода Калмана в результатах и производительности. Автор — Себастьян Маджвик (его интернет-магазин). Метод описан в статье на английском. Данная работа защищена в Университете г. Бристоля Перевода я не нашёл. Переводчик из меня так себе, особенно таких сложных текстов. Но нам же интересно, что за метод?

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

OpenBTS.org — это открытый проект c исходным кодом на GitHub, призванный провести революцию среди мобильных сетей путем замены устаревших телекоммуникационных протоколов и традиционно сложных запатентованных аппаратных систем использованием Интернет-протокола и программного обеспечения с гибкой архитектурой. Архитектура этой системы является открытой для инноваций, позволяя любому желающему разрабатывать новых приложения и сервисы на базе OpenBTS и значительно упрощает настройку и эксплуатацию сети мобильной связи.

Посещать или слушать? Дело вкуса – не более. Или нет?
Предыстория.

Разобрав исходный текст, на выходе образовалось дерево:



Само по себе дерево не имеет ни какого смысла, оно “Деревянное”, смыслом и какой либо ценностью обладает результат анализа (обхода) этого дерева. Для тех кто не готов напрягаться и писать самописные сани по спуску с дерева (например, меня) в antlr4 добавлена возможность получить анализатор почти бесплатно.

1. Visitor

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

2. Listener

Новшество, появившееся в четвертой версии. Поведение этого класса уже далеко не классическое (Observer или Publish/Subscribe). В классическом исполнении наблюдается менеджер который оповещает подписчиков о наступлении событий. Поведения рассматриваемого слушателя больше похоже на работу инспектора. Инспектор перед проверкой узла делает заметку “Я проверяю Х узел”, далее идет обход потомков узла, после обхода, которых можно сделать “Заключение о результатах обхода узла Х”.