Версия для печати


Быстрая функция для замены строк
http://www.delphikingdom.com/asp/viewitem.asp?catalogID=1059

Сергей Осколков
дата публикации 28-09-2004 15:36

Быстрая функция для замены строк

В Дельфи есть функция для замены одного образца в строке на другой - StringReplace. Эта функция позволяет заменить первое вхождение образца или все его вхождения, а также делать замену с учетом регистра букв (Case sensitive). Однако у этой функции есть один существенный недостаток: она очень медленно работает на больших строках при большом количестве вхождений заменяемого образца. Если нужно заменить одно слово на другое в текстовом документе размером в несколько сотен килобайт (а это не такой уж редкий случай), то время работы функции StringReplace растет катастрофически. Здесь приведена другая функция, выполняющая ту же задачу. Она взята из библиотеки Д.Батлера 'Fundamentals'. Функция использует типы и вспомогательные функции из разных модулей библиотеки, я собрал их все в один модуль для облегчения использования. Автор библиотеки на мой вопрос, не нарушает ли такое использование его копирайта, ответил, что все в порядке, так же, как и размещение функции в таком виде на "Королевстве Дельфи".

Если посмотреть, как реализована стандартная функция StringReplace, то можно увидеть, что алгоритм ее довольно прост, но в нем и заложена причина ее медленности. Если отвлечься от учета регистра букв, то алгоритм примерно таков: ищется первое вхождение старого образца, из исходной строки копируется начальная часть до положения этого вхождения, взамен старого прибавляется новый образец и все это добавляется в результат (который первоначально пуст). От исходной строки отрезается начальная часть, включая первое вхождение старого образца. Затем вся эта операция повторяется над остатком исходной строки, и так до тех пор, пока не будут заменены все старые образцы, затем к результату еще добавляется оставшаяся часть исходной строки. (Точнее сказать, операции проводятся не над самой исходной строкой, а над ее копией.)

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

В функции Дэвида Батлера StrReplace использован другой алгоритм, как написано в тексте модуля, адаптированный из процедуры Андрея Дрязгова (adapted from a routine by Andrew N. Driazgov). Сначала находятся все вхождения старого образца и положение каждого записывется в стек, а также подсчитывается общее число вхождений. Затем, исходя из длины старого и нового образцов, а также числа вхождений старого образца, вычисляется длина результирующей строки и для нее выделяется память. Затем ее содержимое заполняется, при этом используется информация о положениях всех вхождений старого образца, которая хранится в стеке.

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

Размер файла, кБСтарый образецНовый образецВремя (Борланд), мсВремя (Д. Батлер), мс
21heshe16-200-1
103царь (36 вхождений)государь28-300-4
451

416515
616 (стихотв. Пушкина)богБог98520
- // -' на '' под '3800 (3,8 сек)20
- // -

23035 (23 сек!)15-20

Сравнения проводились на относительно быстром компьютере: Athlon XP 1800, память 256 МБ. Представляю, какие были бы результаты на моем предыдущем P166MMX с 32 МБ памяти. Собственно говоря, именно на нем эта проблема и вставала особенно остро.

Предлагаемая функция имеет следующий прототип: 

function StrReplace(const Find, Replace, S: AnsiString;
                    const CaseSensitive: Boolean): AnsiString;

Здесь Find - старый образец, Replace - новый. S - исходная строка. CaseSensitive указывает, имеет ли значение регистр букв.

Функция заменяет все вхождения образца, поэтому для случая, когда нужно заменить только его первое вхождение, она не годится. Однако в таком случае не требуется быстродействие и можно использовать стандартную Борландовскую функцию. Текст функции и вспомогательных функций, которые она использует, приведены в модуле StrRepl.pas, который прилагается. Работает на Дельфи 5-7. Недостаток функции: в ней используются указатели и ассемблерные вставки, поэтому она плохо подходит для .NET.



К материалу прилагаются файлы: