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

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

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

Часть 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. Для многих старшеклассников, студентов, да и профессиональных программистов эти темы оказываются весьма сложными при обучении. Существует много литературы и курсов, посвящённых низкоуровневому программированию, но по ним сложно составить полную и всеохватывающую картину. Сложно, прочитав одну-две книги по ассемблеру и операционным системам, хотя бы в общих чертах представить, как же на самом деле работает эта сложная система из железа, кремния и множества программ — компьютер.

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

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

Например, если у вас в программе пользователь может переключаться между двумя экранами, вы заводите enum screen { screen_one, screen_two }; и переменную screen cur_screen_. Отрисовщик должен получить у модели «текущий выбранный экран», и затем отрисовать его, запрашивая у модели дополнительные данные, относящиеся именно к этому экрану. Что-то вроде:

switch (model.cur_screen())
{
case screen_one:
  model.get_screen_one_elements();
  ...
case screen_two:
  model.get_screen_two_elements();
  ...
}


При использовании такой модели, программист может запрашивать данные, которые для текущего состояния совершенно не актуальны. Например, вызвать метод get_screen_two_elements() для получения списка элементов второго экрана, когда текущий экран — первый. Хорошей практикой является использование ассертов вида ASSERT(cur_screen_ == screen_one) в методах, зависимых от конкретного экрана. Это обеспечивает некоторый контроль времени выполнения.

Но есть способ обеспечить контроль времени компиляции и более явное разделение состояний с помощью boost::variant.

Иногда требуется вставить формулу в блог или форум, причем сделать это красиво. В статье приведен обзор сервисов предоставляющих такую услугу.

Допустим есть у нас под Linux софтварный RAID1 собранный с помощью mdadm:

# cat /proc/mdstat
Personalities : [raid1]
md0 : active raid1 sdb[1] sda[0]
      8387572 blocks super 1.2 [2/2] [UU]

И появился у нас еще один винчестер который хотелось бы воткнуть в данную машину расширив доступное дисковое пространство не потеряв при этом в отказоустойчивости т.е. перейти с RAID1 на RAID5.

В последнее время на хабре чаще стали встречаться обсуждения масштабируемых систем и NoSQL решений. Эта статья, написанная техническим директором Amazon — одна из лучших вводных, на мой взгляд, показывающая, какие проблемы возникают при построении масштабируемых систем, что нужно учесть при выборе инструментария, что имеют ввиду авторы кассандры, говоря про обеспечение AP в кассандре и CP в HBase и многое другое.

10 слов об идее.

GTD планировщик в виде многопользовательской RPG для команд разработчиков, вот.

Коротко.

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

Lol, это шутка? Да, так и есть, это шутка. Но в каждой шутке, как говорится, есть доля шутки.

…Говоря о лени и ММО, сейчас я задумываюсь, если мне так влом утром вставать на работу, если мне так лень было ходить на пары, если мне нужно огромное количество усилий потратить, чтобы заставить себя наконец открыть Flex Builder и дописать этот глупый проект, почему я 4 месяца не получая за это зарплаты, вставал в 6 часов утра и весь день «работал» в игре? …

Дла заинтересовавшихся или тех, кому просто любопытно — велкам за хабракат. А вот пока картинка на затравку.

Итак, в новостях снова пишут, что кто-то еще умер из-за игромании. Да, опять Корея.

Какого ...? послушайте, я не пытаюсь доказать что видео игры — это героин. Я полностью понимаю, что в данном случае у жертвы было много проблем в жизни. Но, половина из вас знает что World of Warcraft затягивает и что доктора считают игровую зависимость серьёзной проблемой. А вопрос вот в чем: может быть какие-то игры намеренно разрабатывались, чтобы заставлять вас играть в них, даже если вы не получаете от этого удовольствия?

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

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

В данной статье я расскажу вам, как получить практически полноценный доступ для чтения и записи ко всем файловым системам, используемым в Linux (Ext2/3/4, ReiserFS, XFS, JFS, etc) из-под сабжевых операционных систем. Статья является вольным переводом данного руководства, причем написано оно уже довольно давно, но догуглился я до него только сейчас. :)

Хотим представить вашему вниманию русскоязычную версию руководства tornado server 0.2

Доброго времени суток, уважаемые Хабровчане!

Многие уже давно это знают, а многие — еще нет. Речь идет о том, как в браузере Opera, что называется — from-the-box, грамотно настроить блокировку рекламы, а также отключить «следящие» за пользователем скрипты google ad-sense и yandex direct.

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

После прочтения Dive into Python или подобной ей и ознакомления с документацией возникает вопрос, а что читать дальше? Можно обратиться к списку книг на python.org. Там есть раздел Advanced Books, но в нем всего лишь 6 книг (седьмая не выходила), и только одну я бы назвал по-настоящему стоящей.

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

Ниже собраны сложные материлы про Питон, его устройство и возможности. Все на английском (грех, не знать технический английский). Про Dive into Python я слукавил. Большинство приведенных материалов требуют хорошее знание Питона и наличие опыта программирования на нем.