xFunc 1.4

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

Новые возможности

·         Рисование графика функций (масштабирование, передвижение графика, отображение координат);

·         Расширение количества поддерживаемых функций (логарифмы, тригонометрические и обратные тригонометрические функции, корень n-степени, модуль, константы);

·         Поддержка логических функций;

·         Добавлены два языка: русский и английский;

·         Поддержка разных мер измерения углов;

·         Изменения в коде парсинга (последнее введенное выражение кэшируется, мелкие улучшения);

·         Нахождение производной функции;

·         Упрощение введенного выражения;

·         Добавлены unit-тесты для проверки кода библиотеки;

·         Интерфейс адаптирован под новые возможности;

·         Сохранение состояния программы при выходе;

Что дальше?

Полное изменение пользовательского интерфейса.

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

На этом пока всё, код можно найти всё там же: xfunc.codeplex.com и github.com.

Двоичный поиск на C#

Реализация двоичного поиска на C#

Простенькая реализация, которая может искать элементы в любом массиве, реализующем интерфейс IComparable<T>. При нахождении элемента возвращает его индекс. Если элемент отсутствует возвращает null. Поиск не рекурсивный. С рекурсивным были проблемы на больших массивах. Массив с 10 000 элементов выкидывал StackOverflowException.

        static int? Search<T>(T[] array, int left, int right, T key) where T : IComparable<T>
        {
            while (right >= left)
            {
                int middle = (left + right) / 2;

                int comp = array[middle].CompareTo(key);
                if (comp > 0)
                {
                    right = middle - 1;
                }
                else if (comp < 0)
                {
                    left = middle + 1;
                }
                else
                {
                    return middle;
                }
            }

            return null;
        }

Создание своего ThreadPool'а на C# с фиксированным количеством потоков

Недавно, читая Хабр, я наткнулся на пост. В котором давался пример создания FixedThreadPool, с данными требованиями. Посмотрев код, я увидел, что при запуске каждой задачи создается новый поток (в данный момент автор поста поправил код). С примерными принципами работы пула потоков я знаком. Получается, что это никакой не пул, а просто некий планировщик задач по приоритетам.

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

Интерфейс класса FixedThreadPool я немного изменил. Теперь метод Execute принимает только один параметр Task, а приоритет был перенесен в класс Task. Такой вариант показался мне удобнее.

Source: github.com

TaskPriority:

    // Приоритет выполнения задачи.
    public enum TaskPriority
    {

        // Низкий приоритет.
        Low,
        // Средний приоритет.
        Normal,
        // Высокий приоритет.
        High

    }

Task:

    // Класс представляет задачу для выполнения в FixedThreadPool
    public class Task
    {

        private TaskPriority priority;
        private Action work;
        private bool isRunned;

        // Создает задачу с указанным приоритетом.
        public Task(Action work) : this(work, TaskPriority.Normal) { }

        // Создает задачу с указанным приоритетом.
        public Task(Action work, TaskPriority priority)
        {
            this.priority = priority;
            this.work = work;
        }

        // Запускает задачу.
        public void Execute()
        {
            lock (this)
            {
                isRunned = true;
            }
            work();
        }

        // Приоритет задачи. Устанавливается только при создании задачи.
        public TaskPriority Priority
        {
            get
            {
                return priority;
            }
        }

        // Запущена ли задача. (True - запущена, False - стоит в очереди на выполнение)
        public bool IsRunned
        {
            get
            {
                return isRunned;
            }
        }

    }

FixedThreadPool:

    // Пул потоков. В нем задача запускаются по приоритетам. Если количество потоков больше или равно 4, то на каждые 3 задачи с высоким приоритетом - будет запущена задача с нормальным приоритетом. Если количество потоков меньше 4, тогда задачи выполняются прямо следуя приоритетам. Задачи с низким приоритетом выполняются в последнюю очередь.
    public class FixedThreadPool : IDisposable
    {

        private int numberThreads;

        private ManualResetEvent stopEvent;
        private bool isStoping;
        private object stopLock;

        private Dictionary<int, ManualResetEvent> threadsEvent;
        private Thread[] threads;
        private List<task> tasks;

        private ManualResetEvent scheduleEvent;
        private Thread scheduleThread;

        private bool isDisposed;

        // Создает пул потоков с количеством потоков равным количеству ядер процессора.
        public FixedThreadPool() : this(Environment.ProcessorCount) { }

        // Создает пул потоков с указанным количеством потоков.
        public FixedThreadPool(int numberThreads)
        {
            if (numberThreads <= 0)
                throw new ArgumentException("numberThreads", "Количество потоков должно быть больше нуля.");

            this.numberThreads = numberThreads;

            this.stopLock = new object();
            this.stopEvent = new ManualResetEvent(false);

            this.scheduleEvent = new ManualResetEvent(false);
            this.scheduleThread = new Thread(SelectAndStartFreeThread) { Name = "Schedule Thread", IsBackground = true };
            scheduleThread.Start();

            this.threads = new Thread[numberThreads];
            this.threadsEvent = new Dictionary<int, ManualResetEvent>(numberThreads);

            for (int i = 0; i < numberThreads; i++)
            {
                threads[i] = new Thread(ThreadWork) { Name = "Pool Thread", IsBackground = true };
                threadsEvent.Add(threads[i].ManagedThreadId, new ManualResetEvent(false));

                threads[i].Start();
            }

            this.tasks = new List<task>();
        }

        // Прерывает выполнение всех потоков, не дожидаясь их завершения и уничтожает за собой все ресурсы.
        ~FixedThreadPool()
        {
            Dispose(false);
        }

        // Высвобождает ресурсы, которые используются пулом потоков.
        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }

        // Высвобождает ресурсы, которые используются пулом потоков.
        protected virtual void Dispose(bool disposing)
        {
            if (!isDisposed)
            {
                if (disposing)
                {
                    scheduleThread.Abort();
                    scheduleEvent.Dispose();

                    for (int i = 0; i < numberThreads; i++)
                    {
                        threads[i].Abort();
                        threadsEvent[threads[i].ManagedThreadId].Dispose();
                    }
                }

                isDisposed = true;
            }
        }

        private Task SelectTask()
        {
            lock (tasks)
            {
                if (tasks.Count == 0)
                    throw new ArgumentException();

                var waitingTasks = tasks.Where(t => !t.IsRunned);
                var highTasks = waitingTasks.Where(t => t.Priority == TaskPriority.High);
                var normalTasks = waitingTasks.Where(t => t.Priority == TaskPriority.Normal);

                if (highTasks.Count() > 0)
                {
                    if (numberThreads >= 4)
                    {
                        var runnedHighTasks = tasks.Where(t => t.IsRunned && t.Priority == TaskPriority.High);
                        var runnedNormalTasks = tasks.Where(t => t.IsRunned && t.Priority == TaskPriority.Normal);

                        if (runnedHighTasks.Count() / (runnedNormalTasks.Count() + 1) < 3)
                        {
                            return highTasks.First();
                        }
                        else
                        {
                            return normalTasks.First();
                        }
                    }
                    else
                    {
                        return highTasks.First();
                    }
                }
                else
                {
                    if (normalTasks.Count() > 0)
                    {
                        return normalTasks.First();
                    }
                    else
                    {
                        var lowTasks = tasks.Where(t => t.Priority == TaskPriority.Low).ToArray();
                        return lowTasks.FirstOrDefault();
                    }
                }
            }
        }

        private void ThreadWork()
        {
            while (true)
            {
                threadsEvent[Thread.CurrentThread.ManagedThreadId].WaitOne();

                Task task = SelectTask();
                if (task != null)
                {
                    try
                    {
                        task.Execute();
                    }
                    finally
                    {
                        RemoveTask(task);
                        if (isStoping)
                            stopEvent.Set();
                        threadsEvent[Thread.CurrentThread.ManagedThreadId].Reset();
                    }
                }
            }
        }

        private void SelectAndStartFreeThread()
        {
            while (true)
            {
                scheduleEvent.WaitOne();
                lock (threads)
                {
                    foreach (var thread in threads)
                    {
                        if (threadsEvent[thread.ManagedThreadId].WaitOne(0) == false)
                        {
                            threadsEvent[thread.ManagedThreadId].Set();
                            break;
                        }
                    }
                }

                scheduleEvent.Reset();
            }
        }

        private void AddTask(Task task)
        {
            lock (tasks)
            {
                tasks.Add(task);
            }

            scheduleEvent.Set();
        }

        private void RemoveTask(Task task)
        {
            lock (tasks)
            {
                tasks.Remove(task);
            }

            if (tasks.Count > 0 && tasks.Where(t => !t.IsRunned).Count() > 0)
            {
                scheduleEvent.Set();
            }
        }

        // Ставит задачу в очередь.
        public bool Execute(Task task)
        {
            if (task == null)
                throw new ArgumentNullException("task", "The Task can't be null.");

            lock (stopLock)
            {
                if (isStoping)
                {
                    return false;
                }

                AddTask(task);
                return true;
            }
        }

        // Ставить несколько задачь в очередь.
        public bool ExecuteRange(IEnumerable<task> tasks)
        {
            bool result = true;
            foreach (var task in tasks)
            {
                if (!Execute(task))
                    result = false;
            }

            return result;
        }

        // Останавливает работу пула потоков. Ожидает завершения всех задач (запущенных и стоящих в очереди) и уничтожает все ресурсы.
        public void Stop()
        {
            lock (stopLock)
            {
                isStoping = true;
            }

            while (tasks.Count > 0)
            {
                stopEvent.WaitOne();
                stopEvent.Reset();
            }

            Dispose(true);
        }

    }

Парсер математических и логических выражений на C#

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

Это мой первый пост и особо не судите строго, особенно код, он далеко не самый лучший. =)

История

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

Реализация

Первый пришла идея создания из математического выражения дерева выражения, которое будет построено с учетом приоритетов операций. Каждая математическая операция представляется своим классом, который реализует интерфейс IExpression с единственным методом Calculate:

public interface IExpression
{
    double Calculate(ParameterCollection parameters);
}

Также, бинарные и унарные операторы имеют отдельные базовые классы. Класс UnaryExpression имеет только одну переменную типа IExpression, а BinnaryExpression - две.  Благодаря этому и получается дерево. А методы Calculate реализованы так, что они также используют метод Calculate, объектов типа IExpression, которые содержатся в классе. Немного запутанное объяснение получается, но если взглянуть на код понятнее становится.

Всю структуру классов можно видеть на следующем изображении:

Меня такой способ вполне устраивал. И вполне нормально работал при ручном построении дерева. Но вот как построить такое дерево из вводимой строки, оставалось вопросом. Возникала проблема правильно рассчитывать приоритет операций и учитывать скобки для правильного построения дерева.

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

Ну а далее уже было всё просто. Нужны были методы для конвертирования в ОПН и из ОПН в дерево классов IExpression. Также, я использовал ещё один метод, который из обычной строки создавал коллекцию токенов (для упрощения работы с входной строкой). Весь код создания токенов был написан вручную (обход всей строки по символьно). Регулярные выражения не использовались.

Для поддержки переменных в выражении использовался класс унаследованный от Dictionary<char, double>. И передаваемый в качестве параметра методу Calculate.

В итоге

Получилась вполне рабочая библиотека, к которой оставалось только прикрутить пользовательский интерфейс.

Код доступен на codeplex.com и github.com. В архиве два проекта: библиотека, в которой содержится весь код парсера и само приложение, содержащее пользовательский интерфейс на WPF.

P.S. Добавлена возможность постоить график функции.
P.P.S. Добавлена возможность парсинга логических выражений.