Привет, Хабр! В нашей работе часто возникает потребность в выделении сообществ (кластеров) разных объектов: пользователей, сайтов, продуктовых страниц интернет-магазинов. Польза от такой информации весьма многогранна – вот лишь несколько областей практического применения качественных кластеров:

1. Выделение сегментов пользователей для проведения таргетированных рекламных кампаний.
2. Использование кластеров в качестве предикторов («фичей») в персональных рекомендациях (в content-based методах или как дополнительная информация в коллаборативной фильтрации).
3. Снижение размерности в любой задаче машинного обучения, где в качестве фичей выступают страницы или домены, посещенные пользователем.
4. Сличение товарных URL между различными интернет-магазинами с целью выявления среди них групп, соответствующих одному и тому же товару.
5. Компактная визуализация — человеку будет проще воспринимать структуру данных.

С точки зрения машинного обучения получение подобных связанных групп выглядит как типичная задача кластеризации. Однако не всегда нам бывают легко доступны фичи наблюдений, в пространстве которых можно было бы искать кластеры. Контентые или семантические фичи достаточно трудоемки в получении, как и интеграция разных источников данных, откуда эти фичи можно было бы достать. Зато у нас есть DMP под названием Facetz.DCA, где на поверхности лежат факты посещений пользователями страниц. Из них легко получить количество посещений сайтов, как каждого в отдельности, так и совместных посещений для каждой пары сайтов. Этой информации уже достаточно для построения графов веб-доменов или продуктовых страниц. Теперь задачу кластеризации можно сформулировать как задачу выделения сообществ в полученных графах.

Не так давно состоялся релиз Scala 2.11.0. Одним из примечательных нововведений этой версии являются квазицитаты — удобный механизм для описания синтаксических деревьев Scala с помощью разбираемых во время компиляции строк; очевидно, что в первую очередь этот механизм предназначен для использования совместно с макросами.

Удивительно, но на хабре пока тему макросов в Scala рассматривают не слишком-то активно; последний пост
с серьёзным рассмотрением макросов был аж целый год назад.

В данном посте будет подробно рассмотрено написание простого макроса, предназначенного для генерации кода десериализации JSON в иерархию классов.

В последнее время в научных публикациях всё чаще упоминается алгоритм достижения консенсуса в распределенных системах под названием Paxos. Среди таких публикаций ряд работ сотрудников Google (Chubby, Megastore, Spanner) ранее уже частично освещенных на хабре, архитектуры систем WANdisco, Ceph и пр. В то же время, сам алгоритм Paxos считается сложным для понимания, хоть и основывается он на элементарных принципах.

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

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

И вот, однажды я решил портировать библиотеку на PHP, и теперь хочу поделиться ею с народом и очень надеюсь на помощь в ее улучшении: буду рад советам, баг-репортам и особенно pull-реквестам. Библиотека находится на GitHub'е: github.com/Andre-487/php_rutils

UPD от 26.10.2013: теперь библиотека так же доступна через Composer: packagist.org/packages/andre_487/php_rutils
Так же хочу сказать спасибо всем, кто помог улучшить библиотеку и довести ее до стабильного релиза.

Возможности библиотеки

PHP RUtils — порт Pytils на PHP. Это утилиты для работы с русским текстом. Утилиты разделены на следующие модули (классы):

• Numeral — работа с числами: склонение существительных в зависимости от количества, числа прописью, суммы денег в рублях и копейках прописью.
• Dt — работа с датами: расширение формата дат PHP русскими именами месяцев, дней недели; временные периоды (например, 24 976 дней назад).
• Translit — транслитерация, подготовка строк для использования в URL'ях, именах файлов.
• Typo — небольшой набор правил типографики простого текста.

Итак, этот пост будет немного «поспешным», что неудивительно для субботнего утра (оригинальная статья была опубликована 18-ого августа 2007-ого года. прим.пер.), но я хочу сослаться на этот топик в одной работе, которой собираюсь заняться этой осенью. Я планирую плодотворно поработать: создать несколько ресурсов со ссылками в интернете, которые помогут детям в создании своих первых проектов, а также в обучении таким предметам как физика, физика космоса и робототехника/электроника. Если вы знаете меня, то вы знаете, что я довольно долго изучал эти вещи. Проблема в процессе обучения этим предметам в наше время в том, что они чересчур абстрактны и часто ограничиваются теорией «на бумаге». Чтобы изучить эти предметы на уровне более высоком, чем просто знание тривиальных вещей и фактов, вы должны по-настоящему «заниматься» наукой, а не просто «читать» о них.

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

Продолжение перевода статьи Джона Оллспоу о личных качествах ведущих разработчиков.

Зрелые разработчики не жалуются просто так

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

Доброй пятницы, уважаемый хабр!

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

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

Предположим, что ваша любимая игра все же запустилась. Сначала радости нет предела. Но только до тех пор, пока вы не обнаружите, что максимальное доступное разрешение — 1024х768, а то и вовсе 800х600. На современном мониторе это означает огромные элементы GUI игры, смазанную картинку, а если монитор широкоформатный — еще и сильно искаженные, «пузатые» пропорции. Некоторых фанатов такие мелочи, конечно же, не смущают. Но зачем отказывать себе в максимальном удовольствии от игры, если решить проблему не так уж и сложно?

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

Директивы — это ключевая особенность AngularJS. С помощью директив можно добавлять новое поведение существующим HTML элементам, можно создавать новые компоненты. Примерами директив, добавляющих новое поведения для существующих HTML элементов, могут служить input, select, textarea в связке с ngModel, required и т.п. Перечисленные директивы в основном связаны с валидацией форм в AngularJS. Но тема валидации заслуживает отдельной статьи.

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

Если вы разрабатываете приложение на AngularJS и не создаете директивы, то это уже само по себе немного настораживает. Либо ваше приложение достаточно простое и уложилось в стандартные возможности AngularJS, либо, скорее всего, что-то не так с архитектурой вашего приложения. А если у вас при этом есть работа с DOM-ом в контроллерах или сервисах, то вам однозначно надо разбираться с темой создания директив, т.к. манипуляций с DOM-ом не должно быть нигде, кроме директив.

В данной статье я постараюсь рассмотреть процесс создания собственных директив на нескольких примерах.

Здравствуйте, Хабравчане!
Предлагаю вашему вниманию историю своего участия и победы в финале конкурса по программированию CodeTanks 2012.



Про соревнование я узнал на Хабре, решил выяснить подробнее, пошел на сайт проекта. Обрадовала возможность писать на С++ под Linux без танцев с бубном. Сразу подумалось, что будет выигрыш в производительности по сравнению с участниками, пишущими на языках типа Java/Python. Ну и сам формат соревнования мне понравился: до первого раунда две недели, дальше по неделе перерыва между раундами. Не нужно в жутком цейноте рожать правильно работающий код, а можно относительно спокойно все продумать и запрограммировать. Дальнейшее изучение правил и просмотр боев на сайте только укрепили решение участвовать: мне гораздо более интересно программировать AI в сложном и плохо определенном окружении, чем в полностью формализованном, типа настольных игр.

Первая статья цикла

Интро

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

Введение

Задача RMQ весьма часто встречается в спортивном и прикладном программировании. Удивительно, что на Хабре ещё никто не упомянул эту интересную тему. Попробую восполнить пробел.

Аббревиатура RMQ расшифровывается как Range Minimum (Maximum) Query – запрос минимума (максимума) на отрезке в массиве. Для определённости мы будем рассматривать операцию взятия минимума.

Пусть дан массив A[1..n]. Нам необходимо уметь отвечать на запрос вида «найти минимум на отрезке с i-ого элемента по j-ый».



Рассмотрим в качестве примера массив A = {3, 8, 6, 4, 2, 5, 9, 0, 7, 1}.
Например, минимум на отрезке со второго элемента по седьмой равен двум, то есть RMQ(2, 7) = 2.

В голову приходит очевидное решение: ответ на каждый запрос будем находить, просто пробегаясь по всем элементам массива, лежащим на нужном нам отрезке. Такое решение, однако, не является самым эффективным. Ведь в худшем случае нам придётся пробежаться по O(n) элементам, т.е. временная сложность этого алгоритма – O(n) на один запрос. Однако, задачу можно решить эффективнее.

• Часть 1
• Часть 2

Предисловие

Данный текст является переводом и сокращённым пересказом начальных глав книги Чарльза Э. Хоара. Целью является ознакомление русскоязычной аудитории с данной алгеброй исчисления процессов, коя нашла достаточно широкое применение в современной вычислительной науке в связи с большим распространением параллельных систем. Наиболее близкими и понятными практическими применениями CSP, думаю, будут являться следующие языки программирования:

• Erlang
• Go
• Limbo

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

(Окончание перевода статьи Эдди Османи о сравнении и выборе библиотеки для проекта со значительной ролью JS на клиенте.)
Содержание первой части:

■ Что такое MVC или, лучше сказать, MV*?
■ Когда нам нужен MV*-фреймворк JS?
■ Где же мы будем нуждаться в MV*, а где нет?
■ Проблема выбора: слишком много вариантов?
■ TodoMVC: общее приложение для обучения и сравнения
■ Предложенные нами критерии выбора фреймворка
■ Dojo и усложнение фреймворков на JavaScript
■ Коллекция TodoMVC (фреймворки, на которых сделаны реализации тестового приложения Todo)

Первая часть короткого и жесткого введения в Haskell. Вторую часть можно найти здесь

tl;dr: Очень краткое и сжатое введение в Haskell.

• Введение
  
  • Установка
  • Без паники
  • Самые основы Haskell
    
    • Объявление функций
    • Пример использование типов
    
    
  
  
• Необходимый минимум из Haskell
  
  • Выражения
    
    • Арифметические
    • Логические
    • Возведение в степень
    • Списки
    • Строки
    • Кортежи
    • Разбираемся со скобками
    
    
  • Полезные вещи для записи функций
  
  
• Сложная часть
  
  • Функциональный стиль
    
    • Функции высшего порядка
    
    
  • Типы
    
    • Вывод типов
    • Создание новых типов
    • Рекурсивные типы
    • Деревья
    
    
  • Бесконечные структуры
  
  

UPD. Если туториал вам понравился, черкните пару строк автору оригинальной статьи. Человеку будет приятно ;)

В последнее время я все чаще слышу о NoSQL и о графовых базах данных в частности. Но воспользовавшись хабропоиском с удивлением обнаружил, что статей на эту тему не так и много, а по запросу «Neo4j», так вообще 4 результата, где косвенно упоминается это название в тексте статей.

Что такое Neo4j?

Neo4j — это высокопроизводительная, NoSQL база данных основанная на принципе графов. В ней нет такого понятия как таблицы со строго заданными полями, она оперирует гибкой структурой в виде нод и связей между ними.

Как я докатился до этого?

Уже более года я не использовал в своих проектах SQL, с того времени, как попробовал документо-ориентированную СУБД "MongoDB". После MySQL моей радости не было предела, как все просто и удобно можно делать в MongoDB. За год, в нашей студии создания сайтов, переписали тройку CMS, использующих основные фишки Mongo c её документами, и с десяток сайтов работающих на их основе. Всё было хорошо, и я уже начал забывать, что такое писать запросы в полсотни строк на каждое действие с БД и все бы ничего пока на мою голову не свалился проект с кучей отношений, которые ну никак не укладывались в документы. Возвращаться к SQL очень не хотелось, и пару дней я потратил чисто на поиск NoSQL решения, позволяющего делать гибкие связи — на графовые СУБД. И по ряду причин мой выбор остановился на Neo4j, одна из главных причин — это то, что мой движок был написан на PHP, а для неё был написан хороший драйвер "Neo4jPHP", который охватывает почти 100% REST-интерфейса, предоставляющегося сервером Noe4j.

Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.

Привет!

О плагине JsTree на хабре упоминалось лишь в далеком 2009 году. С тех времен все довольно сильно поменялось. Плагин активно развивается. Страница проекта на гитхабе.

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



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

Что мы имеем?

• Построение дерева на основе html разметки, json и xml формата
• Drag & drop с тонкой настройкой возможности перемещения нодов по дереву
• Динамическое добавление/удаление/изменение нодов
• Возможность построения нескольких деревьев на одной странице и манипуляция нодами между этими деревьями
• Возможность присвоения нодам произвольных типов (file, folder, drive, да какой угодно), и указать отдельное поведения для каждого
• Поддержка тем оформления (на скрине в начале статьи пример того, как это реализовал я)
• Управление с клавиатуры
• Использование нативных и кастомных чекбоксов
• AJAX подгрузка нодов, запоминание состояния дерева
• Плагин красиво и читабельно написан, позволяет писать дополнительные плагины к нему и без проблем кастомизировать.
• Удобная система байндингов для обработки событий
• Мультиязычность
• Управление анимацией раскрытия
• Поиск по дереву
• Кастомное контекстное меню
• Поддержка браузеров: IE 6+, Firefox 2+, Safari 3+, Opera 9+, Chrome
• Мини-фича, которая меня особенно порадовала — плагин wholerow — выделения нода во всю ширину. А-ля mac style

Современные системы мониторинга “из коробки” позволяют отслеживать практически все показатели отдельного узла системы, но обладают рядом существенных недостатков

• зная все об одном узле, о работе системы в целом они не имеют никакого представления — попробуйте из коробки выдать руководству “в данный момент у нас 1200RPS на фронте, 90% страниц отдается за 300мс, 95% за 650мc, системных ошибок и таймаутов происходит меньше 10 в секунду” (см картинку под катом)
• выход за рамки одного из системных показателей одного из узлов системы еще не значит, что стоит бить тревогу — возможно узел попал под повышенную нагрузку, или разработчики сменили алгоритм
• в рамках мониторинга отдельных узлов практически невозможно уследить постепенную деградацию сервиса — как правило он срабатывает только когда уже “ничего не работает”
• деградация производительности внешних сервисов не отслеживается в принципе (вас никогда не банил CDN?)

На исходной у нашей площадки более 1.000.000 уников, ~100.000.000 http запросов на фронтенд в сутки и развесистый, в плане сопровождения, зоопарк проектов. Набор ключевых слов — nginx, apache, php (двух вариаций), oracle. С заядлой периодичностью возникают ситуации “у нас все работает” по отдельно взятым зонам ответственности либо, что тоже не редкость, “у вас ничего не работает”. На границах ответственности идет сплошная передача тикетов.
Мы не стали изобретать велосипед и решили сделать мониторинг по времени и корректности отклика пользователю с отслеживанием отклика бекендов, а также какие из них были задействованы при обработке конкретного запроса. Ну и плюс наши объемы — не сильно большие, но несколько граблей по ходу изложения можно продемонстрировать.

Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

От переводчика

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

Также прошу прощения за отсутствие перевода словосочетания “computer science”. В русском языке нет адекватного ему словосочетания. Всякие «информатики» и «компьютерные науки» — это либо дискредитировавшие себя понятия, либо бессмысленные переводческие суррогаты. Английское понятие “computer science” содержит историческую игру слов, которая в переводе на русский язык должна выглядеть как-то так: «науки о вычислениях, обработке информации и вычислительных устройствах». Думаю, лучше оставить оригинальное “computer science”. Во всяком случае, в таком виде это словосочетание позволит вам самим подобрать нужный контекст из всего многообразия, представляемого им в оригинале.

Почему я решил перевести этот текст (ведь он короткий и не особо насыщенный откровениями)? Потому, что это выступление Кармака. А он, как-никак, знаковая фигура в отрасли разработки ПО. То, что написано ниже, показывает отрыв теории разработки ПО от практики. Ведь, если эти мысли посещают такого разработчика и выносятся на QuakeCon, — то что тогда творится в головах рядовых прикладных программистов?