Generation Next
За последний год произошла небольшая революция в мире СУБД, связанная с появлением безсхемных (безструктурных) СУБД таких как Apache CouchDB. В этих базах данных используется другой подход нежели в реляционных БД. Они достаточно быстро становятся популярны среди Web-разрабочиков из-за своей гибкости, простоты и легкой интеграции с современными технологиями такими как JSON.
В данной статье изложен краткий обзор MongoDB, одной из новых поколений безсхемных СУБД, которая получила большое внимание разработчиков.

Как разработчик, вы сидите на золотой жиле. Вы осознаете это?

Нет, серьезно, на @#$% золотой жиле! Никогда в истории не существовало возможностей так легко создать что-то с нуля, с маленьким или отсутствующим начальным капиталом и маркетинговой моделью, ограниченной только вашим воображением.

Подумайте о крупнейших сайтах, которые вы постоянно посещаете: Facebook, Twitter, Flickr, Foursquare, или даже Google — все они были созданы разработчиками, у которых была лишь идея. Было ли это легко? Черт, нет. Но это могло быть сделано только в наше время. Так, черт побери, почему вы просиживаете день за днем, работая на кого-то?

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

Проекты для дяди

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

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

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

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

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

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

Ищем индекс

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

Не так давно на Хабре уже писали о контесте 10К Apart — соревновании на лучшее веб-приложение общим объемом до 10К, созданное с использованием только клиентских технологий: (HTML, CSS, Javascript, SVG и т.д).



Я хочу представить вашему внимаю нашу работу для этого контеста, которую мы с private_face делали по вечерам в течение двух недель: адвенчуру в стиле dungeon-crawler под названием «Fontanero» (исп. водопроводчик).

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

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

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

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

Введение

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

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

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

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