Предисловие

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

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

Так как исходный Chromium открыт, возникает закономерное желание подсмотреть, можно ли использовать технологию в своих корыстных целях наступления мира на земле.

Как это часто бывает, все уже сделано за нас в этой статье. Все оказывается очень просто, необходимо сделать POST запрос на адрес www.google.com/speech-api/v1/recognize со звуковыми данными в формате FLAC или Speex. Реализуем демонстрацию распознавания WAVE-файлов с помощью C#.

На обучающем ресурсе Udacity запустился мини-курс по веб-производительности от сотрудника Google Ильи Григорика.

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

• Batch-запросы
• Передача даты в составе сложной структуры данных
• Обозначение кастомных типов данных
• Проброс round-trip данных, которые сервер должен вернуть в ответе
• Дополнение запроса и ответа метаданными
• Обработка ошибок, пришедших в ответе

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

jsonex представляет собой попытку объединить решение упомянутых выше и многих других задач в рамках простого единого подхода, основанного на концепции вычислимых данных (callable data).

Комбинаторика в старших классах школы, как правило, ограничивается текстовыми задачами, в которых нужно применить одну из трёх известных формул — для числа сочетаний, перестановок или размещений. В институтских курсах по дискретной математике рассказывают и о более сложных комбинаторных объектах — скобочных последовательностях, деревьях, графах… При этом, как правило, ставят задачу вычислить количество объектов данного типа для некоторого параметра n, например количество деревьев на n вершинах. Узнав количество объектов для фиксированного n, можно задаться и более сложным вопросом: как все эти объекты за разумное время предъявить? Алгоритмы, решающие подобного рода задачи, называются алгоритмами комбинаторной генерации. Таким алгоритмам, например, посвящена первая глава четвёртого тома «Искусства программирования» Дональда Кнута. Кнут очень подробно рассматривает алгоритмы генерации всех кортежей, разбиений числа, деревьев и других структур. Придумать какой-нибудь алгоритм, работающий умеренно быстро, для каждой из этих задач несложно, но с дальнейшей оптимизацией могут возникнуть серьёзные проблемы.

В процессе написания магистерской диссертации, защищённой в Академическом университете, мне потребовалось изучить и применить один из алгоритмов комбинаторной генерации, подходящий для особого класса задач. Это генерация структур, на которых дополнительно введено некоторое отношение эквивалентности. Чтобы было понятно, о чём идёт речь, я приведу простой пример. Давайте попробуем сгенерировать все триангуляции шестиугольника. Получится что-нибудь такое:



Написать алгоритм, который вернёт все такие триангуляции, довольно несложно. Например, сгодится такая процедура: фиксируем какое-нибудь ребро (пусть это будет ребро 1-6), после чего в цикле перебираем вершины, не являющиеся его концами. На текущей вершине и фиксированном ребре строим треугольник, а оставшиеся после этого две области триангулируем рекурсивно. Если присмотреться к получающимся в результате работы этого алгоритма триангуляциям, то можно заметить, что многие из них почти одинаковы и отличаются лишь тем, как расставлены пометки (номера) вершин. Поэтому, полезно было бы придумать алгоритм, который будет генерировать так называемые непомеченные триангуляции — те, что изображены на следующем рисунке:

Почти два года назад вышла статья «What no one told you about z-index» (и её перевод на Хабре «То, что вам никто не говорил о z-index»), авторы которой рассказывают о малоизвестной (76% проголосовавших пользователей Хабра слышат об этом впервые), но документированной возможности создания нового контекста наложения указав opacity меньше единицы.

Но несмотря на название статьи, авторы не рассказали вам ещё кое о чём.


Новый контекст наложения формируется в случаях:

• Корневой элемент () всегда содержит корневой контекст наложения. Любой элемент на странице, не участвующий в локальном контексте наложения (сформированном любым из последующих вариантов), участвует в корневом контексте наложения.
  Элемент с position отличным от static и значением z-index отличным от auto. Кроме одного исключения для position: fixed, но я это вынес в отдельный пункт.
  Элемент имеет значение opacity меньше, чем 1.
  

В этом году в московском офисе Яндекса пройдёт юбилейная 25-я конференция Combinatorial Pattern Matching — главное в мире событие в области алгоритмов на строках.

Конференция начнётся с открытых лекций известных ученых, являющихся отцами-основателями серии конференций и внёсшими огромный вклад в область алгоритмов на строках:

• Альберто Апостолико (см., например, учебники и труды конференций на амазоне)
• Максим Крошмор (опять книги на амазоне)
• Юджин Майерс (один из авторов суффиксных массивов и BLAST-а, см. википедию).

Начиная с версии 1.5, в Firefox появился механизм кеширования, сохраняющий состояние страницы в памяти. Кеширование действует на одну сессию браузера. Перемещаясь по посещенным страницам с использованием кнопок «Назад/Вперёд», нет необходимости загружать страницу с сервера целиком. При этом вся страница, включая js-скрипты, как бы «консервируются» в том состоянии, в котором они были, когда пользователь их покидал. Данный механизм позволяет производить навигацию по посещенным страницам крайне быстро. Состояние кеша остается неизменным, пока действует сессия браузера (пока пользователь не закроет закладку, или браузер).

Не «баг», а «фича»

Помимо прочего, непонимание данного механизма браузеров вызывает настоящую головную боль у разработчиков. Рассмотрим пример.
Есть форма, данные которой мы хотим отправить на сервер. Мы хотим как-то визуализировать этот процесс и запускаем спиннер при отправке формы. Браузер переходит на следующую страницу. Если мы вернемся назад, используя кнопку браузера «Назад» (или через window.history.back()), то скорее всего увидим, что спиннер так и вращается, хотя на самом деле уже ничего не происходит.

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

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

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

1. Объектно-ориентированный код;
2. Работа с HTML5 (ArrayBuffer, Promises, WebCrypto (используется «dev nightly build» Google Chrome));
3. Возможность создавать, проверять, получать внутренние данные, изменять данные для следующих объектов:
   
   1. Сертификаты X.509
   2. Списки отзыва (CRL) X.509
   3. Запросы на сертификат (PKCS#10)
   4. OCSP запросы;
   5. Ответы OCSP сервера
   6. Time-stamping (TSP) запросы
   7. Ответы TSP сервера
   8. CMS Signed Data
   9. CMS Enveloped Data
   
   
4. Реализация собственной «certificate chain validation engine» на JavaScript;
5. … И многое другое! Смотрите под катом!

Современный мир программирования, а особенно веб и javascript уже давно не тот и имеет очень большое количество инструментов для той или иной задачи. В сегодняшнем посте я хотел бы рассказать как скрестить мощь AngularJS и молниеносность отображения view – Facebook React.

Всем известно, что когда мы генерируем коллекцию во view через Angular, то каждый элемент этой коллекции становится observable. Я конечно понимаю и знаю что есть определенный набор библиотек и решений как это обойти, но сегодня речь не об этом. Что же дает нам React? Ну одно из его преимуществ, это jsx синтаксис, который есть не что иным как html в javascript. Также есть возможность создавать reusable компоненты, наследовать их и использовать всю мощь что позволяет делать эта библиотека. Что же приступим.

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

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

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

JavaScript, как никакой другой язык, нуждается в именно таком объяснении. Функциональная природа, скрытая за Си-подобным синтаксисом, и непривычная прототипная модель наследования поначалу сильно сбивают с толку. Давайте мысленно понизим уровень JavaScript до простого процедурного, наподобие Си. Отталкиваясь от этого «недоязыка», переизобретем функциональное и объектно-ориентированное программирование.

MIT опубликовал исходники проекта Mylar — платформы для создания безопасных приложений, с шифрованием и
поиском по зашифрованным данным.

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

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

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



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

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

В предыдущих своих заметках я описал основу, на которой строятся lock-free структуры данных, и базовые алгоритмы управления временем жизни элементов lock-free структур данных. Это была прелюдия к описанию собственно lock-free контейнеров. Но далее я столкнулся с проблемой: как построить дальнейший рассказ? Просто описывать известные мне алгоритмы? Это довольно скучно: много [псевдо-]кода, обилие деталей, важных, конечно, но весьма специфических. В конце концов, это есть в опубликованных работах, на которые я даю ссылки, и в гораздо более подробном и строгом изложении. Мне же хотелось рассказать интересно об интересных вещах, показать пути развития подходов к конструированию конкурентных контейнеров.
Хорошо, — подумал я, — тогда метод изложения должен быть такой: берем какой-то тип контейнера — очередь, map, hash map, — и делаем обзор известных на сегодняшний день оригинальных алгоритмов для этого типа контейнера. С чего начать? И тут я вспомнил о самой простой структуре данных — о стеке.

Одной из самых интересных частей нового стандарта ECMAScript 6 являются стрелочные функции. Стрелочные функции, как и понятно из названия определяются новым синтаксисом, который использует стрелку =>. Однако, помимо отличного синтаксиса, стрелочные функции отличаются от традиционных функций и в других моментах:

• Лексическое связывание. Значения специальных переменных this, super и arguments определяются не тем, как стрелочные функции были вызваны, а тем, как они были созданы.
• Неизменяемые this, super и arguments. Значения этих переменных внутри стрелочных функций остаются неизменными на протяжении всего жизненного цикла функции.
• Стрелочные функции не могут быть использованы как конструктор и кидают ошибку при использовании с оператором new.
• Недоступность «собственного» значения переменной arguments.

Было несколько причин для введения этих отличий. Первоочередная — это то, что связывание (binding) используется довольно часто в JavaScript. Очень легко потерять нужное значение this при использовании традиционных функций, что может привести к непредсказуемым последствиям. Другая причина, это то, что JS-движки смогут легко оптимизировать выполнение стрелочных функций за счет этих ограничений (в противоположность традиционным функциям, которые могут быть использованы в качестве конструктора и которые свободны для модификации специальных переменных).

Рады сообщить, что в издательстве «Питер» вышел перевод новой книги Леонарда Сасскинда и Джорджа Грабовски — «Теоретический минимум» (ориг: The Theoretical Minimum: What You Need to Know to Start Doing Physics).

В Америке эта книга, несмотря на свой формат лекций по физике и классической механике, неожиданно стала настоящим бестселлером, а The Wall Street Journal вообще признал ее «Книгой 2013 года». В России книга вышла в издательстве «Питер» при поддержке гуманитарного фонда «Династия», цель которого — содействовать изданию лучших современных научно-популярных книг в области естественных и гуманитарных наук.



Мы уже издавали одну книгу Сасскинда на русском — «Битву при черной дыре» (пост о ней был на Хабре) — но «Теоретический минимум» по формату и содержанию кардинально от нее отличается.

MongoDB — замечательная база данных, которая становится все популярнее в последнее время. Все больше людей с SQL опытом начинают её использовать, и один и первых вопросов, который у них возникает: MongoDB transactions?.

Если поверить ответам со stackoverflow, то все плохо.

MongoDB doesn't support complex multi-document transactions. If that is something you absolutely need it probably isn't a great fit for you.

If transactions are required, perhaps NoSQL is not for you. Time to go back to ACID relational databases.

MongoDB does a lot of things well, but transactions is not one of those things.

Но мы не поверим и реализуем транзакции (ACID*) основанные на MVCC. Ниже будет рассказ о том, как эти транзакции работают, а тем, кому не терпится посмотреть код — добро пожаловать на GitHub (осторожно, java).

Пост не о MongoDB, а о том, как использовать compare-and-set для создания транзакций, а durability обеспчивается ровно в той степени, в которой её обеспечивает хранилище.

Кто пишет на Node.js и использует MySQL, тот непременно знает, что наш дорогой товарищ Felix Geisendörfer три года назад совершил героический и самоотверженный подвиг: в одиночку разработал очень качественный драйвер для подключения к MySQL, нативно реализовав двоичный протокол этой СУБД на JavaScript. Потом к проекту подключились другие уважаемые товарищи, была реализована поддержка пулов соединений, кластеров, транзакций, восстановление при временной утере соединения и т.д. Сейчас драйвер является самым развитым, хорошо проработанным и активно поддерживаемым из того, что мы имеем в открытых репозитариях npm и github. Удивительно даже, что при хорошо проработанной низкоуровневой реализации, все удобства, которые предоставляет это драйвер для прикладного разработчика, сводятся к одному методу query. Для меня лично, этого очень мало, ну привык дедушка к удобствам для возврата скалярных значений, строк и столбцов в массивы, интроспекции структур БД. Так что, с удовольствием делюсь этими наработками с вами, мои дорогие Хабравчане, но предупреждаю, что все удобства будут на улице. Есть конечно вариант тесной интеграции с драйвером, но FelixGe желает оставить драйвер исключительно низкоуровневым, поэтому я остановился на варианте внешней библиотеки с добавлением к драйверу через примеси. В виде примесей, удобства попали и в платформу Impress, а так же, опубликованы как патч к драйверу. О функционале и вариантах использования далее.

Сегодня мы завершаем новогоднюю серию постов, посвященных лекциям Школы анализа данных. Последний по порядку, но никак не по важности курс — «Алгоритмы и структуры данных поиска».

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

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



Лекции читает Максим Александрович Бабенко, заместитель директора отделения computer science, ассистент кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. М. В. Ломоносова, кандидат физико-математических наук.