Здравствуйте читатели.
Сегодня хотел поговорить на тему различия в написании программ на олимпиадах и на проектах, или как я их называю: "Олимпиадный" и "Корпоративный" стили. У каждого из них есть как свои плюсы так и минусы. Я не говорю, что я владею ими достаточно глубоко, но различия постараюсь продемонстрировать ниже, а заодно и рассказать о том, как понять некоторые паттерны проектирования на простых задачах. Очень редко появляется возможность найти неплохой пример для демонстрации того или иного подхода.
Немного конкретики.
Задача: Magicka.
Для тех кому лень переводить: есть последовательность символов (элементов), и есть несколько преобразований при добавлении очередного символа. Существует два преобразования: 1) если новый и предыдущий символ описаны как преобразуемые, то они удаляются и вместо них ставиться определенный; 2) если новый символ не сопоставим с любым из последовательности - вся последовательность, включая новый символ, уничтожается. Нужно найти конечное состояние последовательности если известны наборы преобразований, уничтожений и последовательность добавления символов.
Решение: симуляция.
А теперь почему я выбрал именно эту задачу. Если мы посмотрим на любое бизнес приложение, то это почти полная симуляция (автоматизация) какого-либо набора действий. Чем наша задача не набор действий?
Вариант решения Олимпиадный:
Что же тут хорошего: Во первых не много текста, все рядом, да и вообще если смотреть на это чудо минут 10-15 то, примерно, понимаешь как оно работает.
Что тут плохого: Данный стиль, лично мне, напоминает язык perl: write only, написал, а через пару дней уже не понимаешь как ты к этому пришел и как сюда внести изменения.
Из вышеизложенных пунктов можно понять, почему некоторые компании с недоверием смотрят в сторону олимпиадников.
Ну что же. Посмотрим как этот код можно привести к корпоративному стилю. Ну или хотя бы попробуем это сделать.
Сущности.
В задаче присутствуют такие понятия как:
Что можно сказать глядя на этот набор пунктов: для начала у нас видна нейкая подобия стратегии (волшебная очередь), а если немного присмотреться, то можно увидеть и билдер. Многим он сложно дается, но надеюсь на этом примере многие поймут зачем он нужен, и к чему он приведет. Тут так же можно углубляться до бесконечности и фанатично, но постараюсь остановиться на этих двух подходах. Еще немного применим модное ныне веение "Депенденси инджекшен" :)
И так, давайте начнем с простого: у нас есть колдун и он умеет читать заклинания по бумажке, с этого и начнем. Какие у него есть подручные средства: пространство, куда он умеет колдовать, назовем это магической очередью. Опишем данного умельцы ввиде интерфейса и реализуем его, благо его задача только махать волшебной палочкой:
Ничего сложного. Имеем интерфейс магической очереди, интерфейс колдуна. Через конструктор передаем колдуну, с чем ему работать. А в методе InvokeElements передаем последовательность элементов которые этот колдун и вызывает.
Продолжим.
Немного остановлюсь на паттерне билдер, ну или то, как я его вижу:
У вас есть объект, который что-то вызывает в другом объекте из которого вы потом забираете результат.
Например: нужно сформировать отчет в нескольких вариантах: XML, TXT, HTML. Отчет содержит заголовок, данные и нижнюю часть документа (график). Так вот, билдер будет выглядеть следующим образом:
Попробуем перенести данный паттерн на нашу задачу. Для этого нам нужно описать, что такое простая очередь. Опишем всех необходимых действий с ней через интерфейс:
Наша простая очередь должна выполнять примитивные действия с элементами: Добавлять элемент в конец, Удалять последний, Очищаться, возвращать количество элементов, Возвращать текущее состояние, Возвращать последний элемент, Возвращать два последних элемента и возвращать все уникальные элементы которые в ней есть. На основании этого мы можем решить нашу задачу вынеся реализацию по объеденению и уничтожению элементов на уровень Магической очереди.
Реализуем простую очередь:
Таким образом, у нас получилась следующая зависимость: Маг зависит от магической очереди, которая зависит от простой очереди.
Приблизительный алгоритм работы следующий:
Так же нужно выделить дополнительную сущность, как конфигурация магической очереди:
Продолжаем. На данном этапе реализуем базовый процесс добавления элемента в магическую очередь используя "Шаблонный метод":
Далее реализуем сам механизм комбинирования и уничтожения очереди:
Ну и наконец, осталось самое простое: пример использования данного чуда.
Создаем обычную очередь, создаем конфигурацию, создаем магическую очередь на основе конфигурации и простой очереди, создаем мага на основе магической очереди, настраиваем конфигурацию, даем магу указания, забираем результат из простой очереди.
И напоследок общая картина как оно работает в виде сиквенс диаграммы (кликабельно):
Исходный код можно взять здесь. Жду ваших комментариев. И надеюсь хоть кто-то смог уловить то, что я хотел передать этим многочасовым трудом.
PS: Назвать стэк очередью была плохой идеей, но надеюсь вы не в обиде. :)
Спасибо за внимание.
Сегодня хотел поговорить на тему различия в написании программ на олимпиадах и на проектах, или как я их называю: "Олимпиадный" и "Корпоративный" стили. У каждого из них есть как свои плюсы так и минусы. Я не говорю, что я владею ими достаточно глубоко, но различия постараюсь продемонстрировать ниже, а заодно и рассказать о том, как понять некоторые паттерны проектирования на простых задачах. Очень редко появляется возможность найти неплохой пример для демонстрации того или иного подхода.
Немного конкретики.
Задача: Magicka.
Для тех кому лень переводить: есть последовательность символов (элементов), и есть несколько преобразований при добавлении очередного символа. Существует два преобразования: 1) если новый и предыдущий символ описаны как преобразуемые, то они удаляются и вместо них ставиться определенный; 2) если новый символ не сопоставим с любым из последовательности - вся последовательность, включая новый символ, уничтожается. Нужно найти конечное состояние последовательности если известны наборы преобразований, уничтожений и последовательность добавления символов.
Решение: симуляция.
А теперь почему я выбрал именно эту задачу. Если мы посмотрим на любое бизнес приложение, то это почти полная симуляция (автоматизация) какого-либо набора действий. Чем наша задача не набор действий?
Вариант решения Олимпиадный:
private void Solve() { string res = string.Empty; var e = new Dictionary(); int i = 0; char last = '#'; while (i<_query.Length) { char next = _query[i]; if (last != '#') { if (_combine.ContainsKey(next) && _combine[next].ContainsKey(last)) { next = _combine[next][last]; res = res.Remove(res.Length - 1); e[last]--; if (e[last] == 0) e.Remove(last); } bool doClear = false; var t = e.Keys.ToArray(); for (int j = 0; j < t.Length; j++) { if (_opposed.ContainsKey(next) && _opposed[next].Contains(t[j])) { doClear = true; break; } } if (doClear) { res = string.Empty; e.Clear(); next = '#'; last = next; i++; continue; } } res += next; if (!e.ContainsKey(next)) e[next] = 1; else e[next]++; last = next; i++; } _result[_num] = res; }
Что же тут хорошего: Во первых не много текста, все рядом, да и вообще если смотреть на это чудо минут 10-15 то, примерно, понимаешь как оно работает.
Что тут плохого: Данный стиль, лично мне, напоминает язык perl: write only, написал, а через пару дней уже не понимаешь как ты к этому пришел и как сюда внести изменения.
Из вышеизложенных пунктов можно понять, почему некоторые компании с недоверием смотрят в сторону олимпиадников.
Ну что же. Посмотрим как этот код можно привести к корпоративному стилю. Ну или хотя бы попробуем это сделать.
Сущности.
В задаче присутствуют такие понятия как:
- Стэк/очередь/список/массив символов:
- Добавляем новый символ
- Достаем последний символ
- Достаем два последних символа
- Множество уникальных символов
- Количество каждого символа в стеке
- Очистка результата
- Волшебная очередь:
- Добавляем новый символ
- Проверки
- Трансформация двух последних в один новый
- Несовместимые символы и очистка результата
- Конфигурация очереди
- Добавление комбинаций и условия уничтожения
- Проверка комбинаций
- Проверка условия уничтожения
- Колдун
- Получает строку и посимвольно вызывает элементы.
Что можно сказать глядя на этот набор пунктов: для начала у нас видна нейкая подобия стратегии (волшебная очередь), а если немного присмотреться, то можно увидеть и билдер. Многим он сложно дается, но надеюсь на этом примере многие поймут зачем он нужен, и к чему он приведет. Тут так же можно углубляться до бесконечности и фанатично, но постараюсь остановиться на этих двух подходах. Еще немного применим модное ныне веение "Депенденси инджекшен" :)
И так, давайте начнем с простого: у нас есть колдун и он умеет читать заклинания по бумажке, с этого и начнем. Какие у него есть подручные средства: пространство, куда он умеет колдовать, назовем это магической очередью. Опишем данного умельцы ввиде интерфейса и реализуем его, благо его задача только махать волшебной палочкой:
internal interface IMagicQueue { void AddElement(char c); } internal interface IMagicMan { void InvokeElements(string items); } internal class MagicMan : IMagicMan { private readonly IMagicQueue _q; public MagicMan(IMagicQueue q) { _q = q; } public void InvokeElements(string items) { foreach (var c in items) { _q.AddElement(c); } } }
Ничего сложного. Имеем интерфейс магической очереди, интерфейс колдуна. Через конструктор передаем колдуну, с чем ему работать. А в методе InvokeElements передаем последовательность элементов которые этот колдун и вызывает.
Продолжим.
Немного остановлюсь на паттерне билдер, ну или то, как я его вижу:
У вас есть объект, который что-то вызывает в другом объекте из которого вы потом забираете результат.
Например: нужно сформировать отчет в нескольких вариантах: XML, TXT, HTML. Отчет содержит заголовок, данные и нижнюю часть документа (график). Так вот, билдер будет выглядеть следующим образом:
using System; using System.Collections.Generic; using System.Text; /// <summary> /// Данные для отчета /// </summary> internal interface IReportData { /// <summary> /// Отчетный период /// </summary> int Year { get; } /// <summary> /// Доход компании /// </summary> decimal Profit { get; } } /// <summary> /// Интерфейс построителя /// </summary> interface IReportBuilder { void BuildHeader(string companyName); void BuildData(List<IReportData> data); void BuildChart(List<IReportData> chartData); string GetResult(); } /// <summary> /// Реализация построителя текстового отчета /// </summary> internal class TextReportBuilder : IReportBuilder { private readonly StringBuilder _result = new StringBuilder(); public void BuildHeader(string companyName) { _result.AppendFormat("Report for {0}\n", companyName); } public void BuildData(List<IReportData> data) { foreach (var reportData in data) { _result.AppendFormat("Year {0}, profit: ${1}\n", reportData.Year, reportData.Profit); } } public void BuildChart(List<IReportData> chartData) { _result.AppendFormat("Generated time:" + DateTime.Now); } public string GetResult() { return _result.ToString(); } } /// <summary> /// Директор /// </summary> class Director { private readonly IReportBuilder _builder; /// <summary> /// Создание директора на основе построителя /// </summary> /// <param name="builder">Построитель</param> public Director(IReportBuilder builder) { _builder = builder; } /// <summary> /// Постройка отчета /// </summary> /// <param name="companyName">Имя компании</param> /// <param name="data">Данные для отчета</param> public void BuildGlobalReport(string companyName, List<IReportData> data) { // Строим отчет не зависимо от конкретной реализации построителя отчетов. _builder.BuildHeader(companyName); _builder.BuildData(data); _builder.BuildChart(data); } } class Source { public void ReportButtonClick() { // Пользователь кликнул по кнопке генерации отчета. // Создаем построитель IReportBuilder builder = new TextReportBuilder(); // Директора Director director = new Director(builder); // Строим отчет director.BuildGlobalReport("KudInc", GetFullReport()); // Получаем отчет. string result = builder.GetResult(); } private List<IReportData> GetFullReport() { var result = new List<IReportData>(); return result; } }
Попробуем перенести данный паттерн на нашу задачу. Для этого нам нужно описать, что такое простая очередь. Опишем всех необходимых действий с ней через интерфейс:
internal interface ISimpleQueue { void AddElement(char element); void RemoveElement(); void Clear(); int Length { get; } string Result { get; } char LastItem { get; } char[] TwoLatestItems { get; } IEnumerable<char> UniqueItems { get; } }
Наша простая очередь должна выполнять примитивные действия с элементами: Добавлять элемент в конец, Удалять последний, Очищаться, возвращать количество элементов, Возвращать текущее состояние, Возвращать последний элемент, Возвращать два последних элемента и возвращать все уникальные элементы которые в ней есть. На основании этого мы можем решить нашу задачу вынеся реализацию по объеденению и уничтожению элементов на уровень Магической очереди.
Реализуем простую очередь:
internal class SimpleQueue : ISimpleQueue { /// <summary> /// Count of each elements. /// </summary> private readonly int[] _available; /// <summary> /// Set of unique elements. /// </summary> private readonly HashSet<char> _history; /// <summary> /// Current queue state. /// </summary> private readonly StringBuilder _queue; /// <summary> /// Create new instance of SimpleQueue with default values. /// </summary> public SimpleQueue() { _available = new int[255]; _history = new HashSet<char>(); _queue = new StringBuilder(); } /// <summary> /// Current queue state. /// </summary> public string Result { get { return _queue.ToString(); } } /// <summary> /// Current queue length. /// </summary> public int Length { get { return _queue.Length; } } /// <summary> /// Remove last element from the queue. /// </summary> public void RemoveElement() { var l = _queue.Length; var c = _queue[l - 1]; _queue.Remove(l - 1, 1); _available[c]--; if (_available[c] == 0) _history.Remove(c); } /// <summary> /// Add new element to the end of the queue. /// </summary> /// <param name="element">Element that should be added.</param> public void AddElement(char element) { // append element to end of queue _queue.Append(element); // increase count of elements _available[element]++; // add element to unique set of elements if (_available[element] == 1) _history.Add(element); } /// <summary> /// Clear current queue state. /// </summary> public void Clear() { // clear queue. _queue.Clear(); // clear element counters. Array.Clear(_available, 0, _available.Length); // clear unique elements set. _history.Clear(); } /// <summary> /// Last queue element. /// </summary> public char LastItem { get { return _queue[_queue.Length - 1]; } } /// <summary> /// Two latest items in the queue. /// </summary> public char[] TwoLatestItems { get { return new[] { _queue[_queue.Length - 2], _queue[_queue.Length - 1] }; } } /// <summary> /// Unique elements that present in the queue. /// </summary> public IEnumerable<char> UniqueItems { get { return _history; } } }
Таким образом, у нас получилась следующая зависимость: Маг зависит от магической очереди, которая зависит от простой очереди.
Приблизительный алгоритм работы следующий:
- Маг колдует новый элемент и отправляет магической очереди на обработку
- Магическая очередь добавляет данный элемент в конец просто очереди
- Магическая очередь осуществляет проверку с использованием конфигурации на наличие преобразования и уничтожения.
Так же нужно выделить дополнительную сущность, как конфигурация магической очереди:
internal interface IMagicQueueConfiguration { /// <summary> /// Checking for opposing. /// </summary> /// <param name="a">First element.</param> /// <param name="b">Second element.</param> /// <returns>True when these elements is opposed, or false when not.</returns> bool IsOpposed(char a, char b); /// <summary> /// Get combination rule. Zero when no combination is available. /// </summary> /// <param name="a">First element.</param> /// <param name="b">Second element.</param> /// <returns>Result of a combination of these elements.</returns> char GetCombine(char a, char b); } internal class MagicQueueConfiguration : IMagicQueueConfiguration { /// <summary> /// Combination matrix. /// </summary> protected readonly char[,] Combine = new char[255, 255]; /// <summary> /// Opposed matrix. /// </summary> protected readonly bool[,] Opposed = new bool[255, 255]; /// <summary> /// Create new combination rule. /// </summary> /// <param name="a">First element.</param> /// <param name="b">Second element.</param> /// <param name="result">Combination result.</param> public void AddCombine(char a, char b, char result) { Combine[a, b] = result; Combine[b, a] = result; } /// <summary> /// Create new opposing rule. /// </summary> /// <param name="a">First element.</param> /// <param name="b">Second element.</param> public void AddOpposed(char a, char b) { Opposed[a, b] = true; Opposed[b, a] = true; } /// <summary> /// Checking for opposing. /// </summary> /// <param name="a">First element.</param> /// <param name="b">Second element.</param> /// <returns>True when these elements is opposed, or false when not.</returns> public bool IsOpposed(char a, char b) { return Opposed[a, b]; } /// <summary> /// Get combination rule. Zero when no combination is available. /// </summary> /// <param name="a">First element.</param> /// <param name="b">Second element.</param> /// <returns>Result of a combination of these elements.</returns> public char GetCombine(char a, char b) { return Combine[a, b]; } }
Продолжаем. На данном этапе реализуем базовый процесс добавления элемента в магическую очередь используя "Шаблонный метод":
/// <summary> /// Base magic queue. /// </summary> internal abstract class BaseMagicQueue : IMagicQueue { /// <summary> /// Result storage. /// </summary> protected ISimpleQueue Sq; /// <summary> /// Configuration provider. /// </summary> protected IMagicQueueConfiguration Qc; /// <summary> /// Create new instance nased on result storage and configuration provider. /// </summary> /// <param name="sq">Storage result.</param> /// <param name="qc">Configuration provider.</param> protected BaseMagicQueue(ISimpleQueue sq, IMagicQueueConfiguration qc) { Qc = qc; Sq = sq; } #region Abstract methods public abstract void Oppose(); public abstract void Combine(); #endregion /// <summary> /// Create new element and process comination and opposing. /// </summary> /// <param name="c">New element value</param> public void AddElement(char c) { Sq.AddElement(c); Combine(); Oppose(); } }
Далее реализуем сам механизм комбинирования и уничтожения очереди:
/// <summary> /// Magic queue with Oppose and Combine implementation. /// </summary> internal class MagicQueue : BaseMagicQueue { /// <summary> /// Create new instance nased on result storage and configuration provider. /// </summary> /// <param name="sq">Storage result.</param> /// <param name="qc">Configuration provider.</param> public MagicQueue(ISimpleQueue sq, IMagicQueueConfiguration qc) : base(sq, qc) { } /// <summary> /// Oppose queue. /// </summary> public override void Oppose() { if (Sq.Length < 2) return; var c = Sq.LastItem; foreach (char item in Sq.UniqueItems) { if (Qc.IsOpposed(item, c)) { Sq.Clear(); return; } } } /// <summary> /// Combine queue. /// </summary> public override void Combine() { if (Sq.Length < 2) return; char[] items = Sq.TwoLatestItems; var t = Qc.GetCombine(items[0], items[1]); if (t != 0) { Sq.RemoveElement(); Sq.RemoveElement(); Sq.AddElement(t); } } }
Ну и наконец, осталось самое простое: пример использования данного чуда.
Создаем обычную очередь, создаем конфигурацию, создаем магическую очередь на основе конфигурации и простой очереди, создаем мага на основе магической очереди, настраиваем конфигурацию, даем магу указания, забираем результат из простой очереди.
class Program { public static void Main(string[] args) { // Create simple queue. var simpleQueue = new SimpleQueue(); // Create queue configurator. var queueConfiguration = new MagicQueueConfiguration(); // Create magic queue mased on configurator and simple queue. var queue = new MagicQueue(simpleQueue, queueConfiguration); // Create new magic man. var magicMan = new MagicMan(queue); // Configure queue. // Q+F traslated into T queueConfiguration.AddCombine('Q', 'F', 'T'); // Q&F will clear the queue. queueConfiguration.AddOpposed('Q', 'F'); // Do magic. magicMan.InvokeElements("FAQFDFQ"); // Take result. var res = simpleQueue.Result; Console.WriteLine(res); } }
И напоследок общая картина как оно работает в виде сиквенс диаграммы (кликабельно):
Исходный код можно взять здесь. Жду ваших комментариев. И надеюсь хоть кто-то смог уловить то, что я хотел передать этим многочасовым трудом.
PS: Назвать стэк очередью была плохой идеей, но надеюсь вы не в обиде. :)
Спасибо за внимание.
Тестовый комментарий.
ОтветитьУдалитьДружище, ты в олимпик солюшене ОДНИМ ридером читаешь файл параллельно в разных потоках без синхронизации вообще? Экстремал ты :) Или операция StreamReader.ReadLine синхронизирована унутре?
ОтветитьУдалитьДля начала я не читаю много поточно.
ОтветитьУдалитьЧтение происходит в конструкторе, после чего создается отдельный поток и в нем происходит решение задачи, а результат пишется в строго отведенный элемент массива.
for (int i=0;i<n;i++)
{
var t = new TaskB(r, i); -- читаю данные
запускю задачу:
var task = Task.Factory.StartNew(t.Solve);
bg[i] = task;
}