Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.

Но я все-таки решил попробовать.

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

Если оглядеться вокруг, то может сложиться впечатление, что отрасль разработки ПО шагает такими громадными шагами, что угнаться за ней нет никакой возможности. И если рассматривать всю отрасль в целом, то действительно это так и есть. Как-то сразу вспоминается старина Брукс со своим «Мифическим человеко-месяцем», когда он в заключении к своей книге пишет о том, как изменилась индустрия ПО в середине 90-х по сравнению с 50-ми годами. В те далекие годы (да, 90-е тоже уже далеки, так что уж говорить за эпоху зарождения индустрии сорока годами ранее) можно было прочитать все журналы (!), компьютерной тематики, которые выходили в свет. Сейчас же ежемесячно появляется десятки книг только по одной из популярных технологий, а количество статей просто не поддается счету.

На тему оптимизации MySQL запросов написано очень много, все знают как оптимизировать SELECT, INSERT, что нужно джоинить по ключу и т.д. и т.п.

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

Для определения страны по IP необходимы специальные базы данных, состоящие из диапазонов IP адресов и соответствующих им стран. Обычно такие базы данных распространяются в виде CSV или SQL файлов для использования в СУБД, либо бинарных файлов специального формата.

Для проведения тестирования была выбрана февральская база GeoLite Country, бесплатная версия GeoIP Country от MaxMind.

В тестировании приняли участие несколько популярных решений и мой «велосипед» на эту тему.

Элементарный пример цикла разработка примитивного ASP.NET (Mono) приложения с использованием Jenkins CI, по мотивам Построение «правильного» процесса разработки на платформе .NET.

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

При написании библиотеки на C++ многие сталкиваются с определенными трудностями при написании и организации кода. У некоторых уже есть готовые решения, у других их нет и они пытаются найти эти решения.

Некоторые трудности при написании кода библиотеки, в большей степени касающиеся «самодокументирования», можно решить с помощью «рабочих» пространств имен.

Для начала, опишем эти трудности и представим обычные способы решения.

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

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

Например, встречались такие варианты:

if ($error['type'] == E_ERROR || $error['type'] == E_PARSE || $error['type'] == E_COMPILE_ERROR){…}

или

if(in_array($error['type'], array(E_ERROR, E_PARSE,  E_COMPILE_ERROR)) {…}

В связи с этим решил написать небольшую статью о битовых операциях с примерами их использования.

Доступна для загрузки новая версия PhpStorm — среды разработки для PHP от компании JetBrains. Закачка идет быстро и нас здесь хорошо знают — так что буду краток.

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

• Анализ кода и поиск дубликатов помогут вам найти потенциальные ошибки и код низкого качества, рефакторинг — безопасно улучшить его
• Диаграммы классов UML помогут охватить взглядом структуру проекта и семантическое представлений изменений — локальных или из VCS
• Просмотр результатов профилирования c помощью Xdebug и Zend Debugger
• Поддержка PhpUnit 3.6 и всех опций командной строки
• CoffeeScript
• Рекурсивная синхронизация папок и гибкая настройка исключений FTP/SFTP
• Microsoft TFS, граф ревизий для git
• Новый интерфейс для всех операционных систем

Подробности и картинки

Уже скоро: релиз WebStorm 3.0 — поддержка Node.JS, JSLint и JSTestDriver

Работайте с удовольствием!

P.S. Ошибки — в трекер, вопросы — в форум, работа над 3.0.1 уже идет!

Если сделать так:

<?php $this->headScript()->appendFile('/js/my1.js');?>
<?php $this->headScript()->appendFile('/js/my2.js');?>
<?php $this->headScript()->captureStart() ?>
  var action = '<?php echo $this->baseUrl ?>';
<?php $this->headScript()->captureEnd() ?>

<?php echo $this->headScript(); ?>
<?php echo $this->magicHeadScript(); ?>

то вместо чего-то типа такого:

<script type="text/javascript" src="/js/my1.js"></script>
<script type="text/javascript" src="/js/my2.js"></script>
<script type="text/javascript">
  var action = '/123';
</script>

получим на выходе:

<script type="text/javascript" src="/cache/js/1b1004a203..._compressed.js"></script>


В компании, где я работаю, мы используем деперсонализированную базу с Production-a. Ее суммарный объем на данный момент около 30 ГБ. Обфускация ruby скриптом занимала около 6 часов. Ускорение обработки можно добиться, если переписать это все в хранимую процедуру (stored procedure). Но у нас в проекте они запрещены… Увы и ах.

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

Одновременная межсайтовая аутентификация (SSO), для чего же она нужна? Допустим у нас есть, назовём его анахроничным термином «портал», с блогами, фотками, фейлами (или файлами, кому как), назовём его fail.ru (не путать с одноимённым сервисом почты на букву М), причём всё это усложнено следующими факторами:
— функционал совершенно разный;
— код написан разными людьми, с испольованием разных технологий;
— работает всё это на разных серверах в разных датацентрах и с разными базами данных;
— сервера находятся на разных доменах.

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

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

Далее мы рассмотрим самописные альтернативы, OpenID, OAuth, SAML, и почему всё это в общем случае не слишком хорошее решение, вопросы хранения аутенитификационных данных, а также некоторые вопросы безопасности в которые без хороших знаний самому лезть не стоит, что такое вообще межсайтовая аутентификация, развеем некоторые мифы.

Некоторое время назад я гуглил интернет по поводу “REST vs SOAP”, прочитал пару статей и вроде бы все понял, но не почувствовал от этого никакого удовлетворения. Что-то было не так, то ли я не почувствовал основную идею, то ли просто читал, одновременно слушая новый музон и думая о новой фиче в проекте. Как появилось время, решил восполнить этот пробел, заодно написав полезную статью по этому поводу.

Итак, пришло время раскрыть некоторые карты и рассказать о том, как устроен Tactoom изнутри.

В этой статье я расскажу о разработке и выведении в production веб-сервиса с использованием:
NodeJS (fibers), MongoDB, Redis, ElasticSearch, Capistrano, Rackspace.

Как сказано на официальном сайте —

Pinba is a realtime monitoring/statistics server for PHP using MySQL as a read-only interface.

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

Это перевод статьи, датированной 1м сентября 2009 года, следует это учесть при прочтении. — прим. пер.

В последний месяц или два команда инженеров Digg потратила совсем немного времени на изучение, тестирование и окончательное внедрение Cassandra в продакшен. Это был очень веcёлый проект, но до того, как веселье началось, нам пришлось потратить какое-то время на выяснение того, что же представляет собой модель данных Cassandra… фраза «WTF is a «super column»» («что за фигня этот суперстолбец?») была произнесена не один раз.

Если вы работали ранее с РСУБД (это касается почти всех), вы вероятно будете немного обескуражены некоторыми названиями при изучении модели данных Cassandra. Мне и моей команде в Digg потребовалось несколько дней обсуждений, прежде чем мы «врубились». Пару недель назад в списке рассылки разработчиков шёл процесс bikeshed-а на тему полностью новой схемы именования для разрешения неразберихи. На всём протяжении дискуссии я думал: «может, если будет несколько нормальных примеров, люди не будут так смущены названиями». Так, это моя попытка объяснения модели данных Cassandra; она предназначена для того, чтобы вы ознакомились, но не уходили в дебри, и, надеюсь, это поможет прояснить некоторые вещи.

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

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

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

Прелюдия

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

В рамках данной статьи я поделюсь своим опытом проектирования сайтов средней сложности. Данный подход зарекомендовал себя понятным как разработчикам, так и клиентам. Я не собираюсь открывать Америку, представленные ниже инструменты всем прекрасно знакомы. Суть данной статьи как раз в том, что бы продемонстрировать насколько просто можно представить достаточно сложные задачи.

Кто здесь?

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

11:24:21 PM Michael: ну хз, надо пробовать
11:24:24 PM Michael: наверное так лучше
11:24:27 PM Michael: даже я думаю наверняка
11:24:36 PM Michael: но пока меня че-то останавливает
11:24:38 PM Michael: лень наверное :)

Знакомо? «Не хочется разбираться? Нет времени?» Тогда читаем дальше. В статье расскажу, как настроить свое любимое рельсовое окружении на разработку с подходом BDD и начать новую жизнь (опционально).

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G: