На написание этой мини-статьи меня натолкнул топик /thread162874.html в котором автор реализует подсчет числа различных символов в тексте. При этом нарушаются все мыслимые и немыслимые правила построения архитектуры приложения, а также не выполняются никакие требования к качеству кода, его производительности, масштабируемости и т.п. Рассмотрим основные недостатки решения, приведенного в /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 например, которое хранит только ключ). Ниже приведен метод, рассчитыающий необходимые нам статистики. Он так прост, что коментарии излишни: Code: 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 для останова рассчетов, не дожидаясь конца алгоритма. Отображение результатов тоже очень простое: Code: 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 .
>>O(n^2) O(n * размер алфавита), где n - длина слова >>Dictionary не знаю точно ничего про этот класс, но рискну предположить, что реализован он как дерево, поэтому поиск вроде containsKey и тп работает за log. И это не считая того, что сам класс, естественно, сильно запутан в целях универсальности. ИМХО, в таких случаях надо делать как-то так (сорри, но на сях): Code: UINT count[ALPHABET_SIZE]={0}; ... char c; ... ++count[c]; ... Так O(1), а памяти на алфавит не очень жалко.
Dictionary это не дерево, это хеш-таблица. Время доступа O(1). О чем прямо написано в MSDN: Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<(Of <(TKey, TValue>)>) class is implemented as a hash table. Оно то да, тока не будем забывать, что в .net строки всегда используют юникод, а в юникоде размер алфавита где-то так около 65536 (для UTF16), так что неизвестно еще что больше, размер алфавита или длина входной строки
>>это хеш-таблица тогда преимущества просто нет UINT count[ALPHABET_SIZE]={0}; - это и есть, по сути, хеш-таблица, только хеши уникальны и f(x) = x. Имеет смысл использовать хеши как в обычной хеш-таблице, только если у нас а) размер алфавита порядка десятков миллионов б) присутствует достаточно ограниченное количество разных символов, но заранее не известных. Иначе эти вычисления хеша и внутреннее устройство класса будут, конечно, кушать O(1), но такое жирное-прежирное O(1), у которого изо всюду эти же O(1)-шки точат >>65536 всё равно, один раз перед выводом мы можем себе позволить по нему пройтись а автора той темы вообще вроде только печатаемые символы интересовали.
desTiny, в целом я согласен, что в рамках данной задачи можно использовать вырожденный хеш, размером с алфавит. Просто в реальных программах такое встречается редко, как правило, ключ имеет бесконечный (или оочень большой) алфавит. А решение с Dictionary в данном случае предпочительнее, потому что 1) Оно стандартно. Применение стандратного класса фреймворка лучше, поскольку он поддерживается другими классами фреймворка. 2) Оно более универсально. Если автор завтра вдруг решит считать статистику не букв, а слов, то алгоритм с Dictionary будет работать практически без изменений, в то время как специализированный UINT count[ALPHABET_SIZE] работать не сможет. 3) Оно более наглядно. Смысл приведенной мною программы - не в подсчете статистики за минимальное время, а в том, что бы показать пример применения хешей для повышения производительности.
>>Смысл приведенной мною программы - не в подсчете статистики за минимальное время, а в том, что бы показать пример применения хешей для повышения производительности. мне кажется, что скорее получилось передать идею масштабируемости с основными пунктами а) разделение интерфейса и кодесов б) использование стандартных классов Тихое стремление к идеальному коду но не люблю я эту абстрактную "масштабируемость". Вот для определения статистики по словам пишется быстрее всего, естественно, хеш, именно таким образом. Но какое-нибудь, например, суффиксное дерево может, случайно, и побыстрее отработать - от небольшого изменения условия может сильно изменится метод решения. PS кусок из интервью со Страуструпом:
Код (просто как "кусок" программы) действительно редко используется повторно, а вот библиотеки - повсеместно и часто.
Я на работе пишу проект, который начали делать ещё в 90х годах. И в котором постоянно чтото меняли-добавляли. В таком случае можно говорить о повторном использовании и к масштабируемости стоит задумываться заранее. Т.к. сегодня нужно одно через пару версий - другое. Или вообще потребуется компоненты системы разносить по разным серверам.
а с Фортрана так кодесы и не переписали нет, если действительно работает, то я не против //>>в 90х годах //ты же вроде на яве пишешь?
Угу, официально Java+C++, по факту только Java. Код с C++ переносится на Java и новые части пишутся на Java. Т.к. от C++ решили в целом избавиться в проекте.
Я не столько про тогда, сколько про сейчас. Вот начинал я писать свой прошлый модуль в 2008 году, требования были одни, сдали версию, всё окей. (Версия всего огромного проекта, в котором пол года моей работы - песчинка). Начинается новая версия, от заказчика новые требования - часть кода своего модуля приходится переписывать, часть - реюзать. И чем менее связный код в целом, тем проще будет его отдельные части переделывать. (И тем позже возникнет желание поскорее "это" спихнуть кому нибудь другому). Как в конструкторе, вынул один блок, вставил другой. Оставшаяся часть используется повторно и для этой версии.