В первой части нашей темы мы рассмотрели решение задачи static RMQ за (O(nlogn), O(1)). Теперь мы разберёмся со структурой данных, называемой дерево отрезков, или интервалов (в англоязычной литературе – segment tree или interval tree). С помощью неё можно решать dynamic RMQ за (O(n), O(logn)).

Определение

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

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

Введение

Задача 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) на один запрос. Однако, задачу можно решить эффективнее.

Жизнь была прекрасна и все было в этом мире хорошо, пока почта с моего сайта не стала активно посылаться в спам практически всеми крупными почтовыми серверами. Особенно усердствовал в этом Gmail. Частенько меня принимали за спамера в Yandex, реже в mail.ru и rambler.

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

Вы PM. Как узнать – готова ли вёрстка к реальному использованию?
Вы заказчик. Как убедиться, что работа выполнена качественно?
Как оценить качество вёрстки?

Когда я стал тим-лидом, а позже PM, передо мной стала задача проверять вёрстку наших проектов. Нужно было выработать формальные, легкопроверяемые критерии, соответствие кода которым, должно было давать некую гарантию, что не будет факапов и ни клиент, ни программеры не сказажут потом “WTF?”.

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

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

Итак что же это за список?

Краткая версия теперь доступна на html5checklist.com (github), где можно вносить pull-request'ы.

История обновлений:

• 2015/08/11: Актуализировал рекомендации по оптимизации скорости загрузки. Добавил требование поддержки Retina. Дополнил «19. Мелочи» требованием что изображения должны масштабироваться в зависимости от размера окна.
• 2015/08/10: актуализирован список исключений для CSSLint
• 2015/07/29: актуализирован пункт №13 «плохо»/«хорошо»
• 2015/04/08: добавлено требование использования препроцессоров и рекомендация использования систем сборки
• 2013/04/25: добавлены анализаторами качества кода: CSSLint и JSHint, указан сайт подбора css font stack (спасибо @fliptheweb), мелкие уточнения (работу интерактивных элементов страницы, что не пропадает фон на высоких разрешениях, не должно быть пустых презентационных блоков, при проверках контента — пробовать удалять заголовки, менять местами блоки)
• 2013/04/24: добавил пункт об минимизации каскада (БЭМ-техники, MCSS, SMACSS), необходимости вписывания в экран моб. устройства, заменил ссылку на проверочный текст отображения стандартного html на код с normalize.css, поправил пример где в рекомендации встречался длинный каскад, упомянул про Opera на Presto и новый уровень семантики — в именах классов BEM.
• 2012/04/12: отсортировал пункты проверки в порядке важности, выделил главные, дополнил статью подробностями
• 2011/12/07: дополнил согласно доклада на WSD Минск'2011.
• 2011/07/19: добавлено про повышение надёжности вёрстки благодаря html5-тэгам, про необходимость favicon/apple-touch-icon, отсутствие багов при ресайзе textarea
• 2011/06/15: добавил пояснения какие ошибки валидации допустимы, рассказал про отсутствие официальной кнопки «HTML5 Valid» и про официальное лого HTML5 на сайте.

Есть один замечательный вопрос, который возникает в любой дискуссии связанной с юнит-тестированием. «Надо ли создавать тесты для юнит тестов». Ответом на этот вопрос, как правило, служит технология Code Coverage. Действительно, если вы хотите убедиться в том, что юнит тест подготовлен правильно, вам нужно только проверить вызываются ли все ветвления в коде. Достигается это простым методом – надо подать на вход проверяемой функции все комбинации данных, которые позволят обойти эти ветвления. И академические примеры из документации это показывают.

Но подвох в том, что реальный мир сложнее. Функции приложения могут учитывать условия не только подаваемые на вход. Как быть в этом случае?

Интеграционное тестирование (в отличие от Unit- или модульного тестирования) это тестирование не отдельных атомарных компонентов системы (классов) а результата их взаимодействия между собой в какой-либо среде.

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

О том, как можно Unit-тестировать JavaScript я писал ранее, сейчас же расскажу о процессе интеграционного тестирования, применяемого в команде.

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

Введение

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

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

B-деревья также представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Но, в отличие от остальных деревьев, они созданы специально для эффективной работы с дисковой памятью (в предыдущем примере – сторонним носителем), а точнее — они минимизируют обращения типа ввода-вывода.

Натолкнулся в разделе QA на интересный вопрос. Ответ на него заставил написать эту статью как бОлее полный ответ на вопрос «как организовать поиск по множеству параметров, как в Яндекс-маркете, например».

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

Итак, что имеем в «ДАНО»

• Имеем 120 чекбоксов — вариант 1/0
• Имеем 30 «радио» с выбором «да/нет/не важно»
• Имеем 2-3 слайдера для указания диапазона цен/размера чего нить
• Имеем самое главное: 12 млн записей в БД.
• Имеем Select * From tovar Where (wifi=true) and (led=false) and (type=3) and ….остальные параметры …; со временем выполнения близкому к истерике клиента.

Обзор практически всех *top утилит под linux (atop, iotop, htop, foobartop и т.д.).

top

Все мы знаем top — самую простую и самую распространённую утилиту из этого списка. Показывает примерно то же, что утилита vmstat, плюс рейтинг процессов по потреблению памяти или процессора. Совсем ничего не знает про загрузку сети или дисков. Позволяет минимальный набор операций с процессом: renice, kill (в смысле отправки сигнала, убийство — частный случай). По имени top суффикс "-top" получили и все остальные подобные утилиты в этом обзоре.

atop

Atop имеет два режима работы — сбор статистики и наблюдение за системой в реальном времени. В режиме сбора статистики atop запускается как демон и раз в N времени (обычно 10 мин) скидывает состояние в двоичный журнал. Потом по этому журналу atop'ом же (ключ -r и имя лог-файла) можно бегать вперёд-назад кнопками T и t, наблюдая показания atop'а с усреднением за 10 минут в любой интересный момент времени.

В отличие от top отлично знает про существование блочных устройств и сетевых интерфейса, способен показывать их загрузку в процентах (на 10G, правда, процентов не получается, но хотя бы показывается количество мегабит).

Незаменимое средство для поиска источников лагов на сервере, так как сохраняет не только статистику загрузки системы, но и показатели каждого процесса — то есть «долистав» до нужного момента времени можно увидеть, кто этот счастливый момент с LA > 30 создал. И что именно было причиной — IO программ, своп (нехватка памяти), процесор или что-то ещё. Помимо большего количества информации ещё способен двумя цветами подсказывать, какие параметры выходят за разумные пределы.

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

В этой статье я бы хотел поделиться своими познаниями в кроссбраузерной и кроссмейлерной верстке почтовых рассылок. Под словом кроссмейлерность подразумевается — корректное отображение верстки во всех почтовых клиентах. Я считаю, что статья вполне актуальна, в виду того, что на хабре эта тема несколько раз освещалась, но некоторые нюансы были неточными, а другие просто устарели. По долгу службы я долгое время занимался версткой html расылок по всему миру, и приведенные ниже правила будут касаться следующих почтовых клиентов и веб-интерфейсов: MS Outlook 2003-2010, mail.ru, rabmler почта, Яндекс почта, Gmail, Yahoo! Mail (Classic), Thunderbird 2.0-3.0, Hotmail, Windows Live Mail, Apple Mail 3-4, AOL Mail, Lotus Notes 8-8.5.

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

Захотелось какого-то автоматизированного решения, и оно было найдено в виде системы статистики с открытым исходным кодом Piwik. Эту систему можно установить на свой сервер, добавить в нее ваш сайт и пользоваться. Она предоставляет функционал, в основном аналогичный GA и Я.Метрика, + имеется возможность написания собственных плагинов (например для себя я разработал виджет «вчера-сегодня-прогноз», аналогичный по функционалу такому же блоку из яндекс.метрики).

Сначала для тестов система вела статистику по 1 домену и 1 поддомену, и справлялась с этим вполне успешно, полностью заменив для меня Я.метрику и GA. Соответсвенно было принято решение использовать Piwik API для реализации автоматического подключения статистики к пользовательским поддоменам. Требовалось выполнить следующее:

1. Создать пользователя в системе Piwik
2. Создать сайт в пивике
3. Выдать пользователю права для просмотра статистики по сайту
4. Получить id сайта для установки счетчика

Позвольте мне начать своё повествование с рассказа про свободное время, семью и тягу к прекрасному. Свободного времени, которое я могу провести с женой, обычно очень мало. То я занят, то жена. То мы оба. Но иногда высвобождается час-другой, который можно провести вместе. А что можно сделать вместе? Ну, кроме того что вы подумали, можно ещё посмотреть вместе фильм. Сходить в кино, например, выбрав один из пяти унылых фильмов в кинотеатре. Или достать с полки DVD и в 5й раз посмотреть «Новинки 2006 года, 8 в 1». Но кому нужны новинки 2006 года в качестве для мобильного телефона или платить деньги за билеты в кино, если всё что нужно для удовольствия можно сделать у себя дома практически бесплатно? Если есть трекер на котором постоянно выкладываются сотни интересных фильмов? Если есть хороший телевизор и диван, на котором смотреть фильмы намного приятнее? Нет, иногда, конечно, приятно сходить в кино, или пересмотреть новинки 2006, но в большинстве случаев мы хотим (1) дома, (2) бесплатно посмотреть (3) новый фильм (4) в хорошем качестве (5) не дожидаясь пока он скачается.

Вступление

Доброго всем времени суток. Поздравляю вас с праздниками и перехожу к теме.
Когда вы выходите за рамки написания простых фрагментов jQuery и приступаете к разработке более сложных взаимодействий пользователей, ваш код может быстро стать громоздким и трудным для отладки. Эта статья покажет вам начать думать об этих взаимодействий в терминах «частичек поведения» используя паттерн проектирования object literal.

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

Но подождите. Допустим, теперь требования изменились. Теперь код, который работал для трех элементов должен работать для десяти. Или ваш код должен быть повторно использован для несколько иного приложения, в котором все идентификаторы разные. Как не потеряться в коде, который является не просто вызовом плагина или парой строчек типа show() и hide()?

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

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

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

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

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

Как Вы знаете — в разработке объёмного JS-приложения где используется популярнейшая библиотека jQuery наступает момент когда остро встаёт проблема производительности. Все силы кидаются на амбразуру профайлера, каждый вызов скрупулёзно исследован, каждый функционально нагруженный кусок реализации обнюхан со всех сторон и выправлен. Но беда поступает не с той стороны, откуда её ждут 90% разработчиков. Селекторы — Как много в этом слове.
Давайте разберёмся — как работает эта магия и почему поиск DOM-элементов может стать причиной падения производительности приложения.

Чтобы было понятно о чем речь, прикладываю 3 скринкаста, второй и третий под катом.

1. Знакомство с макетом #1
   

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

Данная статья давно назревала в моей голове, но совсем в ином формате.
Прочитав последние несколько неуклюжих статей на тему WEB-сервисов (например: http://habrahabr.ru/blogs/development/108973/) и применения в них REST технологии, решил что настало время все-таки откинуть лень, выделить время и написать «переформатированную» в своей голове статью.
Итак, кратко, что Вы найдете в статье и кому она будет полезна:

— новичкам, которые интересуются или планируют написать WEB-сервис для проекта
— профи вряд ли найдут что-то новое для себя
— общая идеология REST
— применение CRUD в WEB-сервисах
— принципы KISS при построении раутеров
— лучшие практики
— немного пиара ;)
— ссылки, литература

Добрый день, %username%!
За последний год столкнулся с несколькими задачами по написанию SOAP/REST API к различным сервисам и вывел для себя боле-менее удобную модель. Я не претендую на фундаментальное исследование, просто хочу поделиться опытом наступания на грабли.

Для начала общие требования к default API:

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