[FF D8]

Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

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

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

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов ":" и ")", т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

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

Fat-Free чем-то похож на известный Ruby-фреймворк Sinatra. Автор Fat-Free помешан на минимализме и чистоте кода, что положительно отразилось на этом простом каркасе для разработки самых разнообразных приложений.

Fat-Free состоит из одного файла и весит всего 55KB. При этом фреймворк обладает таким функционалом: специфический и довольно удобный шаблонизатор, гибкое кеширование, автоматическая защита от спама, интегрированные средства для юнит тестов, профайлер кода.

Он настолько маленький и быстрый, что даже может использоваться для контроля траффика Web-сервера.

Это, также, единственный фреймворк, который защищает Ваше приложение от хотлинкинга и DoS атак.

Беспрецедентные объемы данных заставляют разработчиков и бизнес приглядываться к альтернативам реляционных баз данных, используемым вот уже более тридцати лет. В совокупности все эти технологии известны как «NoSQL базы данных».


Основной проблемой является то, что реляционные базы данных не могут справляться с нагрузками актуальными в наше время (мы говорим о high-load проектах). Есть три конкретные проблемных области:

• горизонтальное масштабирование при больших объемах данных, например как в случае Digg (3 терабайта для зеленых значков, отображаемых, если ваш друг сделал dugg на статье) или Facebook (50 терабайт для поиска по входящим сообщениям) или eBay (2 петабайта в целом)
• производительность каждого отдельного сервера
• не гибкий дизайн логической структуры.

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

Несколько лет назад ко мне пришел мой босс и сказал: «У нас есть новый проект для тебя. Это перенос сайта, который уже имеет 1 миллион посетителей в месяц. Тебенеобходимо его перенести и убедиться, что посещаемость может вырасти в будущем без всяких проблем.» Я уже был опытным программистом, но не имел никакого опыта в области масштабируемости. И мне пришлось познавать масштабируемость трудным путем.

Все началось с того, что прочитал статью на TechCrunch про приложение для iPad — Pulse. Это приложение для просмотра RSS-лент. Именно просмотра, потому что список выстраивается в горизонтальные ленты с превью изображений из каждой статьи. Их можно прокручивать, переходя к более ранним статьям.

Мне показалось это удобным и я полез сразу на сайт, узнать есть ли что-то подобное для PC (так как айпадов не имеем). К слову, после iPad ребята взялись за iPhone и мобильные устройства на базе Android и уже выпустили приложения и для них. Но вот версии для PC они не стали делать, причем на своем форуме писали, что это пока не планируется. Хотя в то же время я видел много вопросов именно с просьбой сделать что-то для обычного компьютера.

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Очень сильное колдунство

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

Вспомним-ка еще раз структуру дерамиды. В ней есть ключ x, по которому дерамида есть дерево поиска, случайный ключ y, по которому дерамида есть куча, а также, возможно, какая-то пользовательская информация с (cost). Давайте совершим невозможное и рассмотрим дерамиду… без ключей x. То есть у нас будет дерево, в котором ключа x нет вообще, а ключи y — случайные. Соответственно, зачем оно нужно — вообще непонятно :)

На самом деле расценивать такую структуру стоит как декартово дерево, в котором ключи x все так же где-то имеются, но нам их не сообщили. Однако клянутся, что для них, как полагается, выполняется условие двоичного дерева поиска. Тогда можно представить, что эти неизвестные иксы суть числа от 0 до N-1 и неявно расставить их по структуре дерева:

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

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

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Тема сегодняшней лекции

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

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

Ищем индекс

В математике, K-я порядковая статистика — это случайная величина, которая соответствует K-му по величине элементу случайной выборки из вероятностного пространства. Слишком умно. Вернемся к дереву: в каждый момент времени у нас есть декартово дерево, которое с момента его начального построения могло уже значительно измениться. От нас требуется очень быстро находить в этом дереве K-й по порядку возрастания ключ — фактически, если представить наше дерево как постоянно поддерживающийся отсортированным массив, то это просто доступ к элементу под индексом K. На первый взгляд не очень понятно, как это организовать: ключей-то у нас в дереве N, и раскиданы они по структуре как попало.

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение

В качестве введения рекомендую прочесть пост про двоичные деревья поиска того же winger, поскольку без понимания того, что такое дерево, дерево поиска, а так же без знания оценок сложности алгоритма многое из материала данной статьи останется для вас китайской грамотой. Обидно, правда?

Следующий пункт нашей обязательной программы — куча (heap). Думаю, также многим известная структура данных, однако краткий обзор я все же приведу.
Представьте себе двоичное дерево с какими-то данными (ключами) в вершинах. И для каждой вершины мы в обязательном порядке требуем следующее: ее ключ строго больше, чем ключи ее непосредственных сыновей. Вот небольшой пример корректной кучи:

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

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

Данный цикл статей посвящён низкоуровневому программированию, то есть архитектуре компьютера, устройству операционных систем, программированию на языке ассемблера и смежным областям. Пока что написанием занимаются два хабраюзера — iley и pehat. Для многих старшеклассников, студентов, да и профессиональных программистов эти темы оказываются весьма сложными при обучении. Существует много литературы и курсов, посвящённых низкоуровневому программированию, но по ним сложно составить полную и всеохватывающую картину. Сложно, прочитав одну-две книги по ассемблеру и операционным системам, хотя бы в общих чертах представить, как же на самом деле работает эта сложная система из железа, кремния и множества программ — компьютер.

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

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

Чаще всего встречается подход «добавим кучу RBL (DNSBL) и будем радоваться жизни». Подход не верный чуть более, чем полностью. Второй по популярности — контент-фильтры, зачастую купленные за бешеные деньги. Такой подход тоже в большинстве случаев совершенно неоправдан.

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

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

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

При разработке баз данных зачастую требуется обеспечить поддержку версионности и хранения истории объектов. Например, у работника может изменяться должность, у должности в свою очередь может меняться оклад — в многомерном моделировании это называется Slowly changing dimensions(далее SCD) — редко изменяющиеся измерения, то есть измерения, не ключевые атрибуты которых имеют тенденцию со временем изменяться. Всего существует 6 основных типов(методов) SCD, которые определяют как история изменений может быть отражена в модели.

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

Цель этой статьи — помочь тем, кто рассчитывает выйти на западные рынки с продуктом или технологией, быть готовыми к тому черному дню, когда вы получите по почте иск о нарушении патентных прав. Если вы рассчитываете на успех, то наивно рассчитывать, что вас обойдет чаша сия. Не обойдет. Правда, это вряд ли будет чаша. Скорее это будет большая неотесанная дубина. Дубина патентного тролля.
Правда, такая история ожидает совсем не в каждой стране. В большинстве стран законы ограждают общество от патентования идей. Осознав, что программное обеспечение не подчиняется законам физики, а значит — запатентовать можно практически все, большинство стран существенно ограничило возможность патентования чего-либо в области ПО. Существует, однако, одно маленькое, но важное исключение — Соединенные Штаты Америки. Про эту страну мы и будем в основном говорить.
Невозможно в одной статье описать все аспекты ситуации с патентами в США. К тому же, я не американский патентный юрист, и не знаю всех тонкостей, а если бы и знал, вряд о них имело бы смысл здесь писать. Поэтому постараемся сконцентрироваться на самом важном, а если всплывут вопросы, поговорим о них в комментах.
Если тема заинтересовала, приглашаю разбираться с ней под катом.