воскресенье, 21 ноября 2010 г.

Doctrine 2 - Getting Started XML-Edition на русском

Наконец-то окончил перевод Getting Started XML-Edition на русский язык.. Это руководство, которое позволяет быстро ознакомиться с Doctrine 2 и ее возможностями и сразу после прочтения руководства начать использование.

Перевод вы можете скачать более удобном для вас виде:

      

А также в онлайн виде на Google Docs - это версия всегда будет самой свежей, а остальные я буду периодически обновлять.

Огромная просьба, если вы заметите ошибки в переводе или знаете как его можно улучшить сообщите мне об этом в комментариях здесь или на email - krasun.net@gmail.com. Также если вы узнаете об обновлении руководства раньше, чем я сообщите мне об этом.

Только вместе мы сможем сделать перевод руководства лучше.

пятница, 19 ноября 2010 г.

Модульное тестирование при использовании SWI-Prolog

В императивных языках программирования, таких, например, как C#, Java или C++ программисты часто используют модульное тестирования. Суть подхода заключается в том, что сначала пишется тест для некоторой функциональной единицы (модуля), а после чего уже пишется код самого модуля. Мы просто поменяли процесс, если раньше мы сначала писали код, потом тестировали, то сейчас мы сначала пишем тест, потом пишем код, а потом тестируем (уже автоматизированно). Конечно, полная автоматизация тестирования это миф, но все же большую часть кода можно покрыть тестами.

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

Такой подход к разработке, называется разработка через тестирование (Test Driven Development) и я считаю, он себя оправдывает при написания проектов, где будет вноситься много изменений в код или проект, просто должен быть создан за короткие сроки. Не думайте, что вы потеряете время на написание тестов, пройдете время и вы поймете, что на самом деле вы только выигрываете.

Теперь о SWI-Prolog, в ПроЛоге мы с вами используем предикаты для реализации логики. И значит, тестировать мы будем предикаты. Идея такая: мы создаем предикат test_p, который тестирует наш предикат p. Как будет проходить тест?

Все очень просто. Для тестирования, мы будем задавать заранее известные входные параметры (термы) и сверять результат исчисления предиката с заранее известным правильным ответом. Если ответы совпали, все в порядке идем дальше, если нет выдаем информативное сообщение.

Для наглядности покажу простой пример, используя SWI-Prolog, заранее оговорюсь, эти же идеи применимы для любой другой версии компилятора ПроЛога.

Напишем предикат max(X, Y, Max), вычисляющий максимальное значение из 2-ух элементов, для начала опишем тест, затем реализацию:

% сперва напишем тест
test_max1 :- 
    max(3, 2, X), 
    X = 3 , !.
test_max1 :- 
    write('max(3, 2, X) вычислен не правильно!'),  
    nl.

test_max2 :- 
    max(2, 3, X), 
    X = 3, !.
test_max2 :- 
    write('max(2, 3, X) вычислен не правильно!'), 
    nl.

test_max3 :- 
    max(2, 2, X), 
    X = 2, !.
test_max3 :- 
    write('max(2, 2, X) вычислен не правильно!'), 
    nl.

run_tests :- 
    test_max1, 
    test_max2, 
    test_max3.
    
% теперь опишем предикат, max 
max(A, B, B) :- 
    A < B, 
    !.
max(A, _, A).

Запустим программу и вот, что увидим:



Изменим, чуть код, не важному почему, допустим случайно, или так надо было:

% ...    

% теперь опишем предикат, max 
max(A, B, B) :- 
    A > B, 
    !.
max(A, _, A).

И вот, что мы увидим в результате.



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

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

понедельник, 15 ноября 2010 г.

Определяем уравнение прямой при помощи искусственных нейронных сетей

Я начал изучать иск. нейронные сети, первая книга с которой я познакомился была Калан. Р. - Основные концепции нейронных сетей. Прочтя эту книгу за 2 дня признаюсь честно, я так ничего и не понял. Решил начну еще раз сначала, после чего прочитал серию статей. И пришел к выводу, что без практики я мало, что пойму. Вот собственно, почему я и начал этот пост. Теперь ближе к теме.

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



Нам будет дан набор точек и на основе него, необходимо найти коэффициенты с и m - в уравнение прямой y = mx + c. Для обучения сети будем использовать дельта-правило - (правило Видроу-Хоффа). Если вкратце, то суть правила такова, мы на вход сети (в нашем случае перцептрон)  подадим значение координаты X, сеть вычислит значение координаты Y, мы сравним вычисленное сетью значение с ожидаемым и получим отклонение, то есть ошибку E. После чего мы полученную ошибку умножим на норму обучения n (она задается вручную) и на сигнал приходящий к Y, в результате мы и получаем отклонение весов dw1, dw2 и так далее. Остается только скорректировать весы w1 = w1 + dw1, w2 = w2 + dw2, ... 

Архитектура сети, также взято из Калан. Р., не удивляйтесь на то, что я привожу материалы из источников, моя задача запрограммировать сеть с использованием C#: 



До каких пор обучать сеть? Здесь, все просто до приемлемого уровня заданной точности, например, до 0.05 или просто провести обучение определенное количество раз, например, 10000. Теперь приведу, код программы, которая имитирует данный перцептрон:


// задаем начальное значение весов случайным образом 
// в интервале от [-0.3, 0.3] 
double[] w = new double[] 
{ 
    ((rD = r.Next(-100, 100) * 0.003) == 0) ? 
        0.3 : rD,
    ((rD = r.Next(-100, 100) * 0.003) == 0) ? 
        0.3 : rD
};

double[] w1 = new double[2]; 
w.CopyTo(w1, 0);

// входные сигналы
double[] x = new double[]
{
    1.0, 
    0.0
};

// норма обучения или скорость обучения 
double n = 0.1; 

double[,] pairs = new double[,] 
{
    {0.2, 1.3},
    {0.25, 1.3},
    {0.4, 1.4},
    {0.48, 1.52},
    {0.6, 1.6},
    {0.8, 1.6},
    {0.9, 2},
    {1, 2.1}
};
            
for (int i = 0; i < 10000; i++)
{
    for (int j = 0; j < pairs.GetLength(0); j++)
    {
        // для x на входе
        x[1] = pairs[j, 0];     
        // ожидаемый y на выходе
        double d = pairs[j, 1];
        // сумматор
        double y = x[0] * w[0] + x[1] * w[1];
        // вычисляем ошибку
        double e = d - y;
        // отклонение весов 
        double dW0 = e * n * x[0];
        double dW1 = e * n * x[1];
        // кооректируем весы 
        w[0] = w[0] + dW0;
        w[1] = w[1] + dW1;
    }
}

Console.WriteLine("w0 = {0}, w1 = {1}", 
    w1[0], w1[1]);
Console.WriteLine("m = {0}, c = {1}, |m - c| = {2}", 
    w[1], w[0], Math.Abs(w[1] - w[0]));
// m = 0.993801..., c = 1.03101...

В результате после выполнения выше приведенного кода, мы получим значения m и c, в следствии чего сможем построить уравнение прямой. 

Проект для Visual Studio 2010 Premium вы можете скачать отсюда. Спасибо, за внимание! Если у вас возникли вопросы, то задавайте. Либо если вы заметили ошибку, то сообщите мне об этом. Я мог здесь ошибиться, ибо я новичок в искусственных нейронных сетях. 

суббота, 9 октября 2010 г.

Простейший компилятор простейшего языка C в Assembler. Часть 2. Лексический блок

Прежде чем читать этот пост, сначала ознакомьтесь с "Простейший компилятор простейшего языка C в Assembler. Часть 1. Транслитератор".

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

Прежде, чем писать код лексического блока, необходимо определиться с лексемами, для этого приведем пример программы:

X = (0.5E1 + 2 + Y);
SCAN(Y);
IF (Y > (X + 2)) {
    PRINT(Y);
} 
Y1 = 10;
M0:
  IF (Y1 != 20 + 30) {
      GOTO M0;
  }    

Разобьем код на лексемы:

(опер. присваивания, 1)  // 1 - номер строки в 
                         // таблице идентификаторов
                         // пример: X = 
(число, 1)               // 1 - номер строки 
                         // в таблице констант 
                         // пример: 0.5
(SCAN, 1)                // 1 - номер строки в 
                         // таблице идентификаторов
                         // пример: SCAN(X)
(IF, IF)                 // пример: IF
((, ()                   // пример: (
(идентификатор, 1)       // 1 - номер строки в 
                         // таблице идентификаторов
                         // пример: x
(), ))                   // пример: )
(ар. операц, +)          // пример: + 
(оп. отношения, >=)      // пример: >=
({, {)                   // пример: {
(}, })                   // пример: }
(;, ;)                   // точка с запятой
(метка, 3)               // 3 - номер строки в 
                         // таблице идентификаторов
                         // пример M0: 
(GOTO, 3)                // 3 - номер строки в 
                         // таблице идентификаторов 
                         // GOTO M0
(PRINT, 2)               // 2 - номер строки в 
                         // таблице идентификаторов
                         // пример: PRINT(Y)

Здесь приведены, только уникальные лексемы для наглядности, так как дважды писать лексему "идентификатор" не нужно.

Теперь вы видите и понимаете, какая задача стоит перед лексическим блоком. Необходимо разбить код на лексемы да и еще в не которых местах проверить синтаксис.

С этой задачей нам позволят разобраться конечные автоматы: детерминированные и не детерминированные, также они решат проблему с производительностью, так как они могут обрабатывать огромные тексты за одни проход. Далее ознакомьтесь с статьями [1], [2], после чего с статьей [3]. Мы будем делать нечто похожее, как описано в третьей статье.

Сначала спроектируем конечный автомат. Я этот делал в файле формата Microsoft Excel. Сам файл можете скачать отсюда, а также всякий случай оставлю "скриншот", для тех кто качать не хочет:



Если вы прочитали, указанные мной, статьи, то для вас не составит труда разобраться с приведенным конечным автоматом. Хотя это может забрать не мало времени. После того, как КА спроектирован осталось перевести его в код на языке программирования C#, аналогично [3] статье.

Код проекта уже с транслитератором и лексическим блоком вы можете скачать отсюда. Проект создан в Visual Studio 2010 Premium.

Если вы заметите ошибки - пишите. Если у вас возникнут вопросы - задавайте их!

воскресенье, 3 октября 2010 г.

Перевод из одной системы координат в другую.

На самом деле перевод не простой. А вот такой:


То есть у вас есть установка фотографирующая точку P (красного цвета на изображении), и задача показать ее в новой координатной системе (V, U), в данном случае это две желтые линии, они означают вектора V, U.

На самом деле после решения данной задачи, стало понятно, что она довольно тривиальная.

Решение заключается вот в чем:  мы точку P повернем на угол между (V, U) и линией l2 + a2 (угол между линией l1, l2) + a1 (угол между l1 и осью X). После поворота мы ее сдвинем на расстояние -l2, потом повернем на угол -a2, после чего можем сдвинуть ее на расстояние -1l и повернем на угол a1 и сдвинем на расстояние -O (точка из которой начинается линия l1). В итоге мы получим точку P в новых координатах (V, U).

Если грубо, то вот, что мы делаем. Мы просто всю нашу фотографирующую установку складываем к осям Y, X.

Я решение выполнил используя javascript-библиотеку Dojo Toolkit, а конкретно dojox.gfx. Приведу пример кода перевода точки P(x, y) в P(v, u):

Весь код можете скачать отсюда. Но внимание, что бы код заработал не открывайте index.html, а создайте хост на веб-сервере, скопируйте туда файлы, а уже потом обращайтесь к нему через браузер.

Спасибо за внимание! Буду рад вопросам в комментариях!

пятница, 24 сентября 2010 г.

Простейший компилятор простейшего языка C в Assembler. Часть 1. Транслитератор

Два слова в общем

Для общего развития, никогда не помешает написать компилятор языка. Я не ставлю перед собой задачу написать компилятор c++ или c#, задачу которую я перед собой ставлю - это необходимый минимум для ознакомления с теорией компиляции.

Входной язык будет достаточно простой, урезанный по самое не могу, C. А выходной язык будет - язык Ассемблера.

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

Наш простейший компилятор языка C (далее TheSimpliestCCompiler - tsico), будет разбит на четыре блока или более: transliteration unit, lexical unit, syntax unit, generation unit. Получатся четырех-проходной компилятор. Чем же занимаются эти блоки?

Transliteration Unit


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

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

Lexical Unit

Лексический блок используя конечные автоматы обрабатывает символы с их символьными классами и на выходе отдает набор уже лексем.

Syntax Unit 

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

Generation Unit

Получает набор атомов и по ним строит программу на выходному языке. Это достаточно простой блок.

Транслитератор

Сегодня, мы приступим к транслитератору. Сразу оговорюсь, язык на котором, мы будем писать транслитератор - C#.

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

Определимся с символьными классами для простейшего прототипа языка C:

  • letter - [A-Za-z]
  • digit - [0-9]
  • whitespace - ' '
  • newline - '\n'
  • compare - [><=!]
  • arithmetic - [+-/*]
  • ( - '('
  • ) - ')'
  • ; - ';'
  • { - '{'
  • } - '}'
  • . - '.'
  • : - ':'

Символы, которые не вошли в данный перечень отнесем к классу other.

Я не буду приводить весь код транслитератор. Покажу лишь фрагмент:

class TransliterationUnit
{

    // ... 

    public void Transliterate(
        string input, string output)
    {
        // don't do this at production, 
        // reading string to memory can be 
        // so dangerous on files with larger size
        string code = File.OpenText(input).ReadToEnd().
                           Replace("\r", "").
                           Replace("\t", "").Trim().
                           ClearExtraWhitespaces();
        List<Symbol> symbols = new List<Symbol>();

        foreach (char c in code)
        {
            
            if (GetSymbolClass(c) != "other")
            {
                symbols.Add(new Symbol() { 
                   Value = c, 
                   Class = GetSymbolClass(c)});
            }
            else
            {
                _logger.Log(String.Format(
                    "Unexpected symbol - '{0}'", c));
            }
        }

        SaveSymbols(output, symbols);
    }

    // ... 
}

Если у вас есть желание ознакомиться с полной работающей версии транслитератора компилятора tsico (я упоминал о названии выше), то вы можете скачать проект с исходным кодом для Visual Studio 2010.

Литература

В завершение я бы хотел посоветовать вам книгу "Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман: Компиляторы. Принципы, технологии и инструментарий".

Отражение точки относительно произвольной прямой - Windows приложение

Как следствие тема о "отражении точки относительно произвольной прямой" тема развилась в такое простое приложение:


Для чего я публикую код этого приложения? Возможно, это не лучший пример, но там затронуты такие темы, как:

  • Перетаскивание графических объектов используя события MouseUp, MouseDown, MouseMove формы. 
  • Изменение курсора мыши на любой другой. 
  • Анимация. 
  • Работа с координатами, перевод координат из одной системы в другую. 
Если вам интересны вышеперечисленные темы, то код для вас. Этот код не является лучшим, а всего лишь наброски идей. Проект для Visual Studio 2010, вы можете скачать отсюда

понедельник, 13 сентября 2010 г.

Отражение точки относительно произвольной прямой

Я уточню название поста - зеркальное отражение точки относительно произвольной прямой проходящей через начало системы координат. Вот стоит перед вами такая задача, вам дана точка с координатами x;y и прямая заданная уравнением ax + by = 0. Программа должна на входе получить a; b; x; y, а на выходе новые отраженные x;y.

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

Например, нам нужно повернуть объект на не который угол. В данном случае мы можем использовать так называемую матрицу поворота (Rotation Matrix или просто R). Как ее получить?






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

В нашей задаче при зеркальной симметрии относительно прямой, мы также можем использовать матрицы. Для начала, посмотрим какие преобразования нам необходимо сделать:






Сначала мы повернем объект до нуля, потом отразим его и вернем в конечное положение. Данные преобразования выполнить достаточно легко - необходимо использовать матрицу поворота и отражения. Для удобства все преобразования сведем к одной матрице, назовем ее Result Matrix и Result Matrix = Rotation Matrix * Reflection Matrix * Rotation Matrix. А уже потом результирующую матрицу мы применим к объекту, в данном случае к точке. 

Как же мы узнаем угол поворота до оси абсцисс, легко мы знаем, что y = kx + b; и мы знаем, что k - это угловой коэффициент, который как раз и показываем отклонение относительно оси абсцисс, k = tan(alpha). Угол мы легко получим, alpha = atan(k). Но у нас же уравнение вида ax + by = 0 - не проблема, приведем его к нужному нам виду y = -(a/b)x; Тогда угол поворота alpha = atan(-a/b), обратный угол поворота это просто -alpha. Итого, у нас есть угол поворота, осталось найти матрицу отражения. А это легко, она также заранее известна, матрица отражения относительно оси абсцисс равна:


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



Код проекта на C#, который демонстрирует решение данной задачи я выложил здесь. Внимание! Проект работает в Visual Studio 2010, желательно Premium. Если же проект вам не удастся открыть, то достаточно скопировать код из файла Program.cs и перенести его в другой проект. 

Если заметите ошибки - сообщите, спасибо и успехов вам! 

суббота, 4 сентября 2010 г.

Сколько времени пользователь провел на сайте?

Я знаю по крайней мере 3 способа, как узнать сколько времени человек провел на сайте, если вы знаете больше, обязательно напишите об этом в комментариях. 

Способ №1. 

До этого способа я уже думаю многие догадались, суть его заключается вот в чем: когда пользователь заходит на сайт, мы с помощью JavaScript на событие load объекта window запускаем таймер и в какой-нибудь переменной записываем время посещений. Когда пользователь выходит с сайта и происходит событие unload объекта window мы на сервер посылаем собранное время с использованием технологии AJAX. 

Внимание! В этом способе есть одна загвоздка и она существенна. Браузер Opera не поддерживает событие unload объекта window. А это значит, что с помощью этого способа вы ни  
как не узнаете сколько времени человек провел на сайте. 

Способ №2. 

Когда пользователь заходит на сайт, мы все также как и в первом способе запускаем таймер, но теперь каждую секунду мы будем записывать в cookie. Тогда при следующем заходе на сайт, мы проверим cookie и если там будет значение мы отправим его на сервер и начнем отчет сначала, в противном случае мы просто начнем отчет. 

Этот способ лишен недостатка первого способа связанного с браузером Opera. Но в этом методе есть другой недостаток, если пользователь посетит сайт лишь один раз, мы так и не сможем узнать, сколько времени он провел, так как не будет повторного посещения, при котором мы сможем отправить на сервер собранные данные. 

Способ №3. 

Этот способ можно назвать самым прямо-в-лобным, так как суть его заключается в следующем, пользователь заходит на веб-страницу и мы запускаем таймер, внимание!  Теперь мы каждые 1-3 секунды отправляем запрос на сервер с подсчитанным секундами.

У этого способа один большой недостаток - постоянное общение с сервером. Зато он лишен недостатков двух предыдущих. 

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

Спасибо за внимание, удачного вам collecttiming`а!



четверг, 2 сентября 2010 г.

Обратная Польская Нотация

Мне больше нравится название на английском языке: Reverse Polish Notation (RPN), коим я и буду пользоваться.

Все мы с ранних классов, привыкли считать выражения такого вида 2 + 2 = ? или 2 * 2 + 2 = ?, может быть даже так (2 - 1) * 3 + 5 = ?. В нас буквально заложено понимание того, что каждая операция в приведенных выражениях имеет свой приоритет и это очень важно! В следствии чего дети всегда путали приоритеты или может быть вы не путали? Также усложняется читабельность ибо когда читал выражение, а потом увидел *, то сразу приходится в голове его перестраивать.

Более удобным видом описания мат. выражений является обратной польская запись (RPN), ее предложил польский математик Лукашевич. Она предлагает избавиться от приоритетов и убирает скобки. В общем выражение становится читать легче.

Давайте, попробуем перевести выше приведенные мной выражения в RPN, а делается это так:
2 + 2 в RPN будет 22+, то есть сначала идут операнды (их два), а затем операция, которую нужно над ними выполнить. Еще 2 * 2 + 2  22*2+, я знаю, что вам до сих привычней первый вид. Заметьте привычней, но не удобней. А теперь переведем (2 - 1) * 3 + 5 в RPN: 21-3*5+.

Помимо того, что мы избавились от скобок, так нам еще и не нужно запоминать приоритеты операций. Попробуем вычислить теперь последнее выражение 21-3*5+, по шагам:
  1. 21- = 1, в итоге получаем 13*5+
  2. 13* = 3, теперь rpn равняется 35+
  3. 35+ = 8, что и является результатом выражения. 
Помимо того, что мы облегчили способ чтения математических выражений для себя, так и компьютеру, теперь будет считать их легче. 

Теперь перейдем к нашей задаче. Нам необходимо реализовать калькуляцию выражений вида (A+B)*C/D-E используя язык программирования C#. Также вместо переменных (A, B, C  и т.д.) мы будем использовать простые цифры (0-9).

По крайнее мере есть два алгоритма перевода выражений в обратную польскую запись RPN:
  1. Используя бинарные деревья.
  2. Используя стек.
Я покажу перевод выражений в обратную польскую запись на примере стека, после чего продемонстрирую вычисление мат. выражений с использованием RPN.

Для перевода обычного мат. выражения в rpn я написал простой класс Converter, я не буду приводить весь код класса, его вы сможете скачать на code.google.com в конце статьи я указал ссылку, а приведу лишь метод ToRpn, ибо я считаю он более важен.

    public string ToRpn(string expression)
    {   
        // очищаем стек
        _stack.Purge();
        string output = "";
          
        // обходим строку посимвольно
        foreach (char c in expression)
        {   
            // если встретили закрывающую скобку
            if (c == ')')
            {  
                // вытаскиваем операции из стека
                // пока не дойдем до открывающейся скобки 
                char op = (char)_stack.Pop(); 
                while (op != '(') 
                {
                    output += op;
                    op = (char)_stack.Pop();
                }
            } 
            // если встретили цифру
            else if (Char.IsDigit(c))
            {
                // сразу добавляем ее к выходной строке
                output += c;
            } 
            // если открывающую скобку
            else if (c == '(')
            {
                // то помещаем ее в стек
                _stack.Push(c);
            }
            // если встретили арифметическую операцию
            else if (IsArithmeticOperation(c))
            {   
                // если стек - пуст
                if (_stack.IsEmpty)
                {
                    // помещаем операцию в стек
                    _stack.Push(c);
                }
                else
                {
                     // проверяем приоритеты 
                     if (GetPriority(c) > 
                         GetPriority((char)_stack.Top))
                     {
                         _stack.Push(c);
                     }
                     else
                     {
                         
                            while (!_stack.IsEmpty &&
                                   GetPriority(c) <= 
                                   GetPriority(
                                       (char)_stack.Top))
                            {
                                output += 
                                    (char)_stack.Pop(); ;
                            }                        
                            _stack.Push(c);
                     }
                }
            }
        }

        // добавляем в выходную строку оставшиеся символы
        while (!_stack.IsEmpty)
        {
            output += (char)_stack.Pop();
        }
   
        return output;
    }

Думаю, комментарии дадут вам понять шаги алгоритма, он достаточно прост. Visual Studio проект с использованием C# можно скачать отсюда.

Используемые материалы: 
Спасибо за внимание, вопросы и замечания принимаются в комментариях!

четверг, 26 августа 2010 г.

Статьи на тему бизнес-логики.

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

Итак, ссылки:
  1. Где бизнес-логика, сынок? (рус.)
  2. О бизнес-логике от Inside C++ (рус.)
  3. Паттерн Domain Model (рус.)
  4. Anemic Domain Model vs Rich Domain Model (рус.)
  5. Организация Модели в Zend Framework (рус.)
  6. Организация Модели: Валидация данных (рус.)
  7. Организация Модели. Управление доступом (рус.)
  8. Domain-Driven Design: Repository (рус.)

четверг, 19 августа 2010 г.

Как укоротить текст до 10 символов?

И так задача: http://pyha.ru/forum/topic/4916. Необходимо ссылку /some-link-with-fabulous-text сократить до 10 символов.

Первое, что мне приходить в голову это архивирование, но текст слишком маленький и архив получиться очень большой. По этому этот вариант отпадает. 
И я решаюсь на хэш-таблицы, где ключ - это будет уникальный хэш в 10 символов, а значение - длинная ссылка. Пример реализации приведу на файлах, вы сможете сделать тоже самое использую субд или другое хранилище. Для этого вам придется всего лишь реализовать интерфейс IHashTable и передать его в объект класса ShortifyUri. 
Пример рабочего кода: 
<?php 
// including library
require_once 'shortify-uri.php';
// creating shortifier instance
$shortifier = new UriShortifier(
    new FileHashTable('data.txt'));
// prepare uris`
$uris = array(
    'some-long-uri-with-text',
    'not-so-long-uri',
    'less-little-uri');
// shortifing uris`
$keys = array();
echo '<pre>';
foreach ($uris as $uri) {
    $key = $shortifier->
              shortify($uri);
    echo "Before shortifing: {$uri}, 
          after {$key} \n";
    $keys[] = $key;
}
// unshortifing uris`
foreach ($keys as $key) {
    $uri = $shortifier->
               unshortify($key);
    echo "Before {$key} 
          after {$uri} \n";
}
echo '</pre>';

Исходный код классов и интерфейса можно скачать отсюда

Изучение английского языка для программиста

Для программиста английский язык - это первый язык. И я решил заняться его изучением всерьез. Пока, что я сделал так. зарегистрировался на StackOverflow.com и стараюсь отвечать на вопросы по -английски. Помимо этого я нашел прекрасный сервис lingualeo.ru (реф. ссылка), меня он впечатляет, я читаю текст и не знакомые мне слова отмечаю, а потом эти слова закрепляю. Очень удобно, поверьте.

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

среда, 28 июля 2010 г.

Как узнать насколько две строки похожи?

Для того, что бы узнать на сколько похожи две строки, можно использовать алгоритм - "расстояние Левенштейна". О нем я сегодня узнал от Алены C++.

Я же хочу предложить вариант реализации на языке программирования php:

function levenshtein_distance($s, $t)
{
 $n = strlen($s); 
 $m = strlen($t); 
 
    /* if used russian or other UTF-8 characters 
    change above code with this 
 $n = mb_strlen($s, 'UTF-8'); 
 $m = mb_strlen($t, 'UTF-8');
 */
 
 if ($n == 0) 
  return $m;
 if ($m == 0) 
  return $n;
  
 $d = array();
 
 for ($i = 0; $i <= $n; $i++) {
  $d[$i][0] = $i;
 }
 
 for ($j = 0; $j <= $m; $j++) {
  $d[0][$j] = $j;
 }
 
 for ($i = 1; $i <= $n; $i++) {
  $sI = $s[$i - 1];
  for ($j = 1; $j <= $m; $j++) {
   $tJ = $t[$j - 1];
   $cost = ($tJ == $sI) ? 0 : 1;
   $d[$i][$j] = min(
    $d[$i - 1][$j] + 1, 
    $d[$i][$j - 1] + 1 , 
    $d[$i - 1][$j - 1] + $cost);
  }
 }

 return $d[$n][$m];
}

echo levenshtein_distance('gumbol', 'gambo');

В результате мы увидим "2", так как необходимо заменить u на a и удалить l.

воскресенье, 11 июля 2010 г.

Инициализация Zend_Translate из файла конфигурации приложения.

Мне больше нравиться настраивать все в файле конфигурации приложения(далее конфиг), хотя конечно встречаются моменты, когда необходимо воспользоваться bootstrap`ом. Сегодня, мне необходимо было инициализировать Zend_Translate из конфига. В документации, я не нашел информации по этому поводу. Поэтому порылся минут 5 в исходниках, после чего у меня получился такой код в .ini файле:

; Translate
resources.translate.adapter = "array"
resources.translate.data    = 
    APPLICATION_PATH  "/languages/ru/Zend_Validate.php"
resources.translate.locale  = "ru"

Код вполне работоспособный.

понедельник, 29 марта 2010 г.

О стандартизации различных CMS.

Последняя версия статьи здесь.

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

Что меня забавляет - так это, то что почти каждый программист пишет свою CMS, это уже как будто обязанность какая-то. А знаете, что обидно? Аргументируются самодельные CMS так:
  1. Я получу опыт. 
  2. Я сделаю лучше, чем Drupal/Wordpress/Joomla!/etc. 
  3. Моя CMS узкоспециализирована.
Конечно, кому-то удается и кто-то пишет CMS лучше, чем существующие. А кто-то загибается и прекращает свою работу на пол. пути.

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

Я пишу о проблеме совместимости модулей CMS. А также шаблонов и прочих компонентов. Почему я вижу в этом проблему?
  1. Потому, что хочется иметь одно решения, и не выбирать из множества. Как бы хочется "постоянства".
  2. Хочется, что бы то, что есть в Joomla, нажатием пары кликов, а то и одного, было и в Drupal. 
Вы просто посмотрите, выходит  модуль для Wordpress и тут же его "копируют" для Drupal. Копируют, имеется ввиду реализовывают схожий функционал. И так постоянно. А что если бы этого не нужно было делать?

Как я вижу решение данной проблемы? На данный момент я вижу два пути:
  1. Создание CMS, которая будет поддерживать модули, шаблоны и т.п. других CMS. На основе неких адаптеров, которые будут подстраивать "инородные" модули. 
  2. Создание единого стандарта CMS, который будет поддерживать каждая CMS.
Возможно есть еще варианты, но их я пока не вижу. О первом варианте, хочется сказать следующее, его реализация будет неимоверна сложная и в любом случае придется привлекать сторонних разработчиков. Конечно, кто-то уже видит в 1-ом варианте коммерческую изюминку. О втором варианте, здесь будет другой подход. Нужно будет уговорит сообщество разработчиков различных CMS сделать такой шаг. 

В любом случае, мне это кажется шагом вперед, шагом в будущее.