Это продолжение поста про оффлайн алгоритмы упаковки.

Суть задачи: имеем полубесконечную полосу — как в тетрисе, только без game over'а, и конечный набор прямоугольников. Данные о прямоугольниках поступают в режиме реального времени; каждый новый прямоугольник необходимо немедленно разместить и больше не двигать с места. Цель — минимизировать общую высоту упакованных прямоугольников.
Это online-вариация задачи об упаковке прямоугольников в полуограниченную полосу (2 Dimensional Strip Packing, 2DSP).

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

Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

В чем, собственно, проблема?

Mail.Ru — огромный портал, существующий более 15-ти лет. За это время мы прошли путь от небольшого веб-проекта до самого посещаемого сайта рунета. В состав портала входит огромное количество сервисов, у каждого из которых своя судьба, и над каждым из которых работает отдельная команда. Разработчикам пришлось как следует потрудиться, чтобы на всех проектах — и новых, и старых, и тех, которые присоединились к порталу по мере его развития, — использовалась единая система авторизации. А через много лет перед нами встала фактически обратная задача: разделить пользовательские сессии. О том, зачем мы это делали, какие трудности нас ожидали и как мы их обошли, я расскажу в этом посте.

Вы, наверное, уже читали интересную статью о том, как можно отключать эффекты :hover при скроле – это позволяет здорово сохранить отзывчивость сайта, но имеет один недостаток – вам приходится опираться на один общий класс, и это плохо.

.hover .element:hover {
  box-shadow: 1px 1px 1px #000;
}

Чем дальше в лес, тем толще партизаны. Нет, не так. Чем старше веб, тем больше джаваскрипта

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

Осенью 2008 года мы потратили две-три недели свободного от основной работы времени, чтобы написать маленькую утилитку для бэкапа баз данных (MS SQL Server и потом MySQL). Сегодня она приносит нам около $230 000 в год и можно с уверенностью говорить, что суммарно мы заработаем на ней больше $1 000 000.

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