Исследование операции поиска символа в строке (PHP)

ИГОРЬ ОРЕЩЕНКОВ, инженер-программист, iharsw@tut.by

Исследование операции поиска
символа в строке (PHP)

В статье рассказывается о способе измерения времени выполнения и сравнения эффективности конструкций языка программирования PHP

Производительность – одна из важнейших характеристик программы

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

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

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

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

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

Проблема выбора эффективного решения

Однако при решении практических задач прямое применение результатов теоретических изысканий не всегда возможно. Они верны в тех случаях, когда алгоритмы выполняются в одинаковых условиях. Но архитектура современных компьютеров представляет собой многоуровневую систему [2], а современные языки и системы программирования предоставляют средства, работающие на разных уровнях этой архитектуры (см. рис. 1). Из-за этого даже малоэффективные алгоритмы, задействованные через встроенные функции языка, которые реализованы на низких уровнях, могут показать более быструю работу по сравнению с реализациями эффективных алгоритмов на верхнем уровне.

Например, в ходе лексического анализа [3] текста приходится решать вопрос о принадлежности символа некоторому множеству: прописных или строчных букв латинского или русского алфавита, цифр, знаков препинания или пробельных символов. Для этого можно провести поиск символа в эталонной строке. Если анализируемые тексты достаточно велики, то имеет смысл выполнять поиск наиболее эффективным способом, учитывая, что эта операция будет повторяться многократно.

В языке программирования PHP решить поставленную задачу можно одним из трех способов:

• с помощью встроенной функции strpos (S, C), выполняющей линейный поиск символа C в строке S;
• реализовав бинарный поиск в отсортированном массиве символов;
• с помощью логического выражения, проверяющего принадлежность символа некоторому диапазону: L ≤ C ≤ R.

Какой из этих вариантов будет работать быстрее?

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

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

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

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

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

Понимая глубину проблемы, было принято решение о разработке на языке PHP класса, автоматизирующего процесс тестирования и обеспечивающего необходимые для него условия.

Статью целиком читайте в журнале «Системный администратор», №1-2 за 2015 г. на страницах 77-81.

PDF-версию данного номера можно приобрести в нашем магазине.

1. Вирт Н. Алгоритмы и структуры данных. //Пер. с англ. – 2-е изд., испр. – СПб.: «Невский Диалект», 2005. – 352 с.
2. Таненбаум Э. Архитектура компьютера. – 5-е изд. (+CD). – СПб.: «Питер», 2013.-844 с.
3. Залогова Л. А. Разработка Паскаль-компилятора. – М.: БИНОМ. Лаборатория знаний, 2012. – 183 с.: ил.
4. Савчук В.П. Обработка результатов измерений. Физическая лаборатория. Ч.1: Учеб. пособие для студентов вузов. – Одесса: ОНПУ, 2002. – 54 с.: ил.
5. Таненбаум Э. Современные операционные системы. – 3-е изд. – СПб.: «Питер», 2013. – 1120 с.
6. Тестирующий класс PHP – https://github.com/R0bur/PHP-performance-test/archive/master.zip.

Комментарии могут оставлять только зарегистрированные пользователи