Форум АНТИЧАТ - Как не нужно писать программы

На написание этой мини-статьи меня натолкнул топик http://forum.antichat.ru/thread162874.html в котором автор реализует подсчет числа различных символов в тексте. При этом нарушаются все мыслимые и немыслимые правила построения архитектуры приложения, а также не выполняются никакие требования к качеству кода, его производительности, масштабируемости и т.п.

Рассмотрим основные недостатки решения, приведенного в http://forum.antichat.ru/thread162874.html :
1) Не разделены интерфейс пользователя и функциональная часть программы. Функционал содержится непосредственно в коде главной формы. Он никак не отделен ни синтаксически ни семантически, что приведет в последствии к тому, что код невозможно будет повторно использовать, будет затруднено его понимание и модификация, будет невозможно масштабирование приложения.
2) Интерфейсные элементы испульзуются как хранилище информации (так ListView >хранит< найденные символы, хотя его основная задача - отображать найденные элементы). В результате - невозможность масштабирования, даже минимального.

Например, если автор вдруг захочет паралельно обрабатывать два текста - он просто физически не сможет этго сделать, поскольку ListView - только один.
3) Алгоритм, как и его реализация, крайне неэффективен. Во-первых используется попросту полный перебор (автор ищет символ в массиве уже найденых символов, что приводит к числу операций O(n^2)). Во-вторых поиск ведется в структурах, не предназначенных для поиска(и вообще хранения информации) - в ListView. Я уж не говорю про такие "мелочи", как нетипизированный ArrayList, поскольку потери на боксинг/анбоксинг выглядят невинно на фоне остального "алгоритма".
4) Приложение имеет недружественный интерфейс. Во время выполнения операции рассчета статистики оно попросту зависает. В паре с неэффективным и долгим алгоритмом это вызовет "недоумение" пользователя.

Теперь рассмотрим реализацию приложения, в которм я попытался устранить все вышеописанные недостатки. Оно не претендует на абсолютную правильность, но по крайней мере оно соответствует тому минимальному уровню, который должен присутствовать в любом, даже в самом простом приложении.

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

Теперь вычисления живут в отдельном классе и в отдельном файле StatCalculator.cs. Можно было бы и вынести этот класс в отдельный проект, но в данном, простейшем случае это уже перебор :). Разделив интерфейс пользователя и класс-вычислитель я убиваю кучу зайцев и Мазая заодно: Во-первых теперь, у меня есть два класса, у каждого из которых есть свой простой и понятный функционал (в литературе это называется принцип единственной ответственности) . Один класс (MainForm) занимается диалогом с пользователем, другой (StatCalculator) - занимается подсчетом статистик в тексте. При этом калькулятор ничего не знает о MainForm, что снижает связность архитектуры, и позволяет использовать калькулятор в других местах программы, либо вообще в других приложениях. Во-вторых, вынеся функционал в отдельный класс я создаю возможность маштабирования и расширения приложения. Так, например, я могу вычислять статистику сразу нескольких текстов - просто создав необходимое число калькуляторов и запустив их в разных потоках. Либо, я могу вообще вынести класс StatCalculator в сервис, и запускать на удаленном сервере - просто передавая ему исходный текст и принимая рассчетную статистику в ответ. В общем, одно только разделение функционала уже решает часть проблем, описанных выше.

Далее, я выделил основные функциональные части программы: ввод текста - вычисление статистик - вывод результата.
Ввод текста автоматически реализуются компонентами формы (TextBox и т.п.), вычисление статистик берет на себя StatCalculator, а выводом результатов занимается метод UpdateInterface() (который при усложнении приложения, можно вынести и в отдельный класс, но здесь я не стал заморачиваться).
Явное разделение функционала по частям дает возможность создания более сложных связей между частями программы.

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

Теперь об алгоритме. Начинающие программисты часто не умеют пользоваться(или даже не знают о них) такими абстрактными типами данных как списки, хеши(HashSet), словари(Dictionary), остортированные списки (SortedList, SortedDictionary), деревья. Часто пользуются исключительно массивами. Не буду останавливаться на целесообразности применения того или иного типа данных - это тема для отдельной статьи. Скажу лишь, что в задаче которую мы решаем, нужно применять Dictionary. При чем хотелось бы особо отметить слово "нужно" именно нужно, а не "можно". В каждой задаче, как правило, есть единственная верная структура даных, которая нужна для правильного и быстрого решения. Программист должен спиным мозгом, на автомате, чувствовать какой именно тип даных нужно использовать в данном конкретном случае. Применение неудачного типа данных влечет потенциальные ошибки(например неуникальность ключей) и гарантированно снижает производительность (например, выполняется полный перебор при поиске).

Итак, в нашей задаче нужно использовать Dictionary. Почему? Во-первых потому что результирующая статистика разбита по символам и в выходном списке один символ может встречаться только один раз (уникальность ключа - одно из свойств Dictionary). Во-вторых, при рассчете статистики, нам нужно будет для каждого символа текста, выяснять был ли уже этот символ и сколько раз он встречался, т.е. фактически производить поиск этого символа в статистиках. Поскольку символов во входном тексте может быть очень много, то нужно максимально ускорить процесс поиска. А у Dictionary скорость доступа к элементам по ключу - O(1) - то что нам нужно, быстрее не бывает. Ну и наконец в-третьих - нам нужно где-то хранить саму статистику (число символов, проценты и т.п.) и тут тоже нам подходит Dictionary (потому что он хранит как ключ, так и значение, в отличии от HashSet например, которое хранит только ключ).

Ниже приведен метод, рассчитыающий необходимые нам статистики. Он так прост, что коментарии излишни:

Код:

        public void CalcCharStat()

        {

            statistics = new Dictionary<char, CharStat>();

            //считаем частоты

            foreach (char c in text)

            {

                if (!statistics.ContainsKey(c))

                    statistics[c] = new CharStat();

                statistics[c].frequency++;

            }

            //считаем сумму всех частот 

            totalChars = 0;

            foreach (CharStat stat in statistics.Values)

                totalChars += stat.frequency;

            //считаем процент

            if (totalChars > 0)

                foreach (CharStat stat in statistics.Values)

                    stat.percent = (float)stat.frequency / totalChars;

        }

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

Быстродействие приведенного алгоритма: O(n) (что является теоретическим пределом для данной задачи).

Теперь остановимся еще на двух моментах - запуск рассчетов в отдельном потоке и отображении результатов.

Запуск рассчета сделан в отдельном потоке. Он создается в главном потоке приложения, запускается и далее приложение ждет пока он завершится, обрабатыая попутно события главной формы, так что приложение в целом - не виснет. При этом достигаются несколько целей:
1) Приложение реагирует на действия пользователя и не "висит"
2) Есть возможность сделать прогресс-бар, для отображения хода рассчета статистик
3) Есть возможность сделать кнопку Stop для останова рассчетов, не дожидаясь конца алгоритма.

Отображение результатов тоже очень простое:

Код:

private void UpdateInterface()

        {

            //очищаем listView

            lvStat.Items.Clear();

            //заносим результаты рассчетов в listView

            foreach (KeyValuePair<char, CharStat> pair in calculator.statistics)

            {

                //приводим char к презентабельному виду

                string presentableChar;

                if (pair.Key <= ' ')

                    presentableChar = "#" + Convert.ToByte(pair.Key);

                else

                    presentableChar = pair.Key.ToString();

                //создаем элемент listView

                ListViewItem item = new ListViewItem(

                    new string[]{

                    presentableChar,

                    pair.Value.frequency.ToString(),

                    string.Format("{0:0.00}", 100*pair.Value.percent)});//здесь округляем процент до двух знаков после запятой

                lvStat.Items.Add(item);

            }

            //обновляем статус бар

            lbTotal.Text = string.Format("Total chars: {0}", calculator.totalChars);

            lbTotalUnique.Text = string.Format("Total unique chars: {0}", calculator.statistics.Count);

        }

Тут можно обратить внимание на двух моментах - во-первых здесь мы преобразуем символы в читабельный вид (в dictionary они хранятся в естественном, "сыром" виде) - ведь не все символы можно отобразить на экране (например, возврат каретки, пробел или табуляцию). Во-вторых здесь мы производим округление рассчитанных процентов. Округление в пользовательском интерфейсе дает два важных преимущества:
1) Сохраняется целостность данных, поскольку сумма процентов внутри dictionary - ровно 100%. После округления это было бы уже не так.
2) Сохраняется возможность указания необходимой точности процентов пользователем. Причем точность процентов можно менять уже после рассчетов.

Вот в общем-то и все что хотелось сказать :)
Полная реализация - здесь http://rapidshare.com/files/322173460/WindowsFormsApplication5.zip.html .