|
Навигация
|
Главная » Игры Использование gperf для эффективной обработки параметров командной строки в C/C++ (исходники)Источник: IBM developerWorks Россия Арпан Сен, Рахул Кардам Обработка параметров командной строки и необходимость gperfИсторически обработка параметров командной строки является одной из областей разработки программного обеспечения, которым уделяется наименьшее внимание. Практически у любого более или менее сложного программного обеспечения существует множество параметров командной строки. На самом деле, нет ничего необычного в сотнях строк кода с операторамиif-else , обрабатывающих вводимые пользователем данные, и поддержка такого кода становится очень трудоемкой даже для опытных программистов. В таких случаях большинство разработчиков на C предпочитают использовать длинные (и, зачастую, вложенные) операторы if-else , дополненные для удобства чтения функциями из библиотеки ANSI C, например, strcmp , strcasecmp и strtok , что видно из Листинга 1.Листинг 1. Обработка параметров командной строки в стиле C
Вместо программного интерфейса API из ANSI C разработчик C++, скорее всего, будет использовать строковые функции из стандартной библиотеки шаблонов (Standard Template Library, STL). Однако же, и здесь не уйти от вложенных последовательностей операторов if-else . Определенно, такой подход нельзя назвать масштабируемым с ростом количества параметров. Для запуска обычной программы с N параметрами, код должен будет выполнить O(N2) сравнений. Чтобы создать код, который будет быстрее в работе и проще в поддержке, имеет смысл использовать хеш-таблицы, в которых будут храниться параметры командной строки, и впоследствии применять хеш для проверки данных, введенных пользователем.Здесь в игру вступает gperf. Он создает хеш-таблицу на основе предварительно заданного списка разрешенных параметров командной строки, а также функцию поиска, временная сложность которой составляет O(1). Таким образом, для вызова обычной программы с N параметрами код должен выполнить только O(N) [N*O(1)] сравнений, что обозначает увеличение производительности на порядок по сравнению с обычным кодом. Особенности использования gperfGperf считывает набор ключевых слов из файла, предоставляемого пользователем (обычно это файл с расширением .gperf, хотя это и не обязательно), например, commandoptions.gperf, и создает исходный код C/C++ для хеш-таблицы, методов хеширования и поиска. Код направляется на стандартный вывод, который может быть перенаправлен в файл следующим образом:
Примечание: Параметр -L сообщает gperf, что создаваемый код должен быть C++.Формат входного файла gperfВ Листинге 2 представлен формат входного файла gperf.Листинг 2. Формат входного файла gperf
Формат состоит из нескольких элементов: включение кода C, объявления, ключевые слова и функции. Включение кода CВключение кода C представляет собой необязательную секцию, заключенную между%{ и %} . Код C и комментарии, приведенные в этой секции, копируются в выходной файл, генерируемый gperf, без изменений. (Обратите внимание на схожесть с утилитами GNU flex и bison.)ОбъявленияСекция объявлений также необязательна; вы можете полностью опустить ее содержимое, если не будете вызывать gperf с параметром-t . Однако если вы включите этот параметр, последним компонентом раздела объявлений должна быть структура, первым полем которой должен быть идентификатор name типа char* или const char* .Впрочем, в gperf существует возможность изменения названия первого поля путем использования параметра -K . Например, если вы желаете назвать это поле command_option , вызывайте gperf следующим образом:
В Листинге 3 представлены разделы включения кода C и объявлений. Листинг 3. Секции включения кода C и объявлений
Ключевые словаВ этой секции содержатся ключевые слова - в данном случае это предварительно определенные аргументы командной строки. Каждая строка этого раздела, начинающаяся со знака # в первой позиции, является комментарием. На первом месте каждой незакомментированной строки указывается ключевое слово, кавычки, обычно связываемые с типомchar* , здесь необязательны. Кроме того, за ключевым словом могут следовать дополнительные поля, которые разделяются запятыми и завершаются концом строки. Как видно из Листинга 4, эти поля являются последней структурой секции объявлений.Листинг 4. Секция ключевых слов
const char* command_option структуры CommandOption; вторая запись ссылается на поле int OptionCode этой же структуры. Итак, что на самом деле здесь происходит? На самом деле, это способ инициализации утилитой gperf хеш-таблицы, в которой будут храниться параметры командной строки и связанные с ними атрибуты.ФункцииФункции - это еще одна необязательная секция. Текст этой секции начинается с символов%% и целиком, до конца файла, копируется в генерируемый файл без изменений. Так же, как и в секции объявлений, вся ответственность за верность кода C/C++ в этой секции лежит на пользователе.Выходной файл gperfGperf хеширует заранее определенный набор ключевых слов, после чего выполняет быстрый поиск по этим словам. В соответствии с этой методикой, gperf выводит две функции:hash() и in_word_set() . Первая - это процедура хеширования, тогда как вторая используется для поиска. Выходной файл gperf может быть либо на языке C, либо на C++, в зависимости от выбранных вами параметров. Если вы желаете, чтобы выходной файл был на языке C, будут созданы две функции C с приведенными выше названиями. Если выходной файл формируется на языке C++, gperf создает класс Perfect_Hash , в котором содержатся два этих метода.Примечание: Для того, чтобы изменить название создаваемого класса, используйте параметр -Z .Прототип функции хеширования имеет следующий вид:
где str представляет параметр командной строки, а len - его длину. Например, для аргумента командной строки +helpverbose , значение str будет +helpverbose , а len - 12 .Функцией поиска в хеше, созданном gperf, является in_word_set() . Прототип этой процедуры зависит от параметра -t , указываемого пользователем. Если вы не указали этот параметр, вы будете иметь дело с параметрами командной строки, определяемыми пользователем, хранящимися в хеше gperf как данные, а не со структурой, связанной с командной строкой.Например, в Листинге 3 определена структура CommandOption , связанная с аргументом пользовательской команды, который вернет процедура in_word_set() . Вы можете изменить название процедуры с помощью параметра -N . Аргументы процедуры схожи с описанными ранее для функции hash() :
Основные параметры gperfGperf является гибко настраиваемым инструментом, принимающим несколько параметров. Все параметры gperf описаны в онлайновом справочнике (смотри ссылку в разделе Ресурсы), в их число входят:
Обзор внутренней структуры gperfСтатическое поисковое множество (Static search set) представляет собой абстрактный тип данных с операциямиinitialize , insert и retrieve . Функции идеального хеша являются оптимизированными по времени и занимаемой памяти реализациями статических поисковых множеств. Gperf - это генератор идеальных хеш-функций из списка ключевых слов, предоставляемых пользователем. Gperf переводит список ключевых слов из n элементов, предоставляемый пользователем, в исходный код, содержащий поисковую таблицу из k элементов и две функции:
Key_List ) и массиве связанных значений (asso_values ). Каждое ключевое слово и его параметры считываются из файла, предоставляемого пользователем, и сохраняются как узлы в связанном списке Key_List . В качестве ключа при поиске для идеальной функции hash() gperf рассматривает только часть символов каждого ключевого слова. Эта часть называется ключом ключевого слова (keyword signature) , или keysig .Массив связанных значений генерируется в функции hash() и индексируется по символам keysig . Gperf выполняет многократный поиск конфигурации связанных значений, устанавливающей соответствие между всеми n ключами keysig и уникальными значениями хеша. Когда gperf находит конфигурацию, устанавливающую уникальное место расположения каждого ключа keysig в создаваемой таблице поиска, создается идеальная функция hash() . Получившаяся идеальная функция hash() возвращает значение unsigned int , лежащее в диапазоне 0..( k -1), где k - максимальное значение хеша ключевого слова +1.В случае, когда k = n, создается минимальная идеальная функция hash() . Значение хеша ключевого слова обычно рассчитывается путем сочетания связанных значений ключа keysig с его длиной. По умолчанию функция hash() добавляет связанное значение первой позиции индекса ключевого слова и связанное значение последней позиции индекса к его длине, например:
Пример проектаЧтобы проиллюстрировать изложенный выше материал, рассмотрим небольшой проект. Посмотрите на файл gperf, приведенный в Листинге 5.Листинг 5. command_options.gperf
В листинге 6 показан файл заголовка command_options.h , включаемый в файл gperf.Листинг 6. Заголовок command_options.h
Вызов gperf из командной строки будет выглядеть следующим образом:
Хеш-таблица генерируется в файле perfecthash.hpp. Поскольку в командной строке был указан параметр -G , генерируется глобальная хеш-таблица. Так как при вызове gperf был указан параметр -C , хеш-таблица объявляется с атрибутом const . В Листинге 7 представлен сформированный исходный код.Листинг 7. Созданный perfecthash.hpp
И, наконец, в Листинге 8 показан основной исходный код. Примечание: Листинг 8 показывает, что вы можете найти любой параметр командной строки в заданном перечне ключевых слов за неизменное время, и, следовательно, принять необходимые меры для обработки этого параметра. Временная сложность IsValidCommandLineOption равна O(1).Листинг 8. gperf.cpp, определяющий точку входа приложения
Примечания: Все примеры, приведенные в этой статье, были проверены с помощью gperf версии 3.0.3. Если вы используете более раннюю версию, то при вызове может потребоваться указание параметра -p .ЗаключениеУтилита gperf настроена на быстрое формирование идеального хеша для небольших и средних множеств данных. Однако у gperf также есть другие области применения. Фактически, это лучший инструмент для работы с идеальными хешами для ключевых слов в компиляторах GNU, а последние усовершенствования также позволяют вам работать с более крупными массивами данных. Попробуйте использовать gperf в вашем следующем проекте.Diablo 3. Третье погружение в дьявольщину. Рецензия: Gears of War 3. Шутер со стальными яйцами. Самоисполняемый phar как способ распространения веб-приложений. Обзор игры The Cursed Crusade. Высокие технологии мотивации. Главная » Игры |
© 2024 Team.Furia.Ru.
Частичное копирование материалов разрешено. |