Почему?

Сейчас Relap.io генерирует 40 миллиардов рекомендаций в месяц на 2000 медиаплощадках Рунета. Почти любая рекомендательная система, рано или поздно, приходит к необходимости брать в расчет содержимое рекомендуемого контента, и довольно быстро упирается в необходимость как-то его классифицировать: найти какие-то кластеры или хотя бы понизить размерность для описания интересов пользователей, привлечения рекламодателей или еще для каких-то темных или не очень целей.

Задача звучит довольно очевидно и существует немало хорошо зарекомендовавших себя алгоритмов и их реализаций: Латентное размещение Дирихле (LDA), Вероятностный латентно-семантический анализ (pLSA), явный семантический анализ (ESA), список можно продолжить. Однако, мы решили попробовать придумать что-нибудь более простое, но вместе с тем, жизнеспособное.

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

Наша компания «RTL-Service» занимается разработкой и продвижением решений локального позиционирования, в связи с чем мы уже знакомили наших читателей с разнообразием технологий локального позиционирования. В сегодняшней статье мы постараемся более подробно остановиться на методах локального позиционирования, в основе которых лежит использование радиоволн.

Оказывается, в свободном доступе есть интересная информация от HeadHunter о повышении фонда оплаты труда (ФОТ) в 2015 году. Со страницы проекта "Банк данных заработных плат" идет ссылка "Сравнивайте зарплаты вашей компании с рынком".

Прямая ссылка на pdf: Зарплаты в России. Итоги 2015 года.


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

И вообще, многим придут на ум уже затертые шаблоны:

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

Но эти выводы и советы слишком уж лежат на поверхности.
We need to go deeper.
Давайте посмотрим, насколько же глубока эта не кроличья нора…

интервьюер: Приветствую, хотите кофе или что-нибудь еще? Нужен перерыв?

я: Нет, кажется я уже выпил достаточно кофе!

интервьюер: Отлично, отлично. Как вы относитесь к написанию кода на доске?

я: Я только так код и пишу!

интервьюер: ...

я: Это была шутка.

интервьюер: OK, итак, вам знакома задача "fizz buzz"?

я: ...

интервьюер: Это было да или нет?

я: Это что-то вроде "Не могу поверить, что вы меня об этом спрашиваете."

интервьюер: OK, значит, нужно напечатать числа от 1 до 100, только если число делится нацело на 3, напечатать слово "fizz", если на 5 — "buzz", а если делится на 15, то — "fizzbuzz".

я: Я знаю эту задачу.

интервьюер: Отлично, кандидаты, которые не могут пройти эту задачу, у нас не сильно уживаются.

я: ...

интервьюер: Вот маркер и губка.

я: [задумался на пару минут]

интервьюер: Вам нужна помощь, чтобы начать?

я: Нет, нет, все в порядке. Итак, начнем с пары стандартных импортов:

import numpy as np
import tensorflow as tf

интервьюер: Эм, вы же правильно поняли проблему в fizzbuzz, верно?

я: Так точно. Давайте обсудим модели. Я думаю тут подойдет простой многослойный перцептрон с одним скрытым слоем.

^{Мужик приходит устраиваться работать на стройку. Его спрашивает мастер:
— Что делать умеешь?
— Могу копать…
— А что еще?
— Могу не копать…}

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

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

В статье фокус делается на программной стороне вопроса состояний процессора. Я не буду концентрироваться на деталях реализации (напряжения, пины, частоты и т.д.), так как 1) они существенно различаются между поколениями и моделями процессоров даже одной архитектуры, тогда как программный интерфейс остаётся обратно совместимым; 2) они не видны напрямую программам и ОС. Это попытка просуммировать информацию, разбросанную по многим страницам справочника Intel IA-32 and Intel 64 Software Developer Manual.

Начнём с простой и всем знакомой ситуации — процессор включён, бодр и весел.

Мотивация

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

Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.

Далее в наиболее доступной форме описаны два основных понятия теории формальных языков: формальный язык и формальная грамматика. Если тест будет интересен аудитории, то автор дает торжественное обещание разродиться еще парой подобных опусов.

Предыдущая статья серии была посвящена теории парсинга исходников с использованием ANTLR и Roslyn. В ней было отмечено, что процесс сигнатурного анализа кода в нашем проекте PT Application Inspector разбит на следующие этапы:

1. парсинг в зависимое от языка представление (abstract syntax tree, AST);
2. преобразование AST в независимый от языка унифицированный формат (Unified AST, UAST);
3. непосредственное сопоставление с шаблонами, описанными на DSL.

Данная статья посвящена второму этапу, а именно: обработке AST с помощью стратегий Visitor и Listener, преобразованию AST в унифицированный формат, упрощению AST, а также алгоритму сопоставления древовидных структур.

Содержание

• Обход AST
  
  • Visitor и Listener
  • Различия в Visitor в ANTLR и Roslyn
  • Грамматика и Visitor в ANTLR
  • Альтернативные и элементные метки в ANTLR
• Типы узлов унифицированного AST
• Тестирование конвертеров
• Упрощение UAST
• Алгоритм сопоставления древовидных структур
• Заключение

В этой серии из двух статей говорится о том, как структура данных и памяти влияет на производительность. Предлагаются определенные действия для повышения производительности программного обеспечения. Даже простейшие действия, показанные в этих статьях, позволят добиться существенного прироста производительности. Многие статьи, посвященные оптимизации производительности программ, рассматривают распараллеливание нагрузки в следующих областях: распределенная память (например, MPI), общая память или набор команд SIMD (векторизация), но на самом деле распараллеливание необходимо применять во всех трех областях. Эти элементы очень важны, но память также важна, а про нее часто забывают. Изменения архитектуры программ и применение параллельной обработки влияют на память и на производительность.

В нашем проекте PT Application Inspector реализовано несколько подходов к анализу исходного кода на различных языках программирования:

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

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

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

• поддержка нескольких языков программирования и простое добавление новых;
• поддержка анализа кода, содержащего синтаксические и семантические ошибки;
• возможность описания шаблонов на универсальном языке (DSL, domain specific language).

В нашем случае все шаблоны описывают какие-либо уязвимости или недостатки в исходном коде.

Весь процесс анализа кода может быть разбит на следующие этапы:

1. парсинг в зависимое от языка представление (abstract syntax tree, AST);
2. преобразование AST в независимый от языка унифицированный формат;
3. непосредственное сопоставление с шаблонами, описанными на DSL.

Данная статья посвящена первому этапу, а именно: парсингу, сравнению функциональных возможностей и особенностей различных парсеров, применению теории на практике на примере грамматик Java, PHP, PLSQL, TSQL и даже C#. Остальные этапы будут рассмотрены в следующих публикациях.

Совсем недавно я написал статью, в которой без объяснений показал то, на что способен метод грамматической эволюции. Я полностью, согласен, что так делать нельзя, но как хотелось показать результаты интересного метода. Я думал «что будет лучше: перевести первоисточник или дать свое собственное объяснение». Лень взяла верх.

Если кому-то интересны эволюционные методы и задача символьной регрессии(и не только), то прошу к прочтению.

Давайте на время отвлечемся от очередного "языка-убийцы C++", ошеломляющих синтетических тестов производительности какой-нибудь NoSQL-ой СУБД, хайпа вокруг нового JS-фреймворка, и окунемся в мир "программирования ради программирования".

А не замахнуться ли нам на Эдсгера нашего Дейкстру?

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

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

Автор: Александр Трищенко


Я расскажу о своем хобби — организации видеотрансляций в браузере по технологии WebRTC (Web Real-Time Communication — веб-коммуникация в режиме реального времени). Этот проект с открытым исходным кодом Google активно развивает с 2012 г., а первый стабильный релиз появился в 2013 г. Сейчас WebRTC уже хорошо поддерживается самыми распространенными современными браузерами, за исключением Safari.

Технология WebRTC позволяет устроить видеоконференцию между двумя или несколькими пользователями по принципу P2P. Таким образом, данные между пользователями передаются напрямую, а не через сервер. Впрочем, сервер нам все равно понадобится, но об этом скажу далее. Прежде всего, WebRTC рассчитана на работу в браузере, но есть и библиотеки для разных платформ, которые тоже позволяют использовать WebRTC-соединение.

Если мы используем WebRTC, мы решаем следующие проблемы:

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

… Молвит он: «Коль жив я буду, чудный остров навещу, у Гвидона погощу».

В царстве Салтана не без изьяна. Принят закон — не лезть за кордон, да тут князь Гвидон.
Опять прислал поклон, да приглашение на угощение,- надо принимать политическое решение.

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

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

До ночи решал Салтан задачку, в итоге свалился в спячку. Снились ему матрицы и точки, да на болоте кочки. На кочку прыгнул Нео с острова Борнео.
— Если хочешь добраться ко сроку — плыви по максимальному потоку.
— Чего? — Салтан почти проснулся. Но Нео уже в зайца обернулся.

См. две другие статьи этой группы — Делаем многозадачность и Преемптивность: как отнять процессор.

Сразу просьба к строгим читателям. Если вы не поняли какой-либо термин из применённых — спросите, я подскажу, что я имел в виду. А если вам нравится другое написание или перевод этого термина — укажите его в комментарии. Я применяю те, которые нравятся мне.

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

Как я уже говорил, шедулер — это просто функция, которая отвечает на вопрос: какую нить и на сколько времени поставить на процессор.

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

Говоря о шедулере нельзя не сказать о приоритетах.

Приоритет — свойство нити (или процесса) влияющее на конкуренцию этой нити с другими нитями за процессор.

Приоритет обычно описывается парой <класс приоритета, значение приоритета внутри класса>.

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

В этой работе рассматриваются вопросы, связанные с прямым и обратным преобразованием “программная переменная – сигнал”: особенности построения каналов передачи данных, подключения периферии к шинам процессора, вопросы адресной приёма-передачи данных и работа гипотетического процессора при обмене данными с внешним устройством.

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

Рис. 1. Схема с неопределенным напряжением в линии передачи. В реальной схеме функцию ключа может выполнять транзистор.

В схеме Рис. 1 при замыкании ключа приёмнику передается 5В источника, однако, когда ключ разомкнут на входе приемника находится неопределенное напряжение.
Этой неопределенности нет в схеме Рис. 2, которая имеет два устойчивых состояния 5В или 0В. Сопротивление R добавлено в схему передатчика для ограничения тока через замкнутый ключ. Переходный процесс в линии пропорционален произведению ёмкости линии на выходное сопротивление передатчика, которое отличается при установлении и сбросе напряжения в линии. При установке напряжения в линии происходит заряд ёмкости через сопротивление R. Во время сброса напряжения ёмкость разряжается через сопротивление замкнутого ключа.


Рис. 2. Передача двух состояний 5В и 0В. Тождественные схемы. Постоянная времени (R*C) перехода из 0В в 5В (заряда емкости) больше постоянной разряда линии через идеальный ключ с нулевым сопротивлением.

Привет всем. Продолжу о Фантоме. Для понимания полезно прочесть статью про персистентную оперативку, а так же общую статью про Фантом на Открытых Системах. Но можно и так.

Итак, мы имеем ОС (или просто среду, не важно), которая обеспечивает прикладным программам персистентную оперативную память, и вообще персистентную «жизнь». Программы живут в общем адресном пространстве с управляемыми (managed) пойнтерами, объектной байткод-машиной, не замечают рестарта ОС и, в целом, счастливы.

Очевидно, что такой среде нужна сборка мусора. Но — какая?

Есть несколько проблем, навязанных спецификой.

Во-первых, теоретически, объём виртуальной памяти в такой среде огромен — терабайты, всё содержимое диска. Ведь мы отображаем в память всё и всегда.

Во-вторых, нас категорически не устраивают stop the world алгоритмы. Если для обычного процесса остановка в полсекундны может быть приемлема, то для виртуальной памяти, которая, большей частью, на диске, это будут уже полчаса, а то как бы не полсуток!

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

Тут нужна оговорка. Вообще говоря, в системе, которая располагает парой терабайт виртуальной памяти, это не так уж критично — даже если не делать освобождение памяти полсуток, возможно, не так много и набежит — ну, например, истратится 2-3, ну 5 гигабайт, ну даже и 50 гигабайт — не жалко, диск большой.

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

Ок, итого у нас две задачи.

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

«Банда четырёх» была неправа, стандартная библиотека Ruby тоже ошибочна, и Rails – также. Но является ли нечто неправильным, если все так делают?

Да.

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

Они говорят: «композиция прежде наследования». Отлично, в этом есть смысл. Они говорят: «используйте делегирование». Отлично. Хотя в книге нет ни единого примера делегирования.

Делегирование – это приём, которому приписывают возможность внесения гибкости в программы. Обычно говорят, что делегирование – это способ достичь композиции. Но делегирование – это не то, что вы думаете, и «Банда четырёх» ввела вас в заблуждение. Хуже того, почти все упоминания о делегировании содержат лишь совместную работу объектов с пересылкой (forwarding) сообщений. Это примеры вызовов методов, а не делегирования.

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