![]() |
![]() ![]() |
![]() |
TarasBer |
![]()
Сообщение
#1
|
![]() Злостный любитель ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: ![]() ![]() ![]() |
Часто встречается такая задача: дана строка S, удалить из неё все символы, равные данному символу c. Первое, что приходит на ум - это воспользоваться стандратной функцией Delete:
for i := 1 to Length(S) do Однако, такой код вообще не будет работать. Дело в том, что верхний предел цикла вычисляется заранее, до выполнения цикла. Строка же при удалении из нее символов укорачивается. Таким образом, мы: а) будем пропускать символы при проверке, б) под конец цикла просто вылезем за текущий размер строки. Если идти с конца, то мы получим уже как бы рабочий код: for i := Length(S) downto 1 do Тем не менее, такой код для разбора больших текстовых документов (100КБ и больше) не годится по причине алгоритмической сложности, приводящей к существенным потерям времени. Дело в том, что Delete - это не мгновенная операция. При удалении символа надо сдвинуть весь остаток строки на одну позицию, то есть Delete работает за O(n). И тогда весь алгоритм работает за O(m*n), где m- количество удаляемых символов в тексте. Оно, как правило, тоже пропорционально длине текста. Но существует алгоритм получше. Пусть перед нами поставили такую задачу: дана строка S1, получить строку S2, которая отличается от первой только отсутствием символа c. Наличие второй строки двигает мысль в другую сторону, в голове появляется алгоритм последовательного построения второй строки с нуля путём добавления в неё всех "хороших" символов из первой строки: S2 := ''; Уже лучше! Добавление символа в конец строки не влечет за собой сдвига хвоста, как вставка/удаление символа в середине. А если переписать эту же процедуру для массива произвольного типа? Тогда нам придётся отказаться от оператора + (или перезагрузить его). Также, придётся хранить длину в отдельной переменной. j := Low(S2); // минимальный индекс для S2 Такой код уже работает за один проход массива, выполняя всю работу за положенное время O(n). А теперь посмотрим внимательно на этот код и зададимся вопросом: а что нам мешает вместо S2 написать S1? Что нам мешает строить новый массив прямо на месте старого? Ведь запись может только отставать от текущего проверяемого элемента, но не опережать его - следовательно, она не портит непроверенные элементы. Тогда получается, что ничего не мешает написать так:
Это для статического массива, у которого номер последнего используемого элемента хранится в отдельной переменной. Для строк код будет такой: j := 1; Для динамических массивов - такой:
Осталось заметить, что на (обычном) тексте в 440 кб удаление пробелов отработало: - наивный код: за 15 секунд, - обсужденный в этой статье алгоритм: меньше 10 миллисекунд. Сообщение отредактировано: TarasBer - 6.11.2010 13:37 -------------------- |
![]() ![]() |
![]() |
Текстовая версия | 10.09.2024 19:04 |