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

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

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

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

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

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

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

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

Добрый день.

Как многие наверное знают, Павел Дуров разрабатывает новый клон What's App и прочих популярных мессенджеров на базе своего собственного протокола MTProto.

Недавно американская компашка выпустила iOS клиент под этот протокол под названием Telegram. Параллельно с этим проводится — конкурс на разработку Android клиента.
Недавно завершился второй этап, народ отправил свои поделки и я в том числе. Скажу сразу, второй этап я не прошел.

В отличие от многих участников, для разработки я пользовался языком C# и Xamarin о чем и хочу рассказать подробнее ниже, так как по Xamarin в рунете информации скажем прямо немного.

Введение

Совсем недавно компания Xamarin анонсировала выход новой версии своего инструментария для кроссплатформенной разработки мобильных приложений, но вменяемых статей на русском по этой тематике так и нет. На Хабре появился небольшой обзор, не связанный с кодингом, там же была пара попыток рассказать об этом чуть подробнее, но дальше процесса создания Hello World приложения дело не зашло. А жаль. В этот раз мы попробуем исправить это досадное недоразумение.

Википедия — свободная общедоступная мультиязычная универсальная интернет-энциклопедия, которая создаётся усилиями многих пользователей. На сегодня Википедия содержит 25 миллионов записей на 285 языках, почти полмиллиарда людей обращаются к ней каждый месяц. По полноте и глубине охвата материала Википедия сравнима со знаменитой Британской энциклопедией. Тысячи добровольных редакторов со всего мира постоянно пополняют её свежими статьями. Благодаря их бескорыстному труду создаётся и развивается это гигантское хранилище знаний.

Википедия стала самым популярным в мире источником общеобразовательных, исторических и научных знаний и входит в топ-10 самых посещаемых сайтов в Интернете. Она привлекает к себе не только тех, кто ищет знания, или хочет ими бескорыстно поделиться, но и маркетологов и PR-менеджеров, пытающихся использовать сайт в качестве рекламной площадки, размещать там заказные проплаченные статьи. Была создана компания Wiki-PR, специализирующаяся на написании и размещении в Википедии статей и правок рекламного характера. Цена размещения одной такой статьи варьировала от 500 до 1000 долларов. Отдельно выплачивался ежемесячный взнос порядка 50-70 долларов за то, чтобы статья или правка не была удалена, или же наоборот, чтобы был удалён и больше не появлялся на страницах Википедии нежелательный для заказчика материал. Этот момент заслуживает особого внимания.

Мы продолжаем делиться с обитателями Хабра кратким изложением выступлений гостей финала Russian Code Cup 2013. Сегодня мы представляем вашему вниманию конспект рассказа Дмитрия Склярова о реверс-инжиниринге.

Дмитрий Скляров — доцент кафедры информационной безопасности МГТУ им. Баумана и аналитик компании Positive Technologies. Работает в области информационной безопасности более 13 лет. Разработчик алгоритма программы Advanced eBook Processor.

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

Асинхронность… Услышав это слово, у программистов начинают блестеть глаза, дыхание становится поверхностным, руки начинают трястись, голос — заикаться, мозг начинает рисовать многочисленные уровни абстракции… У менеджеров округляются глаза, звуки становятся нечленораздельными, руки сжимаются в кулаки, а голос переходит на обертона… Единственное, что их объединяет — это учащенный пульс. Только причины этого различны: программисты рвутся в бой, а менеджеры пытаются заглянуть в хрустальный шар и осознать риски, начинают судорожно придумывать причины увеличения сроков в разы… И уже потом, когда большая часть кода написана, программисты начинают осознавать и познавать всю горечь асинхронности, проводя бесконечные ночи в дебаггере, отчаянно пытаясь понять, что же все-таки происходит…

Именно такую картину рисует мое воспаленное воображение при слове “асинхронность”. Конечно, все это слишком эмоционально и не всегда правда. Ведь так?.. Возможны варианты. Некоторые скажут, что “при правильном подходе все будет работать хорошо”. Однако это можно сказать всегда и везде при всяком удобном и не удобном случае. Но лучше от этого не становится, баги не исправляются, а бессонница не проходит.

Так что же такое асинхронность? Почему она так привлекательна? А главное: что с ней не так?

Вы хорошо поработали, и вот ваше приложение в App Store!

• Храните учётные записи юзеров?
• Используете встроенные покупки?
• Не хотите показывать своё ноу-хау?

Повод задуматься о безопасности кода и данных! Мы будем искать уязвимости в тестовом приложении. В этой статье поговорим о безопасности данных, а в следующей — перейдём к коду.

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

В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.

Мы довольно часто слышим новости о том, что происходит на зарубежных биржах. Лондонская биржа и NASDAQ, кажется, знакомы даже далеким от биржевой торговли пользователям Сети. Зачастую в этих новостях рассказывается об успехах зарубежных финансистов, в частности, в области технологий – рекордах скорости транзакций, производительности, или, наоборот, сбоях оборудования или программного обеспечения. В результате создается впечатление, что зарубежные площадки самые технологичные в мире.

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

Попытайтесь повторить это сами

Как правило, настроенный должным образом сервер Nginx на Linux, может обрабатывать 500,000 — 600,000 запросов в секунду. Но этот показатель можно весьма ощутимо увеличить. Хотел бы обратить внимание на тот факт, что настройки описанные ниже, применялись в тестовой среде и, возможно, для ваших боевых серверов они не подойдут.

Минутка банальности.

yum -y install nginx

На всякий пожарный, создадим бэкап исходного конфига.

cp /etc/nginx/nginx.conf /etc/nginx/nginx.conf.orig
vim /etc/nginx/nginx.conf

А теперь можно и похимичить!

В данном топике, будет рассказано о пошаговой настройке и конфигурации проекта и сервера с использованием связки pinba-engine + pinboard + django-pinba, для сбора и визулизации статистики проектов на Django.

Все проекты являются бесплатными и их исходный код доступен на GitHub под лицензиями GPL или MIT.

Почему pinba?

В команде есть проекты, которые были написаны на php. Посещаемость у проектов достаточно высокая(свыше 200к). Есть очень много узких мест. Часто после каких-либо обновлений и новшеств, мы получали огромные тормоза, о которых узнавали не сразу. Нужно было решение, которое повернуто лицом к заказчику и программисту. Закачик очень не любит zabbix и munin. Решение нашлось. Это был pinboard и pinba. Заказчику понравилось. Он попросил прикрутить pinba ко всем проектам, которые крутились на django.

Инфраструктура .Net содержит встроенные средства генерирования кода (On-the-Fly Code Generation). Это позволяет .Net-программе в момент своего исполнения самостоятельно (без участия программиста) скомпилировать текст, написанный на каком-либо языке программирования и исполнить получившийся код. Логично было бы ожидать, что для осуществления этих действий в стандартной .Net-библиотеке предусмотрен простейший метод соответствующего класса. Но к сожалению это не так. Microsoft, проделав огромный путь по встраиванию в среду .Net средств генерирования кода, не сделала самый последний шаг навстречу простейшим потребностям программистов. Значит, придётся сделать этот шаг самостоятельно.

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

От переводчика. Судя по своему опыту, а также по опыту знакомых коллег-программистов, могу сказать, что для начинающего разработчика среди всех базовых функций языка C# и платформы .NET делегаты и события являются одними из наиболее сложных. Возможно, это из-за того, что необходимость делегатов и событий на первый взгляд кажется неочевидной, или же из-за некоторой путаницы в терминах. Поэтому я решил перевести статью Джона Скита, рассказывающую о делегатах и событиях на самом базовом уровне, «на пальцах». Она идеальна для тех, кто знаком с C#/.NET, однако испытывает затруднение в понимании делегатов и событий.

Представленный здесь перевод является вольным. Однако если под «вольным», как правило, понимают сокращённый перевод, с упущениями, упрощениями и пересказами, то здесь всё наоборот. Данный перевод является немного расширенной, уточнённой и обновлённой версией оригинала. Я выражаю огромную благодарность Сергею Теплякову aka SergeyT, который внёс неоценимый вклад в перевод и оформление данной статьи.

Люди часто испытывают затруднения в понимании различий между событиями и делегатами. И C# ещё больше запутывает ситуацию, так как позволяет объявлять field-like события, которые автоматически преобразуются в переменную делегата с таким же самым именем. Эта статья призвана прояснить данный вопрос. Ещё одним моментом является путаница с термином «делегат», который имеет несколько значений. Иногда его используют для обозначения типа делегата (delegate type), а иногда — для обозначения экземпляра делегата (delegate instance). Чтобы избежать путаницы, я буду явно использовать эти термины — тип делегата и экземпляр делегата, а когда буду использовать слово «делегат» — значит, я говорю о них в самом широком смысле.

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



Есть мнение, что специализированная read-only файловая система при прочих равных обладает преимуществами перед оной общего назначения т.к:

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

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

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

Что же всё-таки можно нарисовать с помощью всего двух треугольников? Квадрат? Фрактал? Полёт сквозь мегатонной мощности взрыв в центре города? Есть ли предел безумию, где заканчивается реальность и начинается явь? Как правильно ухаживать за лучами, чем их кормить и обо что отражать вы узнаете во внезапном продолжении цикла статей про демомейкинг!

«на русской сцене мы удивляем друг друга тем, что вообще что-то делаем», © manwe
(из статуса SCRIMERS на demoscene.ru/forum)

Пятиминутка мета: в этом тексте вам, котятки, предстоит прочитать о том, как потратить свое время совершенно неэффективно с точки зрения отношения размера полученного продукта к потраченным времени и усилиям.
Предположим, что мы хотим сделать что-нибудь эдакое, например, интру размером до 4кб, но мы нищеброды, и у нас нет денег на виндовс и видеокарту с шейдерами, поддерживающими ветвления. Или мы просто не хотим брать стандартный набор из apack/crinkler/sonant/4klang/боже-что-там-еще-есть, делать очередную «смотрите все! я тоже умею рэймарчинг дистанс филдс!» и теряться среди десятков-сотен таких же. Ну или же мы просто любим выпендриваться как попало в надежде, что девочки на нас наконец-то обратят внимание.

В общем, не важно. Пусть у нас просто есть какой-нибудь линукс со слабой видеокартой и вся юность впереди. Попробуем со всем этим теперь создать запускаемый файл размером не более, скажем, 1024 байт, который при запуске умудрялся бы каким-нибудь образом создавать и показывать пользователю что-нибудь (эдакое).

Спасибо каждому, кто читал и комментировал первую часть. Благодаря вам, продолжение будет еще интереснее. Если еще не читали — рекомендую это сделать. Там мало текста, и есть классные видео.

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

• Тренировки. Вырабатывание летных навыков.
• Выбор модели: самолет, вертолет или мультикоптер?
• Выбор конкретной конструкции и размера
• Моторы и ESC
• Полетный контроллер

Как обычно, сразу к делу.

Введение

CFD (Computational fluid dynamics) — вычислительная гидродинамика.
Используется для моделирования разных процессов в жидкостях, а также разных типов жидкостей (например мёд, нефть — это все жидкости).

В данном посте рассматривается 2D симулятор обычной воды с открытой поверхностью и препятствиями (для 3D версии все аналогично + доступны исходники).
Поверхность воды представляет собой границу, отделяющую воду от воздуха.Это позволяет моделировать волны, падение капель и т.д.

Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.