Александр Полозов Skiminok

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

Итак, мое написание диплома началось с того, что я потратил 4 часа на настройку преамбулы под нормы украинского стандарта оформления ДСТУ 3008-95. Насколько мне известно, он почти полностью соответствует русскому ГОСТу. Я знал, что существуют готовые решения (например, disser), но после пары проб предпочел настроить каждую деталь самостоятельно. Для тренировки. Тренировка удалась — я узнал бездну новых вещей о LaTeX, этого монстра невозможно выучить полностью :-)

Под катом я полностью опишу процесс настройки каждой конкретной детали и использование их при написании, а также разные мелочи, упрощающие написание диплома еще больше. Сразу предупреждаю: где-то мои решения могут показаться костылями. Где-то они не слишком универсальны. Я это знаю, понимаю, принимаю и приветствую критику и предложения в комментариях ;-)

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

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

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция

Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John" ◦ "Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.

И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
a ⊗ e = e ⊗ a = a
В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если a ≠ e, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:

public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.

Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.

Условие

Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.

Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя.
Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).
Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое.

На рисунке я продемонстрирую работу такой гипотетической структуры.

 

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

Часть 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). Думаю, также многим известная структура данных, однако краткий обзор я все же приведу.
Представьте себе двоичное дерево с какими-то данными (ключами) в вершинах. И для каждой вершины мы в обязательном порядке требуем следующее: ее ключ строго больше, чем ключи ее непосредственных сыновей. Вот небольшой пример корректной кучи:

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

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

Постановка вопроса: как найти декартово произведение произвольного количества последовательностей с помощью LINQ?

Для начала, давайте убедимся, что мы знаем, о чем идет речь. Я буду обозначать последовательности как упорядоченные множества: {a, b, c, d...} Декартово произведение двух последовательностей S1 и S2 есть последовательность всех возможных упорядоченных пар таких, что их первый элемент из S1, а второй — из S2. Так, к примеру, если у вас есть две последовательности {a, b} и {x, y, z}, то их декартово произведение выглядит как {{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}}.

Для упрощения, предположим, что S1 и S2 состоят из элементов одного типа. Разумеется, мы можем определить декартово произведение последовательности строк с последовательностью чисел как последовательность кортежей (string, int), но впоследствии это окажется тяжело обобщать, потому что система типов C#, в частности, не лучшим образом работает с кортежами произвольной длины.

На этой неделе мы немного обсудим нововведения в VCL, особо фокусируясь на возможностях естественного ввода (жесты и прикосновения) в RAD Studio 2010. Примите во внимание, что всё, о чём мы говорим, есть лишь бета-версия, и до релиза всё может измениться.

С помощью нового механизма вы можете выбирать разнообразные предопределённые движения вашего манипулятора (либо создавать новые, пользовательские) для того, чтобы ассоциировать их с разными действиями. Пользователям браузера Opera (и не только) это покажется знакомым. Для остальных, напомню, что Windows (а значит, и Delphi) давно содержит одно старое движение: Drag&Drop. Считайте, что этот механизм есть нечто подобное, но гораздо более мощное. Разумеется, это будет активно использоваться в программировании с использованием пера, приложениях для контент-киосков с использованием тачскрина и т.д.

Если вдаваться в детали, проясним одно положение: Delphi пытается использовать механизм обработки естественного ввода выпускающегося сейчас Windows 7. Если это невозможно (к примеру, приложение запущено на Windows XP), используется собственный механизм распознавания. Как он это делает? С помощью некоторого нововведения в языке (но это тема другого поста, конечно =)).

Вам случалось быть недовольными QIP? Ну да, нам тоже.

Цель данной статьи: раз и навсегда поставить все точки над «i» по вопросу QIP Infium, его сервисов и текущей ситуации, в которой находится проект. Она расскажет и объяснит вам всё положение спокойными словами, без негодующих воплей и обожающих визгов.
Эта статья:

• не защищает QIP и/или РБК;
• не является рекламным проектом РБК;
• описывает текущую ситуацию, сложившуюся вокруг проекта QIP;
• полезна тем, кто считает, что разработчики утаивают от них все порочащие нововведения;
• особенно полезна тем, кто думает, что привязка ко всем сервисам — обязательное условие работы QIP;
• написана адекватным языком — для адекватных комментаторов;
• написана совместными усилиями всей командой поддержки, тестирования и расширения QIP Infium. Нами же будут даваться в комментариях любые ответы на вопросы, которые возникнут по статье. Милости просим.

Приветствую, Хабр!

Эта статья продолжит тему автоматической кодогенерации в Visual Studio с помощью T4 — Text Template Transformation Toolkit. Часть №1, чуть ранее опубликованная в этом блоге, описывала синтаксис T4 и элементарные принципы его использования. В этот же раз я решил подробнее осмотреть блог уважаемого Олега Сыча и ещё немного адаптировать к хабрааудитории некоторые из его наработок. В частности, сегодня обсудим следующие темы:

• Создание повторно используемых и параметризируемых шаблонов
• Создание генераторов шаблонов
• Отладка, тестирование и расширение генераторов (ссылки)

Я не стал изобретать каких-то особенных примеров. История развития запроса с созданием хранимой процедуры, описанная Олегом, идеально подходит для иллюстрации проблемы, при которой могут потребоваться генераторы. Причем, что характерно, — не надуманной проблемы. Также статья придерживается принципа «меньше слов — больше кода».
Здесь и далее предполагается, что у вас установлена Visual Studio 2005/2008/2010, а также T4 Toolbox.

Приветствую, Хабр!

Сегодня мы поговорим о рутине. Время от времени каждому программисту приходится совершать много нудной, объемной и шаблонной работы, которую постоянно так и хочется автоматизировать, да руки не доходят. Вот об одном малоизвестном способе упростить себе жизнь с помощью кодогенерации я и хочу сегодня рассказать сообществу дотнетчиков. Способ известен как Text Template Transformation Toolkit или попросту T4.