После большого перерыва продолжаем цикл о графических вероятностных моделях (часть 1, часть 2). Сегодня мы наконец-то от постановок задач перейдём к алгоритмам; поговорим мы о самом простом, но часто полезном алгоритме вывода на фактор-графах – алгоритме передачи сообщений. Или, как его ещё можно назвать, алгоритме правильной расстановки скобок.


by sergey-lesiuk

Вот некое простое значение:


И мы знаем, как к нему можно применить функцию:


Элементарно. Так что теперь усложним задание — пусть наше значение имеет контекст. Пока что вы можете думать о контексте просто как о ящике, куда можно положить значение:


Теперь, когда вы примените функцию к этому значению, результаты вы будете получать разные — в зависимости от контекста. Это основная идея, на которой базируются функторы, аппликативные функторы, монады, стрелки и т.п. Тип данных Maybe определяет два связанных контекста:

data Maybe a = Nothing | Just a

Позже мы увидим разницу в поведении функции для Just a против Nothing. Но сначала поговорим о функторах!

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



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

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

Хвост виляет собакой. ("Wag the dog") — чтобы избежать большого скандала или «замять», оставить незамеченным какое-нибудь важное, но неприятное событие, часто используется простой, но хитрый и ловкий приём, который англоязычные политтехнологи называют «Wag the dog», а русскоязычные — «Хвост виляет собакой». Он заключается в том, чтобы вовремя поднять волну обсуждения вокруг вопроса второстепенной важности, на фоне которой другое, более важное событие или действие пройдёт незаметно.
Примеры таких вопросов: Отмена перехода на зимнее время, российское гражданство Депардье, поездка Путина или Саши Грей на Ладе Калине по России, полёты со стерхами и т.д.
Своё название этот приём получил в честь английского выражения tail wagging the dog, который, в свою очередь, появился из следующего народного пассажа:

— Почему собака виляет хвостом?
— Потому, что собака умнее, чем хвост. Если бы хвост был умнее, он вилял бы собакой.

По роду занятий я часто общаюсь с различными русскими и западными командами. Очень частый вопрос — есть ли какая-нибудь специфика в работе наших и как это влияет на разработку?

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

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

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

Я буду приводить влияние разных факторов в порядке их важности и силы влияния. Чем выше — тем сложнее это изменить и тем больший эффект это оказывает.

Разумно ли ожидать, что каждый разработчик будет мастером в любом аспекте процесса разработки? Вероятнее всего нет, однако Facebook может потребовать от вас это. Будучи на конференции OSCON, работник Facebook сказал мне, что они нанимают только «Full Stack» разработчиков. Хорошо, но что это значит?

Для меня, «Full Stack» Разработчик — это кто-то, кто знаком с каждым аспектом: превосходно владеющий многими из них и проявляющий неподдельный интерес ко всем технологиям.

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

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

Тут видишь то большой куб с выпиленным куском, то маленький кубик, стоящий в углу.

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

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

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

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

Что же это за проблемы?

«Качество появляется только тогда, когда кто-нибудь несёт ответственность лично».
— Фредерик Ф. Брукс



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

Предлагаю вашему вниманию вольный перевод эссе "A Generation Lost in the Bazaar" Пола-Хеннинга Кампа, повествующего нам о печальной судьбе поколения IT-профессионалов, выросших в период бума доткомов, а также о фундаментальных проблемах в UNIX, напрямую влияющих на качество и портабельность ПО. Обо всём по порядку.

Древний холивар о том, нужна ли программисту математика, получил неожиданное продолжение в спорах о ЕГЭ. Активно начала продвигаться идея о том, что вообще не надо проверять знания, а надо проверять умение быстро искать ответы. Ну и как вывод – замена ЕГЭ на чемпионат по поиску в Гугле/Яндексе. На мой взгляд, с тем же успехом можно проводить экзамен в виде поиска по школьной библиотеке. Почему-то никто не замечает такой очевидной истины, что быстро находит ответы те, кто знают, что искать, то есть как раз обладают знаниями. Для подтверждения этой идеи я составил 3 задачки для программистов, алгоритмы решения которых я нашел бы за пару минут.

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

«Математика — это язык, на котором написана книга природы»(Г. Галилей)
«Математика – это наука о необходимых заключениях»(Б. Пирс)
«Математика – это строгий язык, служащий для перехода от одних опытных суждений, к другим»(Н. Бор)
«Математика – это иерархия формальных структур»(Н. Бурбаки)
«Математика — это наука о количественных отношениях и пространственных формах действительного мира»(А. Колмогоров)

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

Снова здравствуйте, дорогие мои хабраюзеры! Отгремел, не так громко, как хотелось бы, Computex 2013. Вчера радовали кого-то трансляции с Apple WWDC и Е3. Но сегодня не будет никакого железа, никаких новинок и технологий. Сегодня будут девушки с Computex и только они. Я даже не стану расписывать на каких стендах красотки завлекали посетителей, просто смотрите и плюсуйте. ОСТОРОЖНО, под катом много фоток.
Можно устроить импровизированную голосовалку в комментариях, какая из барышень наиболее понравилась хабражителям.

[ english version ]
Периодически проверяя нет ли реализации того или иного стандартного алгоритма в jdk, пришла мысль составить подобный обзор. Также интересны были причины наличия/отсутствия многих известных структур данных.
Формат обзора — только ключевые свойства и особенности структур и алгоритмов в составе jdk, подробности и детали — расписаны в javadoc или легко найти в исходниках.
Надеюсь на конструктивную критику и коллективный разум если что упустил.
Хватит вступлений, итак, давайте рассмотрим что включает в себя текущий jdk 7 и почему.

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

Дано

• JavaSE 6+
• библиотека с асинхронным методом

void A.asyncMethod(Callback callback);

• метод, который нужно переопределить, и вернуть из него результат

@Override
Object overridenMethod() {
	return syncMethod();
}

Задача

Преобразовать асинхронный вызов метода в синхронный с возвращением результата.

Здравствуй, %USERNAME%!

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

Я люблю desktop-приложения. Признаваться в этом нынче, похоже, стыднее, чем в связях с иностранной разведкой, но это так. Нет, это не значит, что я не люблю интернет-технологии. Более того, некоторые я не только уважаю, а даже более-менее знаю. Но, тем не менее, я скучаю по тем временам, когда программа писалась на одном компьютере, потом компилировалась и запускалась на других, разных компьютерах. Тогда везде (почти) была одна система — Windows с одной и той же API, почти не было проблем совместимости на уровне приложений, никто не материл разработчиков браузеров — все берегли нервы на разработчиков WinAPI, которые умудрялись создавать конфликты даже внутри нее одной. Но это я, конечно, иронизирую, а если серьезно — иногда и сейчас хочется написать просто desktop-приложение, да так, чтобы работало оно на всех популярных системах. Трудно? Если подумать и покопать, то не очень.

Еще я люблю языки высокого уровня с аккуратной архитектурой и строгой типизацией. Мои фавориты — Java и C#. Оба они предоставляют разработчику множество преимуществ по сравнению с C++, оба избавляют от ряда забот. Чем приходится платить? Тем, что таскаешь за собой тяжелую колоду, которая называется Oracle JVM, .NET или mono. Все три колоды весят сотни мегабайт и лицензию имеют такую, что каждый пользователь вынужден качать эту штуку сам, не путая при этом разрядность своего компьютера, а главное — программа на Java не может быть совместима со всеми версиями JVM разом, не так ли? И вот — мы приходим к тому, что просто скинуть программку другу (или миллиону друзей) и не заботиться о том, что она у него не запустится, не выходит. Приходится делать хитрые сетапы, вбивать костыли, и это я еще не упомянул .NET — однажды я видел у друга сразу 3 установленных версии, причем все три были нужны разным приложениям…

Стоп! А давайте напишем программу на Java, но так, чтобы она не требовала установки на машину какой-либо JVM, чтобы одним касанием собиралась под Windows, Linux и OS X и чтобы при этом занимала совсем чуть-чуть; так, чтобы никто даже не понял, что она написана, скажем, не на C. Невозможно? Совсем наоборот! (И нет, я имею в виду не gcj, который лишает Java всех ее прелестей. Рефлексия будет работать и даже сторонние jar вы сможете запускать).

На Coursera сейчас идёт курс Introduction to Data Science от University of Washington, в ходе которого студентов будут учить работе с большими массивами данных, статистическому анализу, data mining, алгоритмам машинного обучения и прочим таким вещам. Авторы курса приглашают организации (коммерческие, некоммерческие и даже просто отдельных людей), которым будет полезна помощь в работе с данными, принять участие, подкинув студентам для решения задачи из реальной жизни.

Схема примерно такая: организация формулирует задачу и предоставляет данные (собственные или из открытых источников), студенты её решают и пишут отчёт. Отчёт потом оценивается другими студентами, плюс организация даёт свой отзыв о работе.
В плюсе все: организация бесплатно получает рабочие руки мозги, а студент — опыт.

По мотивам одного вчерашнего поста про оптимизацию условных переходов при расчете x=sign(a,b)*min(abs(a), abs(b)) якобы в 10 раз. Краткая сводка:

• оптимизация налицо, но размер мнимый: не в 10 раз, а 2.5 раза;
• бенчмарки надо делать правильно: не надо мерить CPU stalls, RAM bandwidth итп вместо исследуемой функции;
• бенчмарки надо делать правильно: иначе могут дико дрожать;
• выставлять только приоритет прикольно, но на коротких бенчмарках зря: +0.5% скорости, -15% дрожания;
• нужно мерить исследуемую функцию и только ее, только так получаешь корректные данные;
• нужно греть проц, нужно считать минимум из N прогонов/секунд, только так побеждаешь дрожание;
• нужно пользовать SSE, с ним получилось 8.6 раз, причем код… читается.

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

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



Интересный метод, описан в статье «A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition» L.R. Rabiner, которая вводит модель скрытой цепи Маркова и описывает три ценных алгоритма: The Forward-Backward Procedure, Viterbi Algorithm и Baum-Welch reestimation. Несмотря на то, что эти алгоритмы представляют интерес только в совокупности, для большего понимания описывать их лучше по отдельности.